C语言动态查找表之二叉排序树

偏执的太偏执、 2022-02-09 09:43 226阅读 0赞

**目录**

1.静态查找表与动态查找表的比较

2.二叉排序树（Binary Sort Tree）

2.1二叉排序树的定义

2.2二叉排序树的查找算法

2.3二叉排序树的插入算法

2.4二叉排序树的构造算法

2.5二叉排序树的删除算法

3.源代码示例

--------------------

## 1 静态查找表与动态查找表的比较 ##

静态查找表一旦生成，所含记录在查找过程中一般是固定不变的。动态查找表不仅可以实现对数据的查找，在表生成后还经常进行插入和删除操作，所以动态查找表是一直在变化的。

## 2 二叉排序树（Binary Sort Tree） ##

### 2.1 二叉排序树的定义 ###

二叉排序树或者是一棵空二叉树，或者是具有下列性质的二叉树：

（1）若左子树不空，则左子树上所有节点的关键码（元素）值均小于根节点的关键码值；若右子树不空，则右子树上所有节点的关键码（元素）值均大于根节点的关键码值；

（2）左右子树也都是二叉排序树

### 2.2 二叉排序树的查找算法 ###

（1）若要查找的树为空，则查找失败

（2）若树非空，则将给定值 x 与树根节点的关键码值比较

1.若 x 等于树根节点的关键码值，查找成功，结束查找；

2.若 x 小于树根节点的关键码值，在树的左子树继续查找；

3.若 x 大于树根节点的关键码值，在树的右子树继续查找

### 2.3 二叉排序树的插入算法 ###

设待插入节点关键码值为 x ：

（1）先在树中查找值为 x 的节点，若查找成功，说明节点已存在，无需插入；

（2）若查找失败，说明节点不存在，则将其插入到树中

因此，新插入节点一定是作为叶子节点插入的。

### 2.4 二叉排序树的构造算法 ###

构造二叉排序树的过程，就是从空二叉树开始，逐个向树中插入节点的过程。

设记录的关键码序列为：63,90,70,55,67,42,98,83,10,45,58

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI1MDMwMg_size_16_color_FFFFFF_t_70][]

### 2.5 二叉排序树的删除算法 ###

设待删除节点为 \*p（p为待删除节点的指针），其双亲节点为 \*f：

（1）\*p 为叶子节点：将 \*f 的相应指针域置空即可

![20200308152704180.png][]

（2）\*p 有右子树或左子树：用 p->rchild / p->lchild 替换 p 即可

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI1MDMwMg_size_16_color_FFFFFF_t_70 1][]

（3）\*p 既有左子树又有右子树：用该树中序遍历序列中的直接前驱（后继）节点值取代被删除节点值即可。具体步骤如下：

1.顺着 \*p 的左孩子的右链域一直找下去，直到没有右孩子为止。\*p 的直接前驱节点肯定没有右孩子

2.用 \*p 前驱节点的关键码值取代 \*p 的关键码值

3.删除 \*p 前驱节点

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI1MDMwMg_size_16_color_FFFFFF_t_70 2][]

## 3.源代码示例 ##

