在Java中遍历二叉树的所有节点

Question

假设我有一个简单的二叉树节点类，如下所示：

public class BinaryTreeNode {
    public String identifier = "";
    public BinaryTreeNode parent = null;
    public BinaryTreeNode left = null;
    public BinaryTreeNode right = null;

    public BinaryTreeNode(BinaryTreeNode parent, String identifier)
    {
        this.parent = parent; //passing null makes this the root node
        this.identifier = identifier;
    }

    public boolean IsRoot() {
        return parent == null;
    }
}

如何添加一个方法，能够递归地遍历任意大小的树，从左到右访问每个现有节点，而不会重新访问已经遍历过的节点呢？

这种方法行得通吗？：

public void traverseFrom(BinaryTreeNode rootNode)
{
    /* insert code dealing with this node here */

    if(rootNode.left != null)
        rootNode.left.traverseFrom(rootNode.left);

    if(rootNode.right != null)
        rootNode.traverseFrom(rootNode.right);
}

- RectangleEquals

---

@PeterWooster - 对的，除了我从每个节点调用遍历方法，导致递归对每个节点进行递归，而不仅仅是从根节点开始。 - RectangleEquals

Answer 1

你可以实现三种二叉树遍历：

示例：

考虑以下二叉树：

Pre-order traversal sequence: F, B, A, D, C, E, G, I, H (root, left, right)
In-order traversal sequence: A, B, C, D, E, F, G, H ,I (left, root, right)
Post-order traversal sequence: A, C, E, D, B, H, I, G, F (left, right, root)

代码示例：

二叉树的从左到右遍历，或称为中序遍历：

public void traverse (Node root){ // Each child of a tree is a root of its subtree.
    if (root.left != null){
        traverse (root.left);
    }
    System.out.println(root.data);
    if (root.right != null){
        traverse (root.right);
    }
}

- codeMan

---

递归总是处理树形结构的最佳方式。有趣的挑战则是如何在不使用递归的情况下解决这个问题。 - Peter Wooster

@Peter Wooster 迭代解决方案对于初学者来说有些难以理解，因此我认为为什么要增加复杂性呢。 - codeMan

我同意，多年前我也写过类似的汇编代码，当然使用了栈。 - Peter Wooster

我知道我很接近了，但也感觉有点不对劲。谢谢你的解释，并+1给你的教育。 - RectangleEquals

@Peter Wooster 你用汇编语言实现的吗？？佩服！！ - codeMan

Answer 2

codeMan是正确的。遍历将访问左侧的每个节点。一旦到达左侧最后一个节点，它就开始沿右侧节点往回工作。这是深度优先搜索（DFS）遍历。因此，每个节点只被访问一次，并且算法运行时间为O(n)。祝编码愉快。

- RouteMapper