java - 递归如何遍历树

Question

java version "1.8.0_92"

我正在研究树以及如何使用递归遍历它们。但我对它的工作原理感到困惑。

  public void preOrder(BinaryTree root) {
        if(root != null) {
            System.out.println(root);
            preOrder(root.leftChild);  <-- this gets called and will start from the top of the function
            preOrder(root.rightChild); <-- how can this get called if the top one will always calls itself?
        }
    }

我认为第二个 preOrder 永远不会被调用，因为上面的调用总是会调用自身，因此第二个 preOrder 永远不会被执行。

Answer 1

它并不总是调用自己。它会一直持续下去，直到触底且 leftChild 为空。然后执行返回而不做任何事情——它备份一级并在最低级别父节点的 rightChild 上重复。当该调用也用完子节点时，执行会从处理该最低级别的父节点返回，再次备份一个调用，并执行该节点的 rightChild ...直到整个树都已完成已遍历。