从下往上扫描树结构?
如果给出以下树结构或与之类似的结构:
我希望返回字符串ZYXWVUT。 我知道如何使用二叉树执行此操作,但不能使用多个子节点。 任何帮助将非常感激。
这称为树的后序遍历 :在打印节点本身的内容之前打印树的所有子树的内容。
这可以递归完成,像这样(伪代码):
function post_order(Tree node) foreach n in node.children post_order(n) print(node.text)
如果要维护ArrayList(比如node_list)以跟踪当前树节点的节点分支数,则可以从根遍历树,直到找到具有空node_list的节点。 这样您就可以识别树的叶节点。 递归方法适用于这种情况。 我没有测试过代码,但我相信这应该适用于您所要求的内容:
如果您要维护类似于下面的类来构建树:
class Node { String data; ArrayList node_list;}
以下递归函数可能是您正在寻找的:
public void traverse_tree(Node n){ if(n.node_list.isEmpty()){ System.out.print(n.data); } else{ for(Node current_node:n.node_list){ traverse_tree(current_node); } System.out.println(n.data); } }
基本上你正在看的是树的后序深度优先遍历。
这样的事情应该做到这一点
public void traverse(){ for(Child child : this.children){ child.traverse(); } System.out.print(this.value); }