二叉搜索树（C语言）

朱雀 2022-06-13 04:20 181阅读 0赞

## 二叉搜索树讲解 ##

学习二叉搜索树的过程中，对于删除操作中的两个节点都存在的情况进行代码编写时，出现了疑惑，所以我着重讲解一下删除操作代码。

首先进行数据的声明：

#include<stdio.h>
    #include<stdlib.h>
    
    typedef int data_type;      //声明元素类型
    typedef struct bst_node{    //node节点值
        data_type data;
        struct bst_node *lchild,*rchild;
    }bst_t,*bst_p;

### 第一个函数是查找要插入的节点位置： ###

传入根节点root与进行比较的值data

bst_p position_insert(bst_p *root,data_type key)        //找到要插入的值的位置
    {
        bsp_p s,p = *root;
    
        while(p)
        {
            s = p;
            if(p->data == key)                              //如果这个值本身就存在，返回NULL
                return NULL;
            p = (key < p->data) ? p->lchild : p->rchild;    //继续向下查找位置
        }
        return s;
    }

### 第二个函数与第一个函数搭配使用，即插入操作： ###

bst_p insert_node(bst_p *root, data_type data)          //进行插入操作
    {
        bst_p s,p = *root;
    
        s  = malloc(sizeof(struct bst_p));                  //申请一个bst_p的空间
    
        s->data = data;                                     //把这个传入的值放进这个新申请的空间里面
        s->lchild = s->rchild = NULL;
    
        if(*root==NULL)                                     //如果是一个空树
            *root = s;
        else
        {
            s = position_insert(*root,data);
            if(s==NULL)                                     //如果要插入的值本身存在
            {
                printf("the element %d exists!\n",data);
                free(s);
                return;
            }
        }
    }

### 第三个函数是查找操作，查找data是否在二叉树中，如果一个树的高度为h，那么查找的时间复杂度最高就是O（h）， ###

bst_p search_node( bst_p *root, data_type data )         //查询数值是否在树中
    {
        bst_p s;
        s = *root;
    
        if(s == NULL)
            printf("empty tree!\n");
        while(s)
        {
            if(s->data == data)
                return s;
            else if(s->data >data)
                s = s->rchild;
            else
                s = s->lchild;
        }
        return NULL;
    }

### 第四个函数是删除操作： ###

首先我放一下完整的代码，稍后说明我的理解：

删除操作主要分为三种，

（1）第一种是删除的是子节点

（2）第二种是删除的节点左右子节点其中有一个存在

（3）第三种是左右两个节点都存在

bool delete_node(bst_p *root,data_type data)            //声明一个q节点，q节点是p节点的父节点
    {
        bst_p q = NULL , p = *root;
        bool sign = false;
    
        if(p ==NULL){       //判断是否是空树
            printf("empty tree !\n nothing to delete");
            return true;
        }
    
        while(p && !sign)   //寻找该节点
        {
            if(p->data == data)
                sign = true;
    
            else if(p->data > data)
            {
                q = p;
                p = p->rchild;
            }
            else
            {
                q = p;
                p = p->lchild;
            }
        }
    
        if(sign == false){      //没找到该节点
            printf("element don't exists!\n");
            return true;
        }
    
        if( p->lchild == NULL && p->rchild == NULL )    //两个子节点都为空，直接删除
        {
            if(p == root)
                printf("now root is delete!\n");
            free(s);
            return true;
        }
        else if( !p->rchild || !p->lchild )       //其中一个子节点为空
        {
            if( q->lchild == p && p->rchild )
            {
                q->lchild = p->rchild;
                free(p);
                return true;
            }
            else if(q->rchild == p && p->rchild)
            {
                q->rchild = p->rchild;
                free(p);
                return true;
            }
            else if(q->lchild == p && p->lchild)
            {
                q->lchild = p->lchild;
                free(p);
                return true;
            }
            else if(q->rchild ==p && p->lchild)
            {
                q->rchild = p->lchild;
                free(p);
                return true;
            }
        }
        else//两个字节点都不为空
        {
            bst_p s,t = p;//采用前驱方式
            s = p->lchild;
            while(s->rchild)
            {
                t = s;
                s = s->rchild;
            }
            p->data = s->data;  //节点s的值赋给节点p的值
            if(t == p)
            {
                p->lchild = s->lchild;
            }
            else
            {
                t->rchild = s->lchild;
            }
            free(s);
            free(t);
            return true;
        }
    }

这段代码主要说的是查找要删除的节点，并保留节点p的父节点，保留父节点主要是考虑到第三种情况，再删除节点时需要用到父节点进行赋值

while(p && !sign)   //寻找该节点
        {
            if(p->data == data)
                sign = true;
    
            else if(p->data > data)
            {
                q = p;
                p = p->rchild;
            }
            else
            {
                q = p;
                p = p->lchild;
            }
        }

（1）删除子节点

if( p->lchild == NULL && p->rchild == NULL )    //两个子节点都为空，直接删除
        {
            if(p == root)
                printf("now root is delete!\n");
            free(s);
            return true;
        }

（2）删除节点中子节点有一个存在

1.这里用到了父节点q，我们在进行删除时，当p是q的左孩子，并且p有右孩子时

![Center][]

else if( !p->rchild || !p->lchild )       //其中一个子节点为空
        {
            if( q->lchild == p && p->rchild )
            {
                q->lchild = p->rchild;
                free(p);
                return true;
            }
    
     
     
     
     
     2.当p是q的右孩子，并且p有右孩子时，
     
     
            else if(q->rchild == p && p->rchild)
            {
                q->rchild = p->rchild;
                free(p);
                return true;
            }
    
     
     
     
     
     
     
     3.当p是q的左孩子，并且p有左孩子时，
     
     
     
     
     
     
             else if(q->lchild == p && p->lchild)
            {
                q->lchild = p->lchild;
                free(p);
                return true;
            }
    
     
     
     
    4.当p是q的右孩子，并且p有左孩子时，
     
     
     
     
     
     
     
            else if(q->rchild ==p && p->lchild)
            {
                q->rchild = p->lchild;
                free(p);
                return true;
            }
        }
     
     
     
     
     （3）当删除的节点有左右两个子节点时，
     
     else//两个字节点都不为空
        {
            bst_p s,t = p;//采用前驱方式
            s = p->lchild;
            while(s->rchild)
            {
                t = s;
                s = s->rchild;
            }
            p->data = s->data;  //节点s的值赋给节点p的值
            if(t == p)
                p->lchild = s->lchild;
            else
                t->rchild = s->lchild;
            free(s);
            free(t);
            return true;
        }

[Center]: /images/20220613/e2803a2dbd144e6282c2e2760968b6a0.png