关于insert()方法的返回值和有关赋值问题

Question

刘老师 我想问下 您说insert()方法返回的值是二叉搜索树的根节点，根节点不是一个嘛,另外返回的值赋值给node的左或右子节点，为什么要这么赋值

Answer 1

liuyubobobo 2017-11-26 07:08:16

对于整棵二叉树而言，只有一个根。但是由于二叉树本身的递归定义的特性，二叉树的每一个节点的左右节点，分别又是两棵二叉树，左右节点分别是对应左右二叉子树的根节点。

注意我们对insert函数的定义：https://github.com/liuyubobobo/Play-with-Algorithms/blob/master/05-Binary-Search-Tree/Course%20Code%20(C%2B%2B)/03-Binary-Search-Tree-Insert/main.cpp

// 向以node为根的二分搜索树中, 插入节点(key, value), 使用递归算法    
// 返回插入新节点后的二分搜索树的根    
Node* insert(Node *node, Key key, Value value)

我们是向“以node为根节点的二叉树”插入节点，返回的是“这个二叉树”的根节点。所以，在public的insert函数中，node这个参数传入的是root，也就是整棵二叉树的根节点：

// 向二分搜索树中插入一个新的(key, value)数据对    
    void insert(Key key, Value value){    
    root = insert(root, key, value);    
}

在具体逻辑上，要注意，我们真正创建一个新的节点的时候，是node为NULL的时候，此时，向一个空树插入一个节点，返回新树的根节点，就是这个节点本身（这个节点本身就是这棵树）。不过此时，我们这个节点并没有挂接到这棵树中，我们需要返回到递归调用的上一层，将这个节点放到递归调用上一层node的左节点或者右节点。这个过程以此类推。其实，这个过程和使用递归的方式在链表中插入一个节点是一致的。只不过对于链表不需要区分左右子树而已，只有一个next指针：）如果对这个递归的返回值理解的不够透彻的话，建议找一些相关资料，从链表的递归方法开始理解：）

关于递归，还可以参考我的这个回答：http://coding.imooc.com/learn/questiondetail/27838.html

加油！

• 提问者 慕UI5584032 #1

  非常感谢！

• 提问者 慕UI5584032 #2

  谢谢波波老师的耐心讲解，辛苦了@|^_^|@