如何理解 Java 中 BST 的递归中序遍历？

Question

我正在尝试了解实现二叉搜索树中序遍历的成熟方法在 Java 中的运作方式。

我得到以下代码：

public void inorder() {
       if (!this.isEmpty()) {
           this.getLeft().inorder();
           System.out.print(this.getValue());
           this.getRight().inorder();
       }
   }

和isEmpty()返回当前Node是否为null，getValue()返回当前节点的值，getLeft()以及getRight()分别返回左右后继节点。

我的问题是，我不明白如何使用这段代码处理遍历。我把我的思路可视化在一张sheet纸上给大家看，圆圈是节点，黑色方块是空节点，被圈起来的节点是当前（this）对象。当我遵循伪代码时，我会在最后到达一个空节点并遇到递归死胡同的情况。我也完全不明白一旦我们已经将子树节点设置为当前 this 对象，代码如何能够返回树层次结构。

My visualization

我是不是想错了，如果是这样，有人可以帮助我理解正确的做法吗？代码有效，但我真的需要了解它是如何实现的。任何帮助将不胜感激

Answer 1

As I am following the pseudocode, I would land in a null node at the end and hit the recursive dead-end case

当您到达“死胡同”的情况时，这意味着递归树的当前分支结束。这并不意味着整个递归结束。

毕竟，当方法X调用方法Y，方法Y结束时，控件returns到方法X。当方法X和Y同名时，仍然如此。递归仅在原始 inorder() 调用（在树的根上执行）returns.

之后结束

您可以对 inorder() 方法的每次调用进行编号，以便将它们区分开来：

1. root.inorder() calls
    2. root.getLeft().inorder() calls
        3. root.getLeft().getLeft().inorder() calls
            4. root.getLeft().getLeft().getLeft().inorder()
               this node is empty, so inorder() #4 method returns control to the previous one (#3)
           now #3 call prints the current node via System.out.print(this.getValue())
             which prints the left most node of the tree 
           then #3 calls 
            5. root.getLeft().getLeft().getRight().inorder()
               this node is also empty, so the current inorder() method returns control to #3
           now #3 also ends, and returns control to the previous method (#2)

等等...

如何理解 Java 中 BST 的递归中序遍历？

How to understand a recursive inorder traversal of a BST in Java?

java

binary-search-tree