old*_*ice 5 language-agnostic tree data-structures
在树形结构中打印树的最简单方法是什么？如...
some root
/ | \
child1 child2 child 3
/
anotherchild / \
yup another
即使手工格式化也很难.如何让程序以这种方式打印树？
除非您可以使用一些不错的图形库,否则以您描述的方式表示层次结构会遇到很多麻烦.
假设您要将其打印到控制台或文件,则必须与预先计算整个树中所有数据元素的长度进行竞争,以便正确排列它们.你如何处理像换行的事情？
更好的方法是垂直表示树,使用缩进来显示子元素.
Root
- Child1
- Grandchild1
- Grandchild2
- Child2
- Grandchild3
- Grandchild4
这对代码来说要简单得多,而且对linewrap之类的东西更加宽容 - 因为一行中只有一个元素.这是文件夹浏览器或xml文档可能显示其分层数据的方式.
要以这种方式执行此操作,请执行深度优先遍历,然后在递归步骤之前打印出节点:
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.
}
}
希望有所帮助
下面的答案是用java编写的，但它非常简单，可以很容易地转录成其他语言：
\n\npublic interface Function1<R, T1>\n{\n R invoke( T1 argument1 );\n}\n\npublic interface Procedure1<T1>\n{\n void invoke( T1 argument1 );\n}\n\npublic static <T> void dump( T node, Function1<List<T>,T> breeder,\n Function1<String,T> stringizer, Procedure1<String> emitter )\n{\n emitter.invoke( stringizer.invoke( node ) );\n dumpRecursive( node, "", breeder, stringizer, emitter );\n}\n\nprivate static final String[][] PREFIXES = { { " \xe2\x94\x9c\xe2\x94\x80 ", " \xe2\x94\x82 " }, { " \xe2\x94\x94\xe2\x94\x80 ", " " } };\n\nprivate static <T> void dumpRecursive( T node, String parentPrefix,\n Function1<List<T>,T> breeder, Function1<String,T> stringizer,\n Procedure1<String> emitter )\n{\n for( Iterator<T> iterator = breeder.invoke( node ).iterator(); iterator.hasNext(); )\n {\n T childNode = iterator.next();\n String[] prefixes = PREFIXES[iterator.hasNext()? 0 : 1];\n emitter.invoke( parentPrefix + prefixes[0] + stringizer.invoke( childNode ) );\n dumpRecursive( childNode, parentPrefix + prefixes[1], breeder, stringizer, emitter );\n }\n}\n它产生以下输出：
\n\nAutomobile\n \xe2\x94\x9c\xe2\x94\x80 Passenger Vehicle\n \xe2\x94\x82 \xe2\x94\x9c\xe2\x94\x80 Light Passenger Vehicle\n \xe2\x94\x82 \xe2\x94\x82 \xe2\x94\x9c\xe2\x94\x80 Two Wheeled\n \xe2\x94\x82 \xe2\x94\x82 \xe2\x94\x82 \xe2\x94\x9c\xe2\x94\x80 Moped\n \xe2\x94\x82 \xe2\x94\x82 \xe2\x94\x82 \xe2\x94\x9c\xe2\x94\x80 Scooter\n \xe2\x94\x82 \xe2\x94\x82 \xe2\x94\x82 \xe2\x94\x94\xe2\x94\x80 Motorcycle\n \xe2\x94\x82 \xe2\x94\x82 \xe2\x94\x9c\xe2\x94\x80 Three Wheeled\n \xe2\x94\x82 \xe2\x94\x82 \xe2\x94\x94\xe2\x94\x80 Four Wheeled\n \xe2\x94\x82 \xe2\x94\x82 \xe2\x94\x9c\xe2\x94\x80 Car\n \xe2\x94\x82 \xe2\x94\x82 \xe2\x94\x9c\xe2\x94\x80 Station Wagon\n \xe2\x94\x82 \xe2\x94\x82 \xe2\x94\x9c\xe2\x94\x80 Pick-up Truck\n \xe2\x94\x82 \xe2\x94\x82 \xe2\x94\x94\xe2\x94\x80 Sports Utility Vehicle\n \xe2\x94\x82 \xe2\x94\x94\xe2\x94\x80 Heavy Passenger Vehicle\n \xe2\x94\x82 \xe2\x94\x9c\xe2\x94\x80 Bus\n \xe2\x94\x82 \xe2\x94\x82 \xe2\x94\x9c\xe2\x94\x80 Single-Deck Bus\n \xe2\x94\x82 \xe2\x94\x82 \xe2\x94\x82 \xe2\x94\x9c\xe2\x94\x80 Mini Bus\n \xe2\x94\x82 \xe2\x94\x82 \xe2\x94\x82 \xe2\x94\x94\xe2\x94\x80 Big Bus\n \xe2\x94\x82 \xe2\x94\x82 \xe2\x94\x94\xe2\x94\x80 Double-Deck Bus\n \xe2\x94\x82 \xe2\x94\x94\xe2\x94\x80 Coach\n \xe2\x94\x82 \xe2\x94\x9c\xe2\x94\x80 Deluxe\n \xe2\x94\x82 \xe2\x94\x94\xe2\x94\x80 Air-Conditioned\n \xe2\x94\x94\xe2\x94\x80 Goods Vehicle\n \xe2\x94\x9c\xe2\x94\x80 Light Goods Vehicle\n \xe2\x94\x82 \xe2\x94\x9c\xe2\x94\x80 Delivery Van\n \xe2\x94\x82 \xe2\x94\x9c\xe2\x94\x80 Light Truck\n \xe2\x94\x82 \xe2\x94\x94\xe2\x94\x80 Tempo\n \xe2\x94\x82 \xe2\x94\x9c\xe2\x94\x80 Three Wheeler Tempo\n \xe2\x94\x82 \xe2\x94\x94\xe2\x94\x80 Four Wheeler Tempo\n \xe2\x94\x94\xe2\x94\x80 Heavy Goods Vehicle\n \xe2\x94\x9c\xe2\x94\x80 Truck\n \xe2\x94\x94\xe2\x94\x80 Tractor Trailer\n...如果您使用以下示例程序调用它：
\n\nfinal class Scratch\n{\n static class Node\n {\n String name;\n List<Node> children;\n\n Node( String name, Node... children )\n {\n this.name = name;\n this.children = Arrays.asList( children );\n }\n }\n\n public static void main( String[] args )\n {\n Node tree = new Node( "Automobile",\n new Node( "Passenger Vehicle",\n new Node( "Light Passenger Vehicle",\n new Node( "Two Wheeled",\n new Node( "Moped" ),\n new Node( "Scooter" ),\n new Node( "Motorcycle" ) ),\n new Node( "Three Wheeled" ),\n new Node( "Four Wheeled",\n new Node( "Car" ),\n new Node( "Station Wagon" ),\n new Node( "Pick-up Truck" ),\n new Node( "Sports Utility Vehicle" ) ) ),\n new Node( "Heavy Passenger Vehicle",\n new Node( "Bus",\n new Node( "Single-Deck Bus",\n new Node( "Mini Bus" ),\n new Node( "Big Bus" ) ),\n new Node( "Double-Deck Bus" ) ),\n new Node( "Coach",\n new Node( "Deluxe" ),\n new Node( "Air-Conditioned" ) ) ) ),\n new Node( "Goods Vehicle",\n new Node( "Light Goods Vehicle",\n new Node( "Delivery Van" ),\n new Node( "Light Truck" ),\n new Node( "Tempo",\n new Node( "Three Wheeler Tempo" ),\n new Node( "Four Wheeler Tempo" ) ) ),\n new Node( "Heavy Goods Vehicle",\n new Node( "Truck" ),\n new Node( "Tractor Trailer" ) ) ) );\n dump( tree, n -> n.children, n -> n.name, s -> System.out.println( s ) );\n }\n}\n好吧，你可以尝试类似 PHP 的 var_dump - 如果你在树状数组上尝试 var_dump，它会给你一个该树的公平表示，即：
root {
child1 {
anotherchild
}
child2
child3 {
yup
another
}
}