二叉搜索树遍历法，是什么使它从左下的子（叶）向上？

Question

我很难理解SearchTree“按顺序遍历方法”在到达最左边的叶子后是如何向上的。我理解，一开始根变成leftchild，然后再往下一层leftchild，再往下一层，直到它变成最低的左叶，它没有左子，也没有右子。好的。但是在根是最后一片叶子之后，它怎么会变平。使traverse方法从左下的子级上升一级的确切代码行是什么。因为对于该节点,root.leftChild和root.rightChild都为空。这对我来说是魔法。

public void inOrderTraverseTree（节点根）{

        if (root != null) {

            inOrderTraverseTree(root.leftChild);

            System.out.println(root);

            inOrderTraverseTree(root.rightChild);

        }

}

Answer 1

这是因为递归函数的属性，它在执行后返回给父调用函数。例如
20
/\
10 30

这是一棵根为20的树。现在遍历您的inOrderTraverseTree代码：1。调用inOrderTraverseTree(20)2。检查根是否为null，这里20不是null。3.调用inOrderTraverseTree(10){20的左边是10}4。检查root是否为null，这里10不是null。5.调用inOrderTraverseTree（null）{10的左侧为null}6。检查root是否为null，这里是null。因此退出“if”，返回到调用函数，即步骤4{root=10}7。打印根，即打印10。8.调用inOrderTraverseTree（null）{10的右边为null}9。检查root是否为null，此处为null。因此退出“if”，返回调用函数，即步骤3{root=20}。{complete execution for root=10 is completed}10。打印root，即打印20。11.调用inOrderTraverseTree(30){20的右边是30}12.检查根是否为null，这里30不为null。13.调用inOrderTraverseTree（null）{30的左侧为null}14。检查root是否为null，这里是null。因此退出“if”，返回到调用函数，即步骤12{root=30}15。打印根，即打印30。16.调用inOrderTraverseTree（null）{30的右边为null}17。检查root是否为null，此处为null。因此退出“if”，返回调用函数，即步骤11{root=20}。{root=30完成完全执行}

这样，根为20的inOrderTraverseTree调用的完全执行也就完成了，打印的值是10（在步骤7中）、20（在步骤10中）、30（在步骤15中）：10 20 30。现在来看“使遍历方法从左下的子级上升一级的代码”：您可以在第9步中看到这一点。其中,当最左侧子级的完整函数循环完全执行时,最左侧子级返回给其父级调用函数。这是递归函数的主要性质。