时间戳

首页 > 解决方案 > 如何理解 Java 中 BST 的递归中序遍历？

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

问题描述

我试图了解实现二叉搜索树的中序遍历的成熟方法如何在 Java 中运行。

我得到以下代码：

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

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

我的问题是，我不明白如何使用此代码处理遍历。我已经在一张纸上可视化了我的想法链供大家查看，圆圈是节点，黑色方块是空节点，而被包围的节点是当前（this）对象。当我遵循伪代码时，我会在最后进入一个空节点并遇到递归死胡同。一旦我们已经将子树节点设置为当前的 this 对象，我也完全不明白代码如何能够回到树层次结构中。

我的可视化

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

标签： javabinary-search-tree

解决方案

当我遵循伪代码时，我会在最后进入一个空节点并遇到递归死胡同

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

毕竟，当方法 X 调用方法 Y 并且方法 Y 结束时，控件返回到方法 X。当方法 X 和 Y 具有相同名称时，仍然如此。递归仅在原始inorder()调用（在树的根上执行）返回后结束。

您可以对对该方法的每个调用进行编号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)

等等...

推荐阅读