Butcher Trees in TikZ

Question

I am trying to construct a function in Tex called \rootedtree, which takes in a a tree written in the notation of J. Butcher and then prints out the corresponding tree in TikZ.

For instance consider the trees here: http://alexander.lundervold.com/talks/ICMAT_oct2014/assets/grafting.jpg , just ignore the operations, we do not need them here. From left to right, the corresponding notation is

[*] 
[*,*]
[[*,*],*,*]

etc.

So the idea is that * corresponds to a node and the square brackets binds the nodes/trees inside to the same root. For the computer scientists out there, note that the root are downwards and the leaves are upwards.

So ultimately I want a something like this

\rootedtree([*,*])

which then draws the corresponding tree in TikZ, where the roots are evenly distributed upwards, e.g. if there is a single child, then it points directly up (90 degrees on both sides), if there are two childs then there are 60 degrees between them and 60 degrees to level on both sides.

I have close to none experience programming things in Tex myself and therefore have no idea how to get started. Any help is highly appreciated. Are there any other packages, where there is something like this and I do not have to start from scratch?

Answer 1

I made a package for this a while a go. See my blog. My solution uses PythonTeX. You can typeset forests and trees and the result will look like this:

The package is based on the following recursive definition of beautiful trees and forests (from my blog):

A forest is beautiful if:

• Each subtree is beautiful.
• The horizontal distance between two adjacent subtrees is one unit.
• The roots of the subtrees are spaced out as evenly as possible.

A tree is beautiful if:

• The forest you get by removing the root of the tree is beautiful.
• The vertical distance between the root and the next level of nodes is one unit.
• The horizontal position of the root is the median of the horizontal positions of the roots of the subtrees.

In addition:

• The tree consisting of a single node is beautiful.

The format differs from what is specified in the question, but it is very compact and should be easy to use. For example, the last example in the picture above is generated by

\forest{b,b,b[b,b[b,b,b]],b,b[b,b,b[b,b]],b[b]}

Here, b is a black node, and b[...] means that all the forests in the bracket are connected to the black node in front of it, with the black node as parent. Forests are specified by simply separating them with commas.

Colour (as in the top-right example) can be added by using

\newnodecolor{r}{red}
\newnodecolor{w}{white}
\forest{b[w,r]}

The package is hosted on GitHub.

Answer 2

Something like this?

Adaption from my earlier answer:

\documentclass{article}
\usepackage{forest}
\forestset{
  */.style={
    delay+={append={[]},}
  },
  rooted tree/.style={
    for tree={
      grow'=90,
      parent anchor=center,
      child anchor=center,
      s sep=2.5pt,
      if level=0{
        baseline
      }{},
      delay={
        if content={*}{
          content=,
          append={[]}
        }{}
      }
    },
    before typesetting nodes={
      for tree={
        circle,
        fill,
        minimum width=3pt,
        inner sep=0pt,
        child anchor=center,
      },
    },
    before computing xy={
      for tree={
        l=5pt,
      }
    }
  }
}
\usepackage{xparse}
\DeclareDocumentCommand\rootedtree{o}{\Forest{rooted tree [#1]}}
\begin{document}
\[
  \rootedtree
  [*]
  \,
  \rootedtree
  [*,*]
  \,
  \rootedtree
  [[*,*],*,*]
\]
\end{document}