这个功能发生了什么？

Question

我正在寻找一种方法来在inorder方法中显示二进制搜索树的内容.我发现这种方法似乎很受欢迎,但我无法理解这种递归是如何工作的.代码将如何达到cout？当main函数调用时,根节点也被传递给函数.编辑:这是考虑"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).否则,如果根节点不为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直接返回.
因此控制返回到显示(1).
下一个陈述是cout << 1.
之后,它通过调用显示正确的子树display(p->right).
该功能通知p==null直接返回.
再次,控制返回到显示(1).
此时,显示器(1)终止并且控制返回到调用显示器(1)的功能,即显示器(2).
它完成了对display(p->left)(为"1")的调用,因此执行下一个语句,即cout << 2.