如何理解java中bst的递归有序遍历？

lx0bsm1f 于 2021-07-03 发布在 Java

关注(0)|答案(1)|浏览(322)

我试图理解实现二叉搜索树有序遍历的成熟方法是如何在java中起作用的。
我得到了以下代码：

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

与 isEmpty() 返回当前节点是否为 null , getValue() 返回当前节点的值，以及 getLeft() 以及 getRight() 分别返回左后继节点和右后继节点。
我在这里的问题是，我不明白如何用这个代码处理遍历。我已经在一张纸上把我的思想链形象化了，让你们看，圆圈是节点，黑色正方形是空节点，被包围的节点是当前（这个）对象。当我在跟踪伪代码时，我会在最后到达一个空节点，然后碰到递归死区。我也完全不明白，一旦我们已经将子树节点设置为当前this对象，代码如何能够回到树层次结构中。
我的想象
我是不是想错了，如果是的话，有人能帮我理解正确的方法吗？代码是有效的，但我真的需要理解它是如何实现的。任何帮助都将不胜感激

Java binary-search-tree

来源：https://stackoverflow.com/questions/65289018/how-to-understand-a-recursive-inorder-traversal-of-a-bst-in-java

1条答案

按热度按时间

cnjp1d6j1#

当我在跟踪伪代码时，我会在结尾处到达一个空节点，并碰到递归死区的情况
当您到达“死胡同”情况时，这意味着递归树的当前分支结束。这并不意味着整个递归都结束了。
毕竟，当方法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)

等等。。。

赞(0）回复(0）举报 2021-07-03

我来回答

如何理解java中bst的递归有序遍历？

1条答案

相关问题

热门标签

最新问答