澄清二叉搜索树中的有序遍历

Question

我正在学习 Java 中的树，在我正在学习的书中遇到了一些令人困惑的行。中序遍历给出的图是这样的：

遍历（递归）的代码是：

private void inOrder(Node leftRoot) {
    if (localRoot != null) {
        inOrder(localRoot.leftChild);
        System.out.println(localRoot.iData + " ");
        inOrder(localRoot.rightChild);
    }
 }

我感到困惑的行是：

Now we’re back to inOrder(A), just returning from traversing A’s left child. We visit A and then call inOrder() again with C as an argument, creating inOrder(C). Like inOrder(B), inOrder(C) has no children, so step 1 returns with no action, step 2 visits C, and step 3 returns with no action. inOrder(B) now returns to inOrder(A).

However, inOrder(A) is now done, so it returns and the entire traversal is complete. The order in which the nodes were visited is A, B, C; they have been visited inorder. In a binary search tree this would be the order of ascending keys.

我已经突出显示了我卡住的部分。首先，我认为在第三步中，inOrder(C)[and not inOrder(B)] returns to inOrder(A)。其次，访问节点的顺序应该是 B -> A - > C.

请帮帮我！

Answer 1

是的，你在这两方面都是正确的。这些似乎是拼写错误，或 勘误表。

作为旁注，我认出了您 post 中的图表样式，因为我多年前从同一本书 (Lafore) 学习了数据结构。不幸的是，他似乎没有在任何地方发布勘误表，这令人失望，因为大多数作者都在努力做到这一点。

澄清二叉搜索树中的有序遍历

Clarification over In-Order traversal in binary search tree

java

algorithm

tree

recursion