从下往上扫描树结构？

Question

如果给定以下或类似的树结构：

``` A / | \ B C D / \ | E F G / \ H I ```

我想要返回字符串 "ZYXWVUT"。我知道如何处理二叉树，但不知道如何处理多叉树。非常感谢您的帮助。

- user2998228

---

你基本上要寻找一个“反向”的广度优先算法。编辑：只需读取树，如果你正在寻找ZYXWVUT，那么这只是深度优先列表... - Rogue

我认为这是后序遍历。 - Ron

澄清一下：您想按照树中节点的深度打印它们吗？因为仅凭您的示例，很难确定您的问题。 - V G

Answer 1

这被称为树的后序遍历：在打印节点本身的内容之前，您需要打印树的所有子树的内容。

这可以通过递归来完成，如下所示（伪代码）：

function post_order(Tree node)
    foreach n in node.children
        post_order(n)
    print(node.text)

- Sergey Kalinichenko

---

包含一张图片，希望您不介意进行翻译。至于原帖中的担忧：“我知道如何在二叉树上操作，但不知道如何处理多个子节点的树”。我认为树的遍历方法适用于任何具有多个子节点的树。 - Ron

Answer 2

如果您正在维护一个ArrayList（比如node_list）来跟踪从当前树节点分支出的节点数量，那么您可以从根节点遍历树，直到找到一个具有空的node_list的节点。这样，您就能够识别出树的叶节点。对于这种情况，递归方法是可行的。我还没有测试过代码，但我相信这应该可以满足您的要求：

如果您正在维护类似于下面的类来构建您的树：

class Node {
     String data;
     ArrayList<Node> 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);
    }
}

基本上你所看到的是树的后序深度优先遍历。

- Rohit Jose

Answer 3

类似这样应该可以做到

public void traverse(){
    for(Child child : this.children){
        child.traverse();
    }
    System.out.print(this.value);
}

- BevynQ