二叉搜索树上的预序遍历

Question

对于二叉搜索树：7为根，1为左子，10为右子。

                                        7
                                      1   10

我试过调试这个函数，看看它是如何工作的，但我似乎不能理解一件事。函数检查并看到1的左子项和右子项都为空后，它就移动到节点10，然后检查右子项是否为空。有人能解释一下递归模式，以及为什么方法在初始检查节点1后没有退出。

private void preOrderTraversal(Node node)
{       
    if(node == null) return; 
    System.out.println(node.data);
    preOrderTraversal(node.leftChild);
    preOrderTraversal(node.rightChild);
}

Answer 1

方法preordertraversal（以Node=1作为参数调用，即以左边的子项调用）确实存在，但随后控制流跳回到调用它的方法，即preordertraversal（以Node=7作为参数调用根）。所以一切都很好。

添加这几行跟踪代码，您就会
明白我的意思，一切都会变得清晰起来。

private void preOrderTraversal(Node node)
{
    System.out.println("Now in preOrderTraversal with " + 
                       (node==null ? "null." : node.data + "."));
    if(node == null) {
        System.out.println("Done. Exit 1 taken.");
        return;
    }
    System.out.println(node.data);
    preOrderTraversal(node.leftChild);
    preOrderTraversal(node.rightChild);
    System.out.println("Done. Exit 2 taken.");
}