Take the 2-minute tour ×
TeX - LaTeX Stack Exchange is a question and answer site for users of TeX, LaTeX, ConTeXt, and related typesetting systems. It's 100% free, no registration required.

clarification: when I say "graph", I mean the computer science term.

I want to draw a full binary tree of h height. It means that there's one root with two sons, each son has two sons and so forth.

Is there a way to make LaTeX (with tikZ for example, but any other way will do) draw a full binary tree of a given h height without manually drawing each node? This should also allow me to write on the edges and on the leaves.

Thanks.

share|improve this question
5  
Is there a reason that you tagged this with lyx? Because your question doesn't mention LyX at all. (Also, it somewhat hurts to hear that 'graph' is a 'computer science term'. Graph theory goes at least back to Euler.) –  Caramdir Nov 30 '10 at 18:42
    
I'm using LyX, it might be relevant - I have no idea. –  Amir Rachum Nov 30 '10 at 19:08
    
Lyx does not seem relevant here, so I've removed the tag –  Joseph Wright Nov 30 '10 at 19:18
1  
a beautiful tree can be made by the package ctan.org/tex-archive/graphics/tree .It is aimed at linguists, but I guess both computer scientists as well as mathematicians can be permitted to use it! With John's full denunciation of himself in the sample! –  Yiannis Lazarides Nov 30 '10 at 19:49
1  
@Yiannis: I'd recommend qtree, along with tikz-qtree‌​, instead of that; I demonstrated it in another answer. Its biggest advantage is that you don't have to preprocess your LaTeX source (ick); it also generalizes to TikZ if you want it to. Again aimed at linguists, but really should be more widely known and used. I don't think it's as automatic as what Amir wants, though. –  Antal S-Z Nov 30 '10 at 20:18
add comment

4 Answers

up vote 11 down vote accepted

Here's an admittedly hackish solution I just whipped up using TikZ:

