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:
You can specify edges explicitly when needed, and specify [draw=none]
. I've also simplified your tree: you don't need to enclose every node in a \node
command unless you have independent reasons for referring to them. For this kind of tree, it might be helpful to make every node a uniform size, so that the sibling distances don't vary. You can do this by setting a minimum size for the every tree node/.style
. I've given a second tree showing how this can be done. In a single tree, you could add the option to the {tikzpicture}
environment itself instead of using \tikzset
.
\documentclass{article}
\usepackage{tikz-qtree}
\begin{document}
\begin{tikzpicture}[grow'=up]
\Tree [.8
[.5
[.3
\edge[]; {1}
\edge[draw=none]; {} ]
6 ]
12 ]
\begin{scope}[xshift=2in]
\tikzset{every tree node/.style={minimum width=2em}}
\Tree [.8
[.5
[.3
\edge[]; {1}
\edge[draw=none]; {} ]
6 ]
12 ]
\end{scope}
\end{tikzpicture}
\end{document}
Best Answer
Putting a nil node is not tricky but rather good maths. Adding manually some space would be ugly.
In pstree you manipulate (ordered) n-ary trees so there is no notion of left or right child node. You can only give a list of child nodes (ordered).
Think of how you will implement binary trees (t := () | (t, t)) with ordered n-ary trees (t := list of trees). The two following binary trees are different.
While they are equal as n-ary trees. You need to explicitly encode the skip of the left child node to simulate that in n-ary trees.
The pstree creators proposed you a distinguished
\Tn
node (nil node) for that purpose.Just like when a missing information is an information.