第 3 节 二分搜索树的第 1 个操作：向二分搜索树中插入新的结点

• 我们利用了二分搜索树的递归的性质来完成 insert 函数的编写。
• 应该特别注意的是：该递归的方法返回了插入了新的结点的二分搜索树的根，这一点保证了插入新结点以后，它能够被它的父结点的 left 或 right 指向，这一点要认真体会：

1、node.left = insert(node.left, key, value);

2、node.right = insert(node.right, key, value);

注意：在递归的实现中，应该把 insert 的结果返回给 node.left 和 node.right ，刚开始接触这个算法的时候，觉得很难理解，写多了就觉得比较自然了。

public void insert(int key, int value) {
    insert(root, key, value);
}

// 向一棵二分搜索树的根结点插入 key 和 value，看看放在左边还是放在右边，然后把插入以后形成的树的根结点返回。
// 注意这里的递归调用实现，初学的时候，不是很好理解。可以尝试从最最简单的情况开始分析。
private Node insert(Node node, int key, int value) {
    if (node == null) {
        count++;
        return new Node(key, value);
    }
    if (key == node.key) {
        // 如果 key 值存在，直接覆盖就好了，即更新
        node.value = value;
    }
    if (key < node.key) {
        // 递归调用结束以后，要把根结点返回回去
        // 因为很可能，node.left 是空，要让新创建的结点接到原来的根，就得执行这步操作
        node.left = insert(node.left, key, value);
    } else {
        // 递归调用结束以后，要把根结点返回回去
        node.right = insert(node.right, key, value);
    }
    return node;
}

#

---

作者：liweiwei1419 链接：https://suanfa8.com/binary-search-tree/insert 来源：算法吧 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。