\makeatletter
\def\bt@parent@index#1{\count0=#1\typeout{c01: \the\count0}\advance\count0 by -1\typeout{c02: \the\count0}\divide\count0 by 2\typeout{c03: \the\count0}\the\count0}
\newenvironment{binarytree}[1]{
  \begingroup
  \newcount\totaldepth\totaldepth=#1
  \def\edge##1##2{\expandafter\edef\csname bt@edge##1\endcsname{##2}}
  \def\leaf##1##2{\expandafter\edef\csname bt@leaf##1\endcsname{##2}}
}{
  \newcount\rowlength % The number of nodes in the current generation of the tree
  \rowlength=1
  \newcount\numnodes\numnodes=0
  \pgfmathparse{2^(\the\totaldepth)}
  \newdimen\nodespread\nodespread=\pgfmathresult cm
  %% Each node will be labeled as `node#', where # is its index.  The nodes are indexed as if they were in an Ahnentafel list.
  \newcount\parent
  \begin{tikzpicture}
    \foreach \depth in {1,...,\the\totaldepth} {
        \foreach \i in {1,...,\the\rowlength} {
          \pgfmathparse{(\the\numnodes - 1) / 2}
          \parent=\pgfmathresult
          \ifnum\parent=\numnodes
            %% Special case for the root node of the tree
            \node[fill,circle,inner sep=2pt] at (0,0) (node\the\numnodes) {};
          \else\pgfmathparse{int(mod(\i,2))}\ifnum\pgfmathresult=1
            %% This is the first node of a subtree's generation
            \node[fill,circle,inner sep=2pt] at ([yshift=-1cm,xshift=-0.7\nodespread] node\the\parent) (node\the\numnodes) {};
          \else
            %% This is a node in the middle of a generation
            \count0=\the\numnodes
            \advance\count0 by -1
            \node[right of=node\the\count0,right=\nodespread,fill,circle,inner sep=2pt] (node\the\numnodes) {};
          \fi\fi
          \ifnum\parent<\numnodes
            %% Draw the edge to the parent
            \draw (node\the\parent) -- node[sloped,above] {\csname bt@edge\the\numnodes\endcsname} (node\the\numnodes);
          \fi
          \ifnum\depth=\totaldepth
            %% We are drawing a leaf, so see if it has a label
            \node[below of=node\the\numnodes] (leaf\the\numnodes) {\csname bt@leaf\the\numnodes\endcsname};
          \fi
          \global\advance\numnodes by 1
        }
        \global\multiply\rowlength by 2
        \global\nodespread=0.5\nodespread
    }
  \end{tikzpicture}
  \endgroup
}
\makeatother

You'll have to tweak it a bit to get the desired spacing between nodes.

Just stick that code that the top of your document (or in a new .sty). Then you can use it like this:

\begin{binarytree}{3} %% The "3" here is the depth of the tree
    \edge{1}{First edge.}
    \edge{5}{Edge 5.}
    \leaf{3}{Leaf 1}
    \leaf{4}{Leaf 2}
    \leaf{5}{Leaf 3}
\end{binarytree}

The edges and leaves are indexed according to their order in the tree's associated Ahnentafel list. The result should look like this:

Resulting tree.

share|improve this answer
    
Amazing, thank you so much! –  Amir Rachum Dec 9 '10 at 12:21
add comment

This is more "proof of concept" than a fully working example; the point of it is as follows. Firstly, to show how to build up a tree recursively using a \foreach loop. Secondly, it uses the tree stuff already in TikZ. Thirdly, someone just mentioned the Htree to me and in figuring out how to draw that, I had an answer-in-search-of-a-question and it occurred to me that with a slight modification, the routine for drawing the H-tree could be adapted to a full binary tree. What's missing is the labelling facilities, though these could be added in without too much difficulty, I'm sure.

Here's the results, first the H-tree:

Htree

and then the binary tree:

binary tree

And now the code:

\documentclass{standalone}
\usepackage{tikz}

\makeatletter

\tikzset{
  htree leaves/.initial=2,
  sibling angle/.initial=20,
  htree level/.initial={}
}

\def\htree@growth{%
  \pgftransformrotate{%
    (\pgfkeysvalueof{/tikz/sibling angle})*(-.5-.5*\tikznumberofchildren+\tikznumberofcurrentchild)}%
  \pgftransformxshift{\the\tikzleveldistance}%
  \pgfkeysvalueof{/tikz/htree level}%
}
\tikzstyle{htree}=[
  growth function=\htree@growth,
  sibling angle=180,
  htree level={
    \tikzleveldistance=.707\tikzleveldistance
    \pgfsetlinewidth{.707*\the\pgflinewidth}
  }
]

\tikzstyle{btree}=[
  growth function=\htree@growth,
  sibling angle=60,
  htree level={
    \tikzleveldistance=.55\tikzleveldistance
    \pgfsetlinewidth{.707*\the\pgflinewidth}
  }
]

\long\def\ge@addto@macro#1#2{%
  \begingroup
  \toks@\expandafter\expandafter\expandafter{\expandafter#1#2}%
  \xdef#1{\the\toks@}%
  \endgroup}

\newcommand{\htree}[2][]{%
  \def\htree@start{\noexpand\coordinate}
  \def\htree@end{}
  \foreach \l in {0,...,#2} {
    \g@addto@macro\htree@start{child foreach \noexpand\x in {1,2} {\iffalse}\fi}
    \g@addto@macro\htree@end{\iffalse{\fi}}
    \global\let\htree@start\htree@start
    \global\let\htree@end\htree@end
  }
  \edef\htree@cmd{\htree@start\htree@end;}
  \begin{scope}[htree,#1]
  \htree@cmd
  \end{scope}
}
\makeatother

\begin{document}
\begin{tikzpicture}[
  rotate=-90,
  yscale=.5
]
\htree[
  btree,
  level distance=3cm,
  line width=8pt,
]{7}
\end{tikzpicture}
\end{document}

It works by building up the appropriate {child foreach \x in {1,2} list. We have to be a bit sneaky about groupings (there may be a sneakier way). The rest is just modified from the trees library in TikZ. I added a hook in to the growth routine so that it was easy to define a style for each level as "some modification of the previous style", instead of having to define styles for each level specifically. Using a different growth function could result in something a little more like the example given in ESultanik's answer - the main point of this answer was to build up the tree using a loop.

share|improve this answer
add comment

You could use a combination of grahviz and dot2tex, in order to generate nice graphs. This combination can produce nice graphs.

share|improve this answer
add comment

There is a new library for automatic (or algorithmic, as we call it in the manual) graph drawing in development in the CVS repository of PGF/TikZ. The first serious graph drawing algorithms are currently being worked on (including force-based algorithms, algorithms for layered drawings such as flow charts, and also algorithms for drawing trees).

I don't know about the status of the tree algorithms but let's hope that this feature (and the algorithms I mentioned) will become available with a new PGF/TikZ release sometime in 2011.

share|improve this answer
    
thanks for the interesting info! –  Amir Rachum May 11 '11 at 14:09
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.