Binary search tree中序遍历递归display函数工作原理及执行路径问询

嘿，我来帮你把这个事儿掰扯明白！首先得指出：你贴的这段代码有个致命的小错误——那个while(p!=NULL)完全是画蛇添足，不仅没用，还会让程序陷入无限递归，根本到不了cout语句！先给你看正确的中序遍历递归函数：

void display(struct tree *p) {
    if(p != NULL) {  // 这里应该用if判断，而不是while循环
        display(p->left);
        cout << p->data << " ";
        display(p->right);
    }
}

递归运行机制到底是啥？ #

递归的核心就是“自己调用自己，直到触发终止条件”，咱们拿一个简单的BST例子来一步步拆解：假设树的结构是这样的：

5
   / \
  3   7
 / \ / \
2  4 6  8

1. 主函数调用display(root)（root是5）：
   因为p!=NULL，先执行display(p->left)——也就是调用display(3)。
2. 进入display(3)：
   同样p!=NULL，先调用display(p->left)——也就是display(2)。
3. 进入display(2)：
   先调用display(p->left)——也就是display(NULL)，这时候p=NULL，函数直接返回（终止条件触发）。
   回到display(2)，现在终于轮到cout<<2了！输出2之后，再调用display(p->right)——也就是display(NULL)，返回，display(2)执行完毕。
4. 回到display(3)：
   左子树的递归已经跑完，现在执行cout<<3，输出3。然后调用display(p->right)——也就是display(4)。
5. 进入display(4)：
   先调用display(p->left)（NULL，返回），然后cout<<4，再调用display(p->right)（NULL，返回），display(4)结束。
6. 回到display(5)：
   左子树递归完成，执行cout<<5，输出5。然后调用display(p->right)——也就是display(7)。
7. 处理右子树display(7)：
   重复和左子树一样的逻辑：先遍历左子树输出6，再输出7，最后遍历右子树输出8。
8. 所有递归完成：最终输出顺序是2 3 4 5 6 7 8，完美符合中序遍历“左子树→根节点→右子树”的规则。

为什么你原来的代码到不了cout？ #

因为你加了while(p!=NULL)，拿display(5)来说，进入函数后，while条件成立，就会一直调用display(p->left)，永远在递归调用左子节点，根本不会往下执行cout那一行，直接陷入无限递归死循环了！把while换成if就一切正常啦。

内容的提问来源于stack exchange，提问作者Pushkar Mahajan