Binary Search Tree insert()方法问题
来源：5-3 二分搜索树的节点插入
极速星宇
2017-05-15
Node* insert(Node *node, Key key, Value value){
if( node == NULL ){
count ++;
return new Node(key, value);
}
if( key == node->key )
node->value = value;
else if( key < node->key )
node->left = insert( node->left , key, value);
else // key > node->key
node->right = insert( node->right, key, value);
return node;
}为什么有两个return ？return node ;的值会怎么传递？
3回答
-
对于编写一个递归函数来说，要保证两部分内容：1）递归终止条件；2）递归运行的过程
比如最简单的斐波那契数列：
int fib(int n){ // 递归终止条件 if(n==0 || n==1) return n; // 递归运行过程 return fib(n-1) + fib(n-2); }在这个代码中，第一个return就是递归终止过程，当要插入一个新节点的树是一棵空树时，直接返回一个new出来的新节点就好了，这个新节点就是插入节点后树的根；第二个return就对应了递归运行过程，当要插入一个新节点的树不是空树时，则使用递归的过程在这棵树中插入新的节点，之后将这棵树的根，依然是插入节点前的这棵树的根node返回就好。
如果对这个过程觉得太抽象，不妨使用debug的方式一步一步跟踪整个程序，从空到向树中插入5-10个节点，看看整个程序是怎样一句一句的执行，数据是怎样做的改变，最终完成的整个树的建立过程。虽然会花些时间，但是是值得的，对于深入理解递归过程是有好处的哦：）
另外，我的另外一门课程《算法面试》（http://coding.imooc.com/class/82.html）中有大量章节讲解递归，有兴趣的话也可以参考：）
032017-06-01 -
liuyubobobo
2017-06-01
比如要向下面的树中插入3这个节点
4 / \ 2 6
首先，运行insert(node=4, key=3)，3和根节点4作比较，因为3比4小，所以3要插入到4的左子树中，也就是递归调用将3插入到以2为根节点的二叉树中；
进入insert(node=2 key=3)，3和2作比较，因为3比2大，所以3要插入到2的右子树中，也就是递归调用将3插入到以NULL为根节点的二叉树中（因为2的右子树为空）；
进入insert(node=NULL key=3)，现在3要插入的二叉树根节点为空，所以使用第一个返回，直接返回了一个新的node节点3；
这次返回会返回到insert(node=2 key=3)，也就是以2为根节点的右子树上已经插入了节点3，之后继续运行insert(node=2 key=3)的后续代码，也就是最后会进入第二个返回node，直接将2这个根节点返回了；
这次返回会返回到insert(node=4, key=3)，也就是以4为根节点的左子树上已经插入了节点3，之后继续运行insert(node=4 key=3)的后续代码，也就是最后会进入第二个返回node，直接将4这个根节点返回了；
4这个根节点是整棵二叉树的根，递归调用到此结束了。我们在这个二叉树中插入了一个新的节点3。
这里的重点是：递归调用是需要返回的！递归调用和普通的函数调用没有差别。普通的函数调用，A调用B，当B执行结束后，A继续执行调用B以后的后续代码。递归调用时同样的！只不过是A调用自己A，调用自己的A这部分代码结束以后，上面的A要继续执行完自己的代码。
依然是：如果对这个过程觉得太抽象，不妨使用debug的方式一步一步跟踪整个程序，从空到向树中插入5-10个节点，看看整个程序是怎样一句一句的执行，数据是怎样做的改变，最终完成的整个树的建立过程。虽然会花些时间，但是是值得的，对于深入理解递归过程是有好处的哦：）
另外，我的另外一门课程《算法面试》（http://coding.imooc.com/class/82.html）中有大量章节讲解递归，有兴趣的话也可以参考：）
512017-06-01 -
夏木清水
2017-05-16
如果node==NULL，就直接return出去，下面的代码就不会运行了；如果node非空，就运行下面的代码，通过第二个return结束函数；
因为要插入新元素，会改变相应二叉树的结构；所以递归中的每一层return node的本质目的是保证，递归的最后一层可以链接到new Node,同时再把这个node层层向上传递到根部；这样的最终结果就是，传入一个初始的root节点指针，返回了一根更新后的root节点指针；
012017-05-17
相似问题