c++ - 二叉查找树递归显示函数，不知道是怎么实现的？

Question

我有一个 BST，我在网上找到了这个函数，它以正确的顺序打印它，但我不明白如何。

void display()
{
    inOrder(root);
}
void inOrder(treeNode* n)
{
   classA foo;
   if (n != NULL)
   {
        inOrder(n->left);
        foo = *n->item;
        cout << foo << endl << endl;
        inOrder(n->right);
    }
 }

我将每个节点的左侧和右侧初始化为 NULL。为什么if语句在一个NULL指针传入后继续执行，从哪里继续执行？

Answer 1

假设您有以下 BST:

当使用此 BST 调用 inOrder 时，

递归级别 0

n 指向 8。所以你输入 block :

    inOrder(n->left);
    foo = *n->item;
    cout << foo << endl << endl;
    inOrder(n->right);

inOrder 使用 n->left 作为参数调用，即节点 3。

递归级别 1

n 指向 3。所以你输入相同的代码块。

inOrder 使用 n->left 作为参数调用，即节点 1。

递归级别 2

n 指向 1。所以你输入相同的代码块。

inOrder 使用 n->left 作为参数调用，参数为 NULL。

递归级别 3

n 指向 NULL。所以你不要输入上面的代码块。您只需从函数返回即可。现在回到上一个递归级别的下一个语句。

递归级别 2

执行以下几行:

    foo = *n->item;
    cout << foo << endl << endl;
    inOrder(n->right);

你打印1。然后，使用 n->right 作为参数调用 inOrder，参数为 NULL。

递归级别 3

n 指向 NULL。所以你不要输入上面的代码块。您只需从函数返回即可。现在回到上一个递归级别的下一个语句。

递归级别 2

没有更多行要执行。该函数只是返回到先前的递归级别。

递归级别 1

执行以下几行:

    foo = *n->item;
    cout << foo << endl << endl;
    inOrder(n->right);

你打印3。然后，使用 n->right 作为参数调用 inOrder，即节点 6。

你现在可以一路跟着这个一步一步来了。最终结果是您最终将按以下顺序打印数字。

1
3
4
6
7
8
10
13
14