c++ - 这个函数发生了什么？

Question

我一直在寻找一种方法来按顺序显示二叉搜索树的内容。我发现这种方法似乎很流行，但我不明白这种递归是如何工作的。代码将如何到达 cout？当主函数调用时，根节点也被传递到函数中。编辑:这是考虑到“root!=NULL”。

    void display(struct tree *p)
{
    while(p!=NULL)
    {
        display(p->left);
        cout<<p->data;
        display(p->right);
    }
}

Answer 1

首先，不是while(p!=NULL)你应该使用 if (p != null) .否则，如果根节点不为空，则会出现无限循环。

首先显示左子树递归调用display(p->left) .之后它显示节点本身( cout<data )，最后递归调用右子树 display(p->right) .

假设您有以下树:

      4
  2       6
1  3     5

对 display(root) 的调用导致以下函数调用:

display(4)
  display(2)
    display(1)
      display(null)
      cout 1
      display(null)
    cout 2
    display(3)
      display(null)
      cout 3
      display(null)
  cout 4
  display(6)
    display(5)
      display(null)
      cout 5
      display(null)
    cout 6
    display(null)

当为节点“1”调用该函数时，它首先通过调用display(p->left) 显示左子树。 .
该函数通知 p==null因此直接返回。
所以控制权返回到 display(1)。
下一条语句是 cout << 1 .
之后，它通过调用 display(p->right) 显示右子树。 .
该函数通知 p==null因此直接返回。
因此，控制再次返回到显示 (1)。
此时，display(1) 已终止，控制权返回到调用 display(1) 的函数，即 display(2)。
它完成了对 display(p->left) 的调用(为“1”)，因此执行下一条语句，即 cout << 2 .