java - 二叉树递归InOrder方法混淆

Question

我正在为数据结构类开发红黑树。

我有代码:

void printInorder(Node node)    //Input is initially the root node 
{ 
     if (node == null) 
     { 
           return; 
     } 
     printInorder(node.left); 
     System.out.println(node.data); 
     printInorder(node.right); 
} 

让我们以这个二叉树为例:

           50 
          /    \ 
       40     60 
      /    \       \ 
     20    45      70 
        /   \      / 
        43  47  65 

代码的输出是正确的，是:20 40 43 45 47 50 60 65 70

我对代码的理解是它会递归调用 printInorder(node.left) 直到达到 20。

此时，它将打印“20”，然后检查 printInorder(node.right)，发现它为 null 并返回到 printInorder(node.right) 语句，此时它位于方法的底部，没有更多代码可运行，因此它退出。

输出是正确的，但根据我对代码的理解，它应该在打印“20”后停止。

谁能解释这个递归循环的过程，对我来说是一步一步的？请假装你正在向有精神障碍的人解释。谢谢。

Answer 1

有个笑话“要懂递归，先懂递归”

首先让我们看一下函数。它有什么作用？

• 检查是否有左节点，如果有则去那里(还没有打印)

• 如果没有左节点打印

• 检查是否有正确的节点并转到那里。

所以这里执行。

1. 第一次执行 printInorder(50)检查是否离开 - 转到左侧节点(打印等待)
2. 现在用左节点 printInorder(40) 第二次执行检查是否离开节点 - 是的!去左边等待打印
3. 第三次执行左节点 printInorder(20)它有左节点吗？不!调用 printInorder(null) 并继续执行。现在打印了 20!它有正确的节点吗？没有
4. 我们回去吧!到第 2 步，我们有 printinorder(40) 但现在我们在去左节点之后。所以我们打印 40 并检查正确的节点 - 瞧，找到了 45!
5. 转到 45 并检查是否已离开节点(打印 45 等待)。左节点为43
6. 转到 printinorder(43)，因为它没有剩余，所以打印它!

就这样……