老师好，关于BST的一个小问题

来源：6-3 向二分搜索树中添加元素

1Kasshole

2018-12-21

二分搜索树课程中老师的add代码是这样写的（我弄成了c++代码）:

Node* add(Node *node, int e){
    if(node == nullptr){
        node = new Node(e);
        return node;
    }
    if(node->data > e) {
        node->left = add(node->left, e);
    }
    else {
        node->right = add(node->right, e);
    }
    return node;
}

很直观，容易看懂

但是我徒手撸的时候，写成了这样:

void add(Node *node, int e){
    if(node == nullptr){
        node = new Node(e);
        return;
    }
    if(node->data == e) return;
    if(node->data > e) add(node->left, e);
    else add(node->right, e);
}

如果这么写程序会崩溃，我想了很久，也在纸上画了画，就是想不出来哪里出了问题。请问和您写的带返回值的add，我的版本有什么漏洞？

写回答

2回答

liuyubobobo

2018-12-21

已采纳

为什么要return，其中的原因，和课程中介绍的递归删除算法（5-3至5-5），我们的remove要返回节点，道理是一样的。

设想，如果没有return，你的添加逻辑只在递归终止操作的node = new Node(e) 这句话中。而node只是这个函数中的一个局部变量而已。当这个函数执行完毕，这个局部变量就被释放了，而他所指向的空间也就丢失了。而return回去，让他赋值给上一层的node.left或者node.right，才可以真正的吧这个new出来的节点挂接在整个BST上。

对此，也可以参考这个问答：http://coding.imooc.com/learn/questiondetail/88146.html 虽然探讨的是链表，但道理是一样的。当然，也建议你写一个链表的递归版本，再仔细感受一下这个差异。

加油！：）

1Kasshole

老师的回答非常精确！

2018-12-21

共1条回复