数据结构与算法——二叉排序树详解以及代码实现

冷不防 2022-05-26 05:24 99阅读 0赞

# 二叉排序树介绍 #

我们知道二叉树，每个结点最多有2棵子树，被称为左子树 和 右子树。  
二叉排序树，显然也是一颗二叉树，它有更突出的特性在**数据域上呈现排序的特性**。  
在**二叉排序树**中，***每个树的左子树的数据域均小于它的根结点值，每个树的右子树的数据域均大于它的根结点值，每棵树的左、右子树 均为二叉排序树***。从它特性很容易得到，**对二叉排序树 进行中序遍历一定是升序序列**。

# 代码实现思路 #

二叉排序树，相关算法主要有：

*  创建二叉排序树
 *  结点的查询
 *  结点的插入
 *  结点的删除

查询？很好实现吧，递归结点查询key的值是否相等 ，不相等就递归查询呗，递归出口 node==NULL，**查询到结点通过传出参数返回，没有查询到返回离key值最近的结点**。

插入？根据二叉排序的特性进行插入呗，可以**调用查询接口**，如果二叉排序树没有该结点，则允许插入，**将插入结点挂到返回的结点上呗**。

删除？删除就要分情况了，第3种情况有点绕，初学者要好好结合代码理解。

1.  待删除结点，**只有左子树，可以直接用其左子树替换删除结点**，因为它的左子树上的所以结点都比它值小，仍然符合二叉排序的特性
2.  待删除结点，**只有右子树，同理可以直接使用其右子树替换删除结点**，因为它的右子树上
3.  待删除结点，**左右子树都存在，如何是好呢**？因为我们删除结点之后，仍然要满足二叉排序树的特性，每个树结点的左子树比都比它小，右子树都比它大！现在就要想到前面提到的特性了，**二叉排排序树的中序遍历一定是升序序列，删除结点的数据域可以使用 中序遍历的前驱结点 或者后驱结点数据域替换**？有木有，**注意这里只替换数据域，因为原来的逻辑关系还要保留**，**所以不能释放删除结点的内存，而释放的是替换的前驱结点或者后驱结点**！

创建二叉排序树？利用插入算法直接实现呗，刚开始为空二叉树，利用插入算法，可以生成二叉排序树。

# 实现代码 #

