什么是二叉查找树

二叉查找树本质就是通过二分搜索的方法来快速查找

二叉查找树也叫二叉搜索树或是二叉排序树，它具有一定的规则：

  • 左子树中所有结点的值，均小于其根结点的值。
  • 右子树中所有结点的值，均大于其根结点的值。
  • 二叉搜索树的子树也是二叉搜索树。
    一棵二叉搜索树长这样：
    二叉查找树示意图
    查找值为15的结点：
  1. 从根结点18开始，因为15小于18，所以从左边开始找。
  2. 接着来到10，发现10比15小，所以继续往右边走。
  3. 来到15，成功找到。
    实际上，我们在对普通二叉树进行搜索时，可能需要挨个进行查看比较，而有了二叉搜索树，查找效率就大大提升了，它就像我们前面的二分搜索那样。

    因为二叉搜索树要求比较严格，所以我们在插入结点时需要遵循一些规律，这里我们来尝试编写一下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <stdio.h>
#include <stdlib.h>

typedef int E;

typedef struct TreeNode {
    E element;
    struct TreeNode * left;
    struct TreeNode * right;
} * Node;

Node createNode(E element){
    Node node = malloc(sizeof(struct TreeNode));
    node->left = node->right = NULL;
    node->element = element;
    return node;
}

int main() {
    
}

二叉查找树的操作

插入操作

我们就以上面这颗二叉查找树为例，现在我们想要依次插入这些结点，我们需要编写一个特殊的插入操作，这里需要注意一下，二叉查找树不能插入重复元素，如果出现重复直接忽略：

1
2
3
4
5
6
7
8
9
10
11
Node insert(Node root, E element){
    if(root){
        if(root->element > element)    //如果插入结点值小于当前结点，那么说明应该放到左边去
            root->left = insert(root->left, element);
        else if(root->element < element)    //如果插入结点值大于当前结点，那么说明应该放到右边去
            root->right = insert(root->right, element);
    } else {   //当结点为空时，说明已经找到插入的位置了，创建对应结点
        root = createNode(element);
    }
    return root;   //返回当前结点
}

上诉代码的主要图形逻辑是，根据插入逻辑找到一个空节点，然后插入元素。
这样我们就可以通过不断插入创建一棵二叉查找树了：

1
2
3
4
5
6
7
8
9
10
11
void inOrder(Node root){
    if(root == NULL) return;
    inOrder(root->left);
    printf("%d ", root->element);
    inOrder(root->right);
}

int main() {
    Node root = insert(NULL, 18);   //插入后，得到根结点
    inOrder(root);   //用中序遍历查看一下结果
} 
1
2
3
4
5
6
int main() {
    Node root = insert(NULL, 18);   //插入后，得到根结点
    insert(root, 10);
    insert(root, 20);
    inOrder(root);
}

可以看到中序结果为：
结果图

搜索操作

那么插入写好之后，我们怎么找到对应的结点呢？实际上也是按照规律来就行了：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
Node find(Node root, E target){
    while (root) {
        if(root->element > target)    //如果要找的值比当前结点小，说明肯定在左边
            root = root->left;
        else if(root->element < target)   //如果要找的值比当前结点大，说明肯定在右边
            root = root->right;
        else
            return root;   //等于的话，说明找到了，就直接返回
    }
    return NULL;   //都找到底了还没有，那就是真没有了
}

Node findMax(Node root){   //查找最大值就更简单了，最右边的一定是最大的
    while (root && root->right) 
        root = root->right;
    return root;
}

删除操作

最后我们来看看二叉查找树的删除操作，这个操作就比较麻烦了，因为可能会出现下面的几种情况：

  1. 要删除的结点是叶子结点。
  2. 要删除的结点是只有一个孩子结点。
  3. 要删除的结点有两个孩子结点。
    首先我们来看第一种情况，这种情况实际上最好办，直接删除就完事了：
    示意图
    而第二种情况，就有点麻烦了，因为有一个孩子，当移除后，需要将孩子结点连接上去：
    示意图
    可以看到在调整后，依然满足二叉查找树的性质。最后是最麻烦的有两个孩子的情况，这种该怎么办呢？前面只有一个孩子直接上位就完事，但是现在两个孩子，到底谁上位呢？这就不好办了，为了保持二叉查找树的性质，现在有两种选择：
  • 选取其左子树中最大结点上位
  • 选择其右子树中最小结点上位

这里我们以第一种方式为例：
示意图
现在我们已经分析完三种情况了，那么我们就来编写一下代码吧：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
Node delete(Node root, E target){
    if(root == NULL) return NULL;   //都走到底了还是没有找到要删除的结点，说明没有，直接返回空
    if(root->element > target)   //这里的判断跟之前插入是一样的，继续往后找就完事，直到找到为止
        root->left = delete(root->left, target);
    else if(root->element < target)
        root->right = delete(root->right, target);
    else {   //这种情况就是找到了
        if(root->left && root->right) {   //先处理最麻烦的左右孩子都有的情况
            Node max = findMax(root->left);  //寻找左子树中最大的元素
            root->element = max->element;  //找到后将值替换
            root->left = delete(root->left, root->element);  //替换好后，以同样的方式去删除那个替换上来的结点
        } else {   //其他两种情况可以一起处理，只需要删除这个结点就行，然后将root指定为其中一个孩子，最后返回就完事
            Node tmp = root;
            if(root->right) {   //不是左边就是右边
                root = root->right;
            } else {
                root = root->left;
            }
            free(tmp);   //开删
        }
    }
    return root;   //返回最终的结点
}

说些什么吧！

twikoo