C语言-数据结构-二叉排序树

待我称王封你为后i 2022-05-15 03:05 231阅读 0赞

main.c文件 使用dev C++编辑器

/* 二叉排序树BST: 定义: 二叉查找树. 不是一颗空树, 就是一颗具有下列属性的树 1)左子树非空,则左子树所有结点关键字小于根节点 2)右子树非空,则右子树所有结点关键字大于根节点 3)左右子树本身也是一颗二叉树 二叉排序树是一种递归的数据结构, 可以方便对二叉排序树进行各种递归操作 对二叉排序树进行中序遍历,得到一个递增有序序列 */
    
    #include "stdio.h"
    #include "stdlib.h"
    #include "stdbool.h"
    #include "malloc.h" 
    #include "BinarySortTree.h"
    
    //0-48 A-65
    int main()
    {
        PBinSortTr T = BST_Create();
    
        PBinSortTr P ;
        BST_Search(T,'M',&P); //查找结点,讲M的双亲节点传给P 
    
        BST_Delete(&T, 'E');
        printf("%c\n",T->rChild->data); 
    
    
    
    
        printf("\nhello World!\n");
        return;
    }

二叉排序树头文件文件 BinarySortTree.h

#ifndef __BINARYSORTTREE_
    #define __BINARYSORTTREE_
    #include "stdio.h"
    #include "stdlib.h"
    #include "stdbool.h"
    #include "malloc.h" 
    #define Malloc(node) (PBinSortTr)malloc(sizeof(BinSortTrNod))
    
    /*数据类型重定义*/
    typedef char typeEmpty;
    
    /*二叉排序树*/ 
    typedef struct BinarySortTree{
        typeEmpty data;
        struct BinarySortTree *lChild, *rChild;
    }BinSortTrNod, *PBinSortTr;
    
    
    /*函数声明*/ 
    PBinSortTr BST_Create(void);    //创建二叉排序树 
    bool BST_Insert(PBinSortTr *T, typeEmpty key);  //在T 中插入key 
    PBinSortTr BST_Search(PBinSortTr T, typeEmpty key, PBinSortTr *P);
    bool BST_Delete(PBinSortTr *T, typeEmpty key); //删除T中key的结点 
    void DeleteNode(PBinSortTr *T);  //删除结点*T 
    
    
    /*函数实现*/
    
    /*创建二叉排序树*/ 
    PBinSortTr BST_Create()
    {
        PBinSortTr T = NULL;
        int n = 0;
        typeEmpty str[] = "AEFBDGC";
        while( str[n++] != '\0' );n--;  //计算str长度  到 n; 
        printf("长度为%d\n",n); 
    
        int i = 0;
        while(i<n)
        {
            BST_Insert(&T, str[i++]);  //注意:: 这里不能出入参数T,T是实参,必须传入地址,才能改变T的结构 
        } 
        return T; 
    } 
    
    
    /* 
    二叉排序树 T中插入key
    规则: 如果树空 直接插入
          如果关键字key小于根结点,插入左子树
          如果关键字key大于根结点,插入右子树
    
    注意: 这里是改变T的结构,所以需要传入的是指针*T而不是T 
    */
    bool BST_Insert(PBinSortTr *T, typeEmpty key)
    {
        if(NULL == (*T) ) 
        {
            (*T) = (PBinSortTr)malloc(sizeof(BinSortTrNod));
            (*T)->data = key;
            (*T)->lChild = (*T)->rChild = NULL;
            return true;
        }
        else if(key == (*T)->data) //树中无重复数据 
        {
            return true;//树中有关键字一样的数据,返回错误 
        }
        else if((*T)->data > key)
        {
            return BST_Insert(&(*T)->lChild, key);
        } 
        else
        {
            return BST_Insert(&(*T)->rChild, key);
        }
    }
    
    
    /*二叉排序树T中 查找key 返回指向key的指针*/
    //T是原树
    //key待查数值
    //P指向key父节点 
    PBinSortTr BST_Search(PBinSortTr T, typeEmpty key, PBinSortTr *P)
    {
        while(T && key != T->data)
        {
            *P = T;
            if(key > T->data)  T = T->rChild;
            else  T = T->lChild;
        } 
    
        if(!T) //key未查到 
        {
            *P = T;
        } 
    
        return T;   
    } 
    
    
    /*
    二叉排序树T删除元素key 
     1)如果删除结点是树叶 
     2)如果结点只有左子树或者右子树,则让k的子树成为z父节点的子树,代替z
     3)如果k左右有两颗树, 则令k直接后继(或前驱)代替k,然后从二叉排序树中
        删除直接后继(或者前驱),转化成第一种或者第二种情况 
    
    */
    bool BST_Delete(PBinSortTr *T, typeEmpty key)
    {
        if(!(*T))
        {
            return false;       
        }
    
        if(key == (*T)->data)
        {
            DeleteNode(T); 
            return true;
        }
        else if(key < (*T)->data)
        {
            return BST_Delete(&(*T)->lChild, key);
        } 
        else
        {
            return BST_Delete(&(*T)->rChild, key);
        }
    }
    
    void DeleteNode(PBinSortTr *T)
    {   
        PBinSortTr Q = *T; //Q是双亲结点 
    
        if((*T)->rChild == NULL) //*T没有右节点 
        {
            *T = (*T)->lChild;
            free(Q); 
            return;
        } 
        else if((*T)->lChild == NULL) //*T没有左节点 
        {
            *T = (*T)->rChild;
            free(Q);
            return;         
        }
    
        PBinSortTr S;   //将前驱作为*T代替*T 
        S = (*T)->lChild;
        while( S->rChild ) //S指向前驱(有待删除) 
        {
            Q = S;
            S = S->rChild;
        }                   //while结束后S指向待删除,
                            //Q指向S的双亲,等待Q好指向S的后免得孩子们 
    
        (*T)->data = S->data;
        if(Q != (*T))    
        {
            Q->rChild = S->lChild;
        } 
        else        //当*T的左孩子只有左孩子的时候 
        {
            Q->lChild = S->lChild;
        }
    
        free(S);
        return;
    }
    
    #endif