#include <stdio.h>
    #include <stdlib.h>
    
    typedef int KeyType; // 定义节点关键码的类型为整型
    typedef struct node  // 二叉排序树的结构体
    {
        KeyType key;                  // 树节点的关键码
        struct node *lchild, *rchild; // 左右孩子指针
    } node, *BiSortTree;
    
    void CreateBST(BiSortTree *T);            // 构造二叉排序树
    void InsertBST(BiSortTree *T, KeyType x); // 向T中插入关键码值为 x 的节点
    void DeleteBST(BiSortTree *T, KeyType x); // 删除T中关键码值为 x 的节点
    void TraverseBST(BiSortTree T);           // 中序遍历BST
    int SearchBST(BiSortTree T, KeyType x, BiSortTree *p, BiSortTree *f);
    int SearchBST_Recursive(BiSortTree T, KeyType x, BiSortTree *p, BiSortTree *f);
    // 在T中查找关键码值为 x 的节点，若找到则返回1，p指向该节点，f指向该节点双亲节点；否则返回0
    
    int main(void)
    {
        BiSortTree T, p, f;
    
        p = f = NULL;
        CreateBST(&T);
        printf("遍历：");
        TraverseBST(T);
        printf("\n");
    
        printf("查找 98 ：");
        int flag = SearchBST(T, 98, &p, &f);
        if (flag)
            printf("查找成功！\n");
        else
            printf("查找失败！\n");
    
        printf("递归查找 100 ：");
        flag = SearchBST_Recursive(T, 100, &p, &f);
        if (flag)
            printf("查找成功！\n");
        else
            printf("查找失败！\n");
    
        printf("插入 77 ：");
        InsertBST(&T, 77);
        TraverseBST(T);
        printf("\n");
    
        printf("删除 77 ：");
        DeleteBST(&T, 77);
        TraverseBST(T);
        printf("\n");
    
        return 0;
    }
    
    void CreateBST(BiSortTree *T) // 构造二叉排序树
    {
        KeyType x;
    
        printf("请输入若干整数构建BST，以 -1 结束：");
    
        *T = NULL;
        scanf("%d", &x);
        while (x != -1) {
            InsertBST(T, x);
            scanf("%d", &x);
        }
    }
    // 在T中查找关键码值为 x 的节点，若找到则返回1，*p指向该节点，*f为*p双亲节点；否则返回0
    int SearchBST(BiSortTree T, KeyType x, BiSortTree *p, BiSortTree *f)
    {
        *p = T;
        while (*p) {
            // 查找成功
            if ((*p)->key == x)
                return 1;
            else {
                // 在左子树继续查找
                if (x < (*p)->key) {
                    *f = *p;
                    *p = (*p)->lchild;
                }
                // 在右子树继续查找
                else {
                    *f = *p;
                    *p = (*p)->rchild;
                }
            }
        }
    
        return 0; // 查找失败
    }
    int SearchBST_Recursive(BiSortTree T, KeyType x, BiSortTree *p, BiSortTree *f)
    {
        // 树空时，查找失败
        if (!T)
            return 0;
        // 查找成功
        else if (x == T->key) {
            *p = T;
            return 1;
        }
        // 在左子树继续查找
        else if (x < T->key)
            return SearchBST_Recursive(T->lchild, x, p, &T);
        // 在右子树继续查找
        else
            return SearchBST_Recursive(T->lchild, x, p, &T);
    }
    void InsertBST(BiSortTree *T, KeyType x) // 向T中插入关键码值为 x 的节点
    {
        BiSortTree p, f, s;
    
        f = p = NULL;
        // 若树中不存在关键码值为 x 的节点，则插入
        if (!SearchBST(*T, x, &p, &f)) {
            s = (node *)malloc(sizeof(node)); // 申请节点并赋值
            s->key = x;
            s->lchild = NULL;
            s->rchild = NULL;
    
            // 若树为空，将新申请的节点作为根节点
            if (!*T)
                *T = s;
            else {
                // 插入节点为f的左孩子
                if (x < f->key)
                    f->lchild = s;
                // 插入节点为f的右孩子
                else
                    f->rchild = s;
            }
        }
    }
    void DeleteBST(BiSortTree *T, KeyType x) // 删除T中关键码值为 x 的节点
    {
        BiSortTree p, f, s, s_parent;
        /**
         * p：要删除的节点
         * f：p的双亲结点
         * s：p的中序前驱节点
         * s_parent：s的双亲结点
         */
    
        p = f = NULL;
        // 若树中存在关键码值为 x 的节点，则删除
        if (SearchBST(*T, x, &p, &f)) {
            // 被删除节点无左右孩子
            if (!p->lchild && !p->rchild) {
                // 若删除的是根节点
                if (p == *T) {
                    *T = NULL;
                    free(p);
                }
                // 若删除的不是根节点
                else {
                    if (p->key < f->key)
                        f->lchild = NULL;
                    else
                        f->rchild = NULL;
                    free(p);
                }
            }
            // 被删除节点有右孩子无左孩子
            else if (!p->lchild && p->rchild) {
                // 若删除的是根节点
                if (p == *T) {
                    *T = p->rchild;
                    free(p);
                }
                // 若删除的不是根节点
                else {
                    if (p->key < f->key)
                        f->lchild = p->rchild;
                    else
                        f->rchild = p->rchild;
                    free(p);
                }
            }
            // 被删除节点有左孩子无右孩子
            else if (p->lchild && !p->rchild) {
                // 若删除的是根节点
                if (p == *T) {
                    *T = p->lchild;
                    free(p);
                }
                // 若删除的不是根节点
                else {
                    if (p->key < f->key)
                        f->lchild = p->lchild;
                    else
                        f->rchild = p->lchild;
                    free(p);
                }
            }
            // 被删除节点有左右孩子
            else {
                s_parent = p;
                s = p->lchild;
                while (s->rchild) // 查找被删除节点中序前驱节点
                {
                    s_parent = s;
                    s = s->rchild;
                }
                p->key = s->key;
                if (s_parent == p)
                    s_parent->lchild = s->lchild;
                else
                    s_parent->rchild = s->lchild;
                free(s);
            }
        }
    }
    void TraverseBST(BiSortTree T) // 中序遍历BST
    {
        if (T) {
            TraverseBST(T->lchild);
            printf("%d, ", T->key);
            TraverseBST(T->rchild);
        }
    }

![20190502200343865.jpg][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI1MDMwMg_size_16_color_FFFFFF_t_70]: /images/20220206/d88761cac18f47d0a54d09b82a9378ba.png
[20200308152704180.png]: /images/20220206/d27b3f6046f64e66a7e21e722b7288e9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI1MDMwMg_size_16_color_FFFFFF_t_70 1]: /images/20220206/1eb40427431e4022b59aafcdbe0247cc.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI1MDMwMg_size_16_color_FFFFFF_t_70 2]: /images/20220206/3cb6fd2ddc1e42c4bc6b44500b4eea5e.png
[20190502200343865.jpg]: /images/20220206/ab6aa54eb6c14d17bfa298458c1fb4ce.png