在private insert... 中，当key == node.key时，返回当前node，对根节点的疑问。

Question

刘老师，你好！在递归函数中，当key == node.key时，直接return 当前node，也就意味着，根节点root = 返回的这个node。这样岂不是改变了全局的根节点了？

Answer 1

liuyubobobo 2018-03-21 08:21:23

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两个小时就够了，比对着代码生想一下午有用的多。

加油！：）

• 提问者 LeonSun #1

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