1回答

liuyubobobo

2017-11-26

已采纳

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

注意我们对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

加油！

2

2

慕UI5584032

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

2017-11-26

共2条回复