二叉搜索树

二叉搜索树（Binary Search Tree）

二叉搜索树，也称二叉查找树或二叉排序树，可以是一棵空树。

如果不为空树，那么二叉搜索树满足以下性质：

非空左子树的所有结点的值小于其根结点的值。
非空右子树的所有结点的值大于其根结点的值。
左、右子树均是二叉搜索树。

查找结点

在二叉搜索树中查找一个元素从根结点开始，如果树为空，返回NULL。

如果树不为空，则将根结点的值和被查找的key值进行比较：

如果key值小于根结点的值，只需在左子树中继续查找。
如果key值大于根结点的值，只需在右子树中继续查找。
如果key值与根结点的值相等，查找成功。

查找结点（迭代）

bool binary_search_tree_contains(binary_search_tree_t *tree, T elem) {
    if (tree == NULL) {
        return false;
    }

    node_t *node = tree->root;
    while (node != NULL) {
        if (elem < node->data) {
            node = node->left;
        } else if (elem > node->data) {
            node = node->right;
        } else {
            return true;
        }
    }
    return false;
}

为避免递归调用的额外开销，可将尾递归（在函数最后才使用递归返回）的函数改为迭代函数。

PRO EXCLUSIVE探索不止于此

解锁完整互动实验、进阶解析与精选参考答案。

尊享 Pro 权益

查找最小值和最大值

二叉搜索树中，最小值一定在树的最左分枝上没有左孩子的结点上，最大值一定在树的最右分枝上没有右孩子的结点上。

查找最小值（递归）

static node_t *binary_search_tree_min(node_t *node) {
    if (node == NULL || node->left == NULL) {
        return node;
    }
    return binary_search_tree_min(node->left);
}

查找最大值（迭代）

static node_t *binary_search_tree_max(node_t *node) {
    if (node == NULL) {
        return NULL;
    }

    while (node->right != NULL) {
        node = node->right;
    }
    return node;
}

插入结点

在二叉搜索树中插入结点与查找的算法相似，需要找到插入的位置并将新结点插入。

插入结点

static node_t *__binary_search_tree_add(node_t *node, T elem) {
    if (node == NULL) {
        return binary_search_tree_node_create(elem);
    }

    if (elem < node->data) {
        node->left = __binary_search_tree_add(node->left, elem);
    } else if (elem > node->data) {
        node->right = __binary_search_tree_add(node->right, elem);
    }
    return node;
}

binary_search_tree_t *binary_search_tree_add(binary_search_tree_t *tree, T elem) {
    if (tree == NULL) {
        return NULL;
    }

    if (binary_search_tree_contains(tree, elem)) {
        return tree;
    }
    tree->root = __binary_search_tree_add(tree->root, elem);
    tree->size++;
    return tree;
}

PRO EXCLUSIVE探索不止于此

解锁完整互动实验、进阶解析与精选参考答案。

尊享 Pro 权益

删除结点

删除叶子结点时，父结点的对应指针改为NULL；只有一个孩子时，让父结点直接指向这个孩子；有两个孩子时，用右子树的最小值替换待删结点的数据，再删除这个后继结点。删除根结点时也要更新root。

PRO EXCLUSIVE探索不止于此

解锁完整互动实验、进阶解析与精选参考答案。

尊享 Pro 权益

题目

根为10、左孩子为5、右孩子为15。把12作为5的右孩子，仍是搜索树吗？

题目

删除一个有两个孩子的结点时，复制右子树最小值后还必须做什么？

从图中的搜索树开始：写出查找10的比较路径；插入5，画出新指针；然后删除根8，按右子树最小值替换的方法画出每次指针变化与最终树。最后写出中序序列。

二叉搜索树