这个二叉树遍历算法是如何工作的？

Question

所以我得到了算法

void traverse(Node node) {
    if (node != null) {
        traverse(node.leftChild);
        System.out.println(node.name);
        traverse(node.rightChild);
    }
}

我不明白这是怎么回事。因此，如果我处于输入为空的位置，会发生什么？假设我们打印空节点的父节点（我不知道你是怎么到那里的）并继续，假设我们已经将节点覆盖到树的深处，我们如何爬回树上？这个算法哪里可以根据需要不断跳转到父节点？

Answer 1

要理解这一点，你需要先理解递归。这里对于每个节点 parent 我们对左 child 然后对右 child 做同样的事情。并在遍历左侧后打印 parent 名称。

当节点为 null 时我们什么都不做，所以不会调用 child

void traverse(Node node) {
    if(node!=null) {
        traverse(node.leftChild);
        System.out.println(node.name);
        traverse(node.rightChild);
    }
}

示例：

parent and childs
1 -> 2,3
2 -> 4,5
3 -> 6,7

所以这里 traverse(1) 首先作为根调用。

traverse(1) -> traverse(2) // left
               traverse(3) // right

traverse(2) -> traverse(4) // left
               traverse(5) // right

traverse(3) -> traverse(6) // left
               traverse(7) // right

traverse(4) -> nothing called
traverse(5) -> nothing called
traverse(6) -> nothing called
traverse(7) -> nothing called

现在确定它调用的顺序

traverse(1) -> traverse(2) // left
                  traverse(2) -> traverse(4) // left
                                     traverse(4) -> nothing called
                                 traverse(5) // right
                                     traverse(5) -> nothing called
               traverse(3) // right
                  traverse(3) -> traverse(6) // left
                                      traverse(6) -> nothing called
                                 traverse(7) // right
                                      traverse(7) -> nothing called

这个二叉树遍历算法是如何工作的？

How does this binary tree traversal algorithm work?

java

binary-tree

traversal