How can one draw an unbalanced binary tree – with missing nodes using the forest package?
[Tex/LaTex] Unbalanced binary tree with forest
foresttrees
Related Solutions
One option is to name some special \node
s (the root and the lowest(s) one(s)) in the tree and then use the fit
library with a circular \node
:
The example code:
\documentclass{article}
\usepackage{forest}
\usetikzlibrary{fit}
\begin{document}
\begin{forest}
[a,name=root
[b
[c
[d,name=lowestl]
[e]
]
[f ]
]
[g
[h]
[i
[j]
[k,name=lowestr]
]
]
]
\node[draw,circle,fit={(root) (lowestl) (lowestr)}] {};
\end{forest}
\end{document}
This is an interesting problem. I decided to see what I could produce using asymptote and graphviz programs.
The following asymptote
code will write an input file in the dot
language (part of graphviz
) and then perform a system call to the dot
executable to compile the graph. You will need both of these open source programs installed.
Note that the defineChildren
function is called recursively until the desired graph level is reached.
//srand(seconds());
int levels = 15;
int getWeightedRandom(int thisLevel) {
int i = floor(0.5 + unitrand() * 25 - thisLevel/2.0);
if (i < 4) return 0;
if (i < 9) return 1;
if (i < 14) return 2;
if (i < 18) return 3;
if (i < 22) return 4;
return 5;
}
file fout=output("sample.dot");
void defineChildren(string parentName) {
int thisLevel = length(parentName);
if (thisLevel >= levels) { return; }
for (int i = 1; i <= getWeightedRandom(thisLevel); ++i) {
string childName = parentName + string(i);
write(fout, parentName + " -> " + childName + ";", endl);
defineChildren(childName);
}
}
write(fout, "digraph G {", endl);
write(fout, "node [shape=circle, label=\"\"];", endl);
write(fout, "edge [arrowhead=none];", endl);
defineChildren("0");
write(fout, "}", endl);
system("dot -Tpdf sample.dot -o sample.pdf");
You call this asymptote code with the following command in a windows batch file. The -nosafe
flag is required to use the system
call that is at the end of the asymptote
code.
asy -nosafe sample.asy
If you uncomment the first line, then the random number generator will be seeded with the computer clock and the graph will be different each time you process the code. Sometimes this will result in a blank output because the first node has no children.
I played around with the getWeightedRandom
function to try to produce an appealing graph. I incorporated the level (row) of the graph in the random number function because otherwise the graph tends to get very wide at the bottom.
EDIT to give dashed lines at bottom per OP comment:
The following code is modified to make the lowest level of the tree have dashed edges. Also, the bottom row of nodes have a white border color to make them invisible.
//srand(seconds());
int levels = 15;
int getWeightedRandom(int thisLevel)
{
int i = floor(0.5 + unitrand() * 25 - thisLevel/2.0);
if (i < 4) return 0;
if (i < 9) return 1;
if (i < 14) return 2;
if (i < 18) return 3;
if (i < 22) return 4;
return 5;
}
file fout=output("sample.dot");
void defineChildren(string parentName)
{
int thisLevel = length(parentName);
if (thisLevel >= levels) { return; }
for (int i = 1; i <= getWeightedRandom(thisLevel); ++i)
{
if (thisLevel == levels - 1)
{
write(fout, "edge [style=dashed];", endl);
write(fout, "node [color=white];", endl);
}
else
{
write(fout, "edge [style=solid];", endl);
write(fout, "node [color=black];", endl);
}
string childName = parentName + string(i);
write(fout, parentName + " -> " + childName + ";", endl);
defineChildren(childName);
}
}
write(fout, "digraph G {", endl);
write(fout, "node [shape=circle, label=\"\"];", endl);
write(fout, "edge [arrowhead=none];", endl);
defineChildren("0");
write(fout, "}", endl);
system("dot -Tpdf sample.dot -o sample.pdf");
Best Answer
There are various things you might mean by 'missing nodes'. A Minimal Working Example of the kind of tree you have, together with an explanation of how you wish to adapt it would be invaluable.
The following example shows three things you might have in mind:
Node 2 is missing in a first sense: the branch simply continues without stopping to make the node. This creates an 'unbalanced' tree - the angles of the left and right branches are different.
l*=2
which doubles it.Node 6 is missing in a second sense: it is simply empty. It is treated in every way as a proper node but there is no content.
{}
just provides empty content.Node 9 is missing in a third sense: it causes a gap in the entire structure of branches and nodes. This isolates its children, 17 and 18 from the remainder of the tree.
.phantom
style demonstrated in NightRa's answer.The code: