What is the easiest way to print out a tree in it's tree-structure? Such as...
some root
/ | \
child1 child2 child 3
/
anotherchild / \
yup another
Even formatting it by hand is hard. How can you make a program print a tree this way?
Unless there is some nice graphical library that you can use, you will have a lot of trouble representing a hierarchy in the way that you describe.
Assuming you want to print it to the Console, or a file, you will have to contend with pre-calculating the lengths of all of the data elements in the entire tree in order to line them up correctly. And how do you handle things like line-wrap?
A much better way is to represent the tree vertically, using indentation to show a child element.
Root
- Child1
- Grandchild1
- Grandchild2
- Child2
- Grandchild3
- Grandchild4
This is much simpler to code, and more tolerant of things like linewrap - as there is only ever one element on a line. This is how a folder-browser or xml document might display its hierarchical data.
To do it this way, you do a depth-first traversal and before the recursive step you print out the node:
public void PrintNode(TreeNode node)
{
PrintNode(node, 0);
}
private void PrintNode(TreeNode node, int indentation)
{
// Print the value to the console/file/whatever
// This prefixes the value with the necessary amount of indentation
Print(node.Value, indentation);
// Recursively call the child nodes.
foreach(TreeNode childNode in node.Children)
{
PrintNode(childNode, indentation + 1); // Increment the indentation counter.
}
}
Hope that helps
The following answer is in java, but it is so simple that it can easily be transcribed to other languages:
public interface Function1<R, T1>
{
R invoke( T1 argument1 );
}
public interface Procedure1<T1>
{
void invoke( T1 argument1 );
}
public static <T> void dump( T node, Function1<List<T>,T> breeder,
Function1<String,T> stringizer, Procedure1<String> emitter )
{
emitter.invoke( stringizer.invoke( node ) );
dumpRecursive( node, "", breeder, stringizer, emitter );
}
private static final String[][] PREFIXES = { { " ├─ ", " │ " }, { " └─ ", " " } };
private static <T> void dumpRecursive( T node, String parentPrefix,
Function1<List<T>,T> breeder, Function1<String,T> stringizer,
Procedure1<String> emitter )
{
for( Iterator<T> iterator = breeder.invoke( node ).iterator(); iterator.hasNext(); )
{
T childNode = iterator.next();
String[] prefixes = PREFIXES[iterator.hasNext()? 0 : 1];
emitter.invoke( parentPrefix + prefixes[0] + stringizer.invoke( childNode ) );
dumpRecursive( childNode, parentPrefix + prefixes[1], breeder, stringizer, emitter );
}
}
It produces the following output:
Automobile
├─ Passenger Vehicle
│ ├─ Light Passenger Vehicle
│ │ ├─ Two Wheeled
│ │ │ ├─ Moped
│ │ │ ├─ Scooter
│ │ │ └─ Motorcycle
│ │ ├─ Three Wheeled
│ │ └─ Four Wheeled
│ │ ├─ Car
│ │ ├─ Station Wagon
│ │ ├─ Pick-up Truck
│ │ └─ Sports Utility Vehicle
│ └─ Heavy Passenger Vehicle
│ ├─ Bus
│ │ ├─ Single-Deck Bus
│ │ │ ├─ Mini Bus
│ │ │ └─ Big Bus
│ │ └─ Double-Deck Bus
│ └─ Coach
│ ├─ Deluxe
│ └─ Air-Conditioned
└─ Goods Vehicle
├─ Light Goods Vehicle
│ ├─ Delivery Van
│ ├─ Light Truck
│ └─ Tempo
│ ├─ Three Wheeler Tempo
│ └─ Four Wheeler Tempo
└─ Heavy Goods Vehicle
├─ Truck
└─ Tractor Trailer
...if you invoke it using the following sample program:
final class Scratch
{
static class Node
{
String name;
List<Node> children;
Node( String name, Node... children )
{
this.name = name;
this.children = Arrays.asList( children );
}
}
public static void main( String[] args )
{
Node tree = new Node( "Automobile",
new Node( "Passenger Vehicle",
new Node( "Light Passenger Vehicle",
new Node( "Two Wheeled",
new Node( "Moped" ),
new Node( "Scooter" ),
new Node( "Motorcycle" ) ),
new Node( "Three Wheeled" ),
new Node( "Four Wheeled",
new Node( "Car" ),
new Node( "Station Wagon" ),
new Node( "Pick-up Truck" ),
new Node( "Sports Utility Vehicle" ) ) ),
new Node( "Heavy Passenger Vehicle",
new Node( "Bus",
new Node( "Single-Deck Bus",
new Node( "Mini Bus" ),
new Node( "Big Bus" ) ),
new Node( "Double-Deck Bus" ) ),
new Node( "Coach",
new Node( "Deluxe" ),
new Node( "Air-Conditioned" ) ) ) ),
new Node( "Goods Vehicle",
new Node( "Light Goods Vehicle",
new Node( "Delivery Van" ),
new Node( "Light Truck" ),
new Node( "Tempo",
new Node( "Three Wheeler Tempo" ),
new Node( "Four Wheeler Tempo" ) ) ),
new Node( "Heavy Goods Vehicle",
new Node( "Truck" ),
new Node( "Tractor Trailer" ) ) ) );
dump( tree, n -> n.children, n -> n.name, s -> System.out.println( s ) );
}
}
Well, you could try something like PHP's var_dump - if you try var_dump on a tree-like array, it will give you a fair representation of that tree, that is:
root {
child1 {
anotherchild
}
child2
child3 {
yup
another
}
}
How about this answer to a similar question? It prints a nice ASCII-art tree.
Or maybe this one if you want to go fully graphical?
I had to do this last year writing a family tree application. Found a java tutorial online that helped but my Google-fu failed me today so I will have to simply explain it.
It is simply a recursive algorithm that adjusts position of parent node based on child nodes. In pseudocode it is something like this:
positionNode (node,x,y) {
foreach (child in node.children) {
positionNode(child,x,y+1)
x ++
}
node.x = (x-1)/2
node.y = y
}
I may not be remembering this correctly, you may need to tweak the code a bit to get it right.