#define _CRT_SECURE_NO_WARNINGS
    #include <stdio.h>
    #include <stdlib.h>
    
    //二叉树节点
    typedef struct BiNode 
    {
        int data;
        struct BiNode* lchild, *rchild;
    }BiNode,*BiTree;
    
    typedef enum bool{ false,true }bool;
    
    
    //二叉树 中序遍历
    void TraverseMid(BiTree root)
    {
        if (root == NULL)
        {
            return;
        }
        TraverseMid(root->lchild);
        printf("%d ", root->data);
        TraverseMid(root->rchild);
    }
    /* 二叉排序树的查询 tree 查找的二叉树根结点 parent tree的双亲结点 node 传出参数，查找到的结点指针，没找到为最接近key的结点的指针 key 查找关键字 */
    bool SearchBST(BiTree root,BiTree parent,BiNode** node,int key )
    {
        if (root == NULL)               //已经找到头了，还没有找到，返回最接近key的结点的指针
        {
            *node = parent;
            return false;
        }
        else
        {
            if (key < root->data)       //key 比root 小，搜索root的左子树
            {
                return SearchBST(root->lchild, root, node, key);
            }
            else if(key > root->data)   //key 比root 大，搜索root的右子树
            {
                return SearchBST(root->rchild, root, node, key);
            }
            else                        //key == root->data，找到key 返回
            {
                *node = root;
                return true;
            }
        }
    }
    //插入
    bool InsertBST(BiTree root, int data)
    {
        BiNode* node = NULL;
        if (SearchBST(root, NULL, &node, data)) //在树上有相同的结点，不允许插入
        {
            return false;
        }
        else
        {
            BiNode * newNode = (BiNode*)malloc(sizeof(BiNode));
            newNode->lchild = newNode->rchild = NULL;
            newNode->data = data;
            if (data < node->data)
            {
                node->lchild = newNode;
            }
            else
            {
                node->rchild = newNode;
            }
            return true;
        }
    }
    //具体删除结点动作
    bool DeleteNode(BiTree* node)
    {
        BiTree tmp, pre, pre_parent;
        if ((*node)->lchild == NULL)                    //删除结点的左子树为NULL，将右子树顶替，释放删除结点内存
        {
            tmp = *node;
            *node = (*node)->rchild;                                
            free(tmp);
        }
        else if ((*node)->rchild == NULL)               //删除结点的右子树为NULL，将左子树顶替，释放删除结点内存
        {
            tmp = *node;
            *node = (*node)->lchild;
            free(tmp);
        }
        else                                            //删除结点的左右子树均不为空，删除结点数据换成其前驱或者后继的数据 结点并不释放，这里换成前驱
        {
            pre_parent = *node;
            pre = pre_parent->lchild;                   //pre 删除结点的中序遍历前驱结点
            while (pre->rchild != NULL)                 //while循环 寻找左子树中最大结点
            {
                pre_parent = pre;
                pre = pre->rchild;
            }
            if (pre == (*node)->lchild)
            {
                (*node)->data = pre->data;
                (*node)->lchild = pre->lchild;
            }
            else
            {
                (*node)->data = pre->data;
                pre_parent->rchild = pre->lchild;
            }
            free(pre);
        }
        return true;
    }
    //删除
    bool DeleteBST(BiTree *root, int key)
    {
        if (root == NULL)
            return false;
        if (key == (*root)->data)
        {
            return DeleteNode(root);
        }
        else if (key < (*root)->data)
        {
            return DeleteBST(&(*root)->lchild, key);
        }
        else
        {
            return DeleteBST(&(*root)->rchild, key);
        }
    }
    //利用二叉树插入操作，创建二叉排序树
    void CreateBST(BiTree *tree)
    {
        int num;
        printf("请输入根节点数据:");
        scanf("%d", &num);
        *tree = malloc(sizeof(BiNode));
        (*tree)->data = num;
        (*tree)->lchild = (*tree)->rchild = NULL;
        while (1)
        {
            printf("请输入结点数据(-1结束):");
            scanf("%d", &num);
            if (num == -1)
            {
                break;
            }
            InsertBST(*tree, num);
        }
    }
    
    int main(int argc, char *argv[])
    {
        BiTree binarySortTree;//二叉排序树
        CreateBST(&binarySortTree);
        int menu, key,ret;
        BiNode* node;
        while (1)
        {
            printf("----菜单----------------\n");
            printf("----1.中序遍历二叉排序树\n");
            printf("----2.查找结点\n");
            printf("----3.插入结点\n");
            printf("----4.删除结点\n");
            printf("----5.退出\n");
            scanf("%d", &menu);
            switch (menu)
            {
            case 1:
                TraverseMid(binarySortTree);
                printf("\n");
                break;
            case 2:
                printf("请输入key:");
                scanf("%d", &key);
                ret = SearchBST(binarySortTree, NULL, &node, key);
                ret == true ? printf("%d存在\n",key) : printf("%d不存在\n", key);
                break;
            case 3:
                printf("请输入插入data:");
                scanf("%d", &key);
                ret = InsertBST(binarySortTree,key);
                ret == true ? printf("%d插入成功\n", key) : printf("%d插入失败\n", key);
                break;
            case 4:
                printf("请输入删除data:");
                scanf("%d", &key);
                ret = DeleteBST(&binarySortTree,key);
                ret == true ? printf("%d删除成功\n", key) : printf("%d删除失败\n", key);
                break;
            case 5:
                exit(0);
            }
        }
        return 0;
    }

# 运行检测 #

![hello][]  
![world][]

[hello]: /images/20220526/2e87cf90df6e45179b44048812c2d50d.png
[world]: /images/20220526/b14ce8eb31b84f1db9619425f1d00bf3.png