Binary Search Tree insert()方法问题

Question

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 ;的值会怎么传递？

Answer 1

liuyubobobo 2017-05-17 00:41:54

对于编写一个递归函数来说，要保证两部分内容：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）中有大量章节讲解递归，有兴趣的话也可以参考：）

• wang_liu #1

  第二个return就对应了递归运行过程  ，  返回的是 node 。  老师，能不能使用 两次递归调用 具体解释一下第二个返回 node  的 过程呢？？？

• liuyubobobo 回复 wang_liu #2

  我尝试描述了一个过程在下面的回答中，看看你能不能理解：）

• wang_liu 回复 liuyubobobo #3

  嗯呢，，谢谢老师，理解了呢

Answer 2

liuyubobobo 2017-06-01 00:20:37

比如要向下面的树中插入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）中有大量章节讲解递归，有兴趣的话也可以参考：）

• 提问者 极速星宇 #1

  感谢老师

Answer 3

夏木清水 2017-05-16 09:19:41

1. 如果node==NULL，就直接return出去，下面的代码就不会运行了；如果node非空，就运行下面的代码，通过第二个return结束函数；

2. 因为要插入新元素，会改变相应二叉树的结构；所以递归中的每一层return node的本质目的是保证，递归的最后一层可以链接到new Node,同时再把这个node层层向上传递到根部；这样的最终结果就是，传入一个初始的root节点指针，返回了一根更新后的root节点指针；

• liuyubobobo #1

  非常感谢你的回答：）