1回答

liuyubobobo

2018-03-21

已采纳

insert这个函数的语意是：向以node为根的二分搜索树中插入(key, value)节点；返回的也是这个以node为根节点的二分搜索的根。所以，是的，进入insert，node就是当前二分搜索树的根，只要node ！= NULL，一定返回node自身。（如果node==NULL，就创建一个新节点）

但是，这不意味着改变全局根节点。因为只有第一次调用，这个insert的第一个参数传入的是root（如果此时root->key === key，我们修改这个root->key，就是是我们想要的结果）；但是后续递归调用，insert的第一个参数传的是node->left或者node->right，也就是不断地递归，在一棵更小的子树中完成这个过程。

关于二分搜索树中的递归问题，还还可以参考一下这个问答：

http://coding.imooc.com/learn/questiondetail/27838.html

最最重要的是，如果想不透，建议你使用小数据集，在准备一张白纸，用IDE提供的debug功能，一步一步跟踪一下程序的运行，搞明白在这个递归函数的调用过程中，程序的每一步在执行以后都发生了什么，数据产生了什么样的变化，和自己理解的程序执行的过程有没有出入，出入在哪里。花费一个下午跟踪一下，绝对是值得的，能够帮助你彻底理解代码运行的逻辑。其实通常1-2两个小时就够了，比对着代码生想一下午有用的多。

加油！：）

0

1

LeonSun

好的，非常谢谢刘老师这么详细的回答！

2018-03-21

共1条回复