二分搜索树的一个小问题，有点小小困惑

Question

波波老师，在二分搜索树的添加和删除元素的操作中，最终返回的node，也就是新的二分搜索树的根，其实还是原来的根（root），是吗？（排除删掉root元素的情况，并假设添加操作时，root不为空）

Answer 1

liuyubobobo 2019-04-09 23:06:41

这个node是我们传进去的参数，不是我们在类里的成员变量root。

注意，我们的递归函数都是在处理以node为根节点的二分搜索树，而不是以root为根节点的整棵二分搜索树。而node是我们传进去的参数。所以，你会看到，已添加为例，有如果node == null，返回一个new Node。因为对一个空树添加一个新节点，结果就是一个新节点。但此时root不代表为空。我们的添加过程递归向下，参数是不断变化的，node也是不断变换的，最终，一定会找到node==null的时候，也就是递归到底的时候。

注意，我们递归调用的参数变化：（蓝线）

在体会一下这个递归的过程，尤其是结合我们在讲链表时所说的，递归的宏观语义和微观执行两个角度，看能不能理解这个递归的运行？

加油！：）

• 提问者 YupG #1

  有点感觉了，我再好好感悟一下，谢谢波波老师！