二叉搜索树(Binary Search Tree)--C语言描述(转)-阿里云开发者社区

开发者社区> developerguy> 正文

二叉搜索树(Binary Search Tree)--C语言描述(转)

简介: 图解二叉搜索树概念 二叉树呢,其实就是链表的一个二维形式,而二叉搜索树,就是一种特殊的二叉树,这种二叉树有个特点:对任意节点而言,左孩子(当然了,存在的话)的值总是小于本身,而右孩子(存在的话)的值总是大于本身。
+关注继续查看

图解二叉搜索树概念

二叉树呢,其实就是链表的一个二维形式,而二叉搜索树,就是一种特殊的二叉树,这种二叉树有个特点:对任意节点而言,左孩子(当然了,存在的话)的值总是小于本身,而右孩子(存在的话)的值总是大于本身。

下面来介绍在此种二叉树结构上的查找,插入,删除算法思路。

查找:因为这种结构就是为了来方便查找的,所以查找其中的某个值很容易,从根开始,小的往左找,大的往右找,不大不小的就是这个节点了;

代码很简单,这里就不写了。

插入:插入一样的道理,从根开始,小的往左,大的往右,直到叶子,就插入。

代码:

复制代码
int Insert(BSTree *T,data_type data)//插入数据
{
    BSTree newnode,p;
    newnode = (BSTree)malloc(sizeof(BSNode));
    newnode->lchild = newnode->rchild = NULL;
    newnode->data = data;
    if(*T == NULL)
    {
        *T = newnode;
    }
    else
    {
        p = *T;
        while(1)
        {
            if(data == p->data)
            {
                return 0;//数值已存在,不能插入
            }
            else if(data > p->data)
            {
                if(p->rchild == NULL)//右孩子为空,插入
                {
                    p->rchild = newnode;
                    return 1;
                }
                else        //继续向下找
                {
                    p = p->rchild;
                }
            }
            else
            {
                if(p->lchild == NULL)//左孩子为空,插入
                {
                    p->lchild = newnode;
                    return 1;
                }
                else        //继续向下找
                {
                    p = p->lchild;
                }
            }
        }
    }
}
复制代码

 

删除:而结点的删除则比较麻烦,是这个结构中最难的一环,因为我们删除的结点不一定是叶子结点,是叶子结点很好办,但是如果是二叉树中的一个结点,则涉及到删除后的连接问题。

删除一共分为以下四种情况:

1.删除结点为叶子结点:这个就不说了,删除很简单。

2.删除结点不是叶子结点,其左子树不为空,右子树为空:这种情况,只需将其父结点与其右孩子结点连接,然后删除,例如删除下图的40,就是连接30与35。

3.删除结点不是叶子结点,其右子树不为空,左子树为空:这种情况,只需将其父结点与其左孩子结点连接,然后删除,例如删除下图的80,就是连接50和90

4.删除结点不是叶子结点,左右子树都不为空,这种情况最复杂,咋们单独分析分析。

此种情况下,总的删除思想就是:把这个结点往下挪,直到它变为叶子为止。挪移规则:即和此结点下的最大孩子的值交换,把删除该结点转换为删除孩子结点的操作。

当然会出现这种情况,交换后此结点仍然不是叶子结点,那就继续按照挪移规则直到将改结点挪移成叶子结点。举例如图:

 

首先是我自己写的一个删除算法,借用了查找函数。

我的想法还是以前链表的删除思路,删除一个结点需要记录前一个结点,所以我就是用fa记录删除结点的父结点,然后操作的。

所以借用的查找函数就不仅仅只是返回结点地址,也要返回父结点地址。

复制代码
BSTree Find(BSTree T,data_type data,BSTree *target) //查找函数,并返回父亲结点地址
{
    if(T == NULL)//二叉树为空
    {
        *target = NULL;
        return NULL;
    }
    else if(T->data == data)//树根即为要查找的结点
    {
        *target = T;
        return NULL;
    }
    else
    {
        while(T)
        {
            if(T->lchild && T->lchild->data == data)
            {
                *target = T->lchild;
                return T;
            }
            if(T->rchild && T->rchild->data == data)
            {
                *target = T->rchild;
                return T;
            }
            if(data > T->data)
            {
                T = T->rchild;
            }
            if(data < T->data)
            {
                T = T->lchild;
            }
        }
        return NULL;
    }
}

int Delete1(BSTree *T,data_type data)//删除
{
    BSTree fa,target;
    if(*T == NULL)//树为空
    {
        return 0;
    }
    fa = Find(*T,data,&target);//fa为删除结点的父结点,target为删除结点
    if(target->lchild == NULL)    //删除结点左子树为空,右子树不为空的情况(左右子树都为空的情况也适用)
    {
        if(fa == NULL && target->rchild == NULL)//树只存在根结点的情况
        {
            free(*T);
            *T = NULL;
            return 1;
        }
        if(fa->rchild == target)
        {
            fa->rchild = target->rchild;
            free(target);
            return 1;
        }
        if(fa->lchild == target)
        {
            fa->lchild = target->rchild;
            free(target);
            return 1;
        }
    }
    else if(target->rchild == NULL)//删除结点右子树为空,左子树不为空的情况
    {
        if(fa->rchild == target)
        {
            fa->rchild = target->lchild;
            free(target);
            return 1;
        }
        if(fa->lchild == target)
        {
            fa->lchild = target->lchild;
            free(target);
            return 1;
        }
    }
    else    //左右子树都不为空的情况
    {
        if(target->lchild->rchild == NULL)    //孩子结点中最大值结点为target->lchild
        {
            target->data = target->lchild->data;
            return Delete1(&(target->lchild),target->data);
        }
        else        //孩子结点中最大值结点为target->lchild->rchild.....->rchild
        {
            BSTree p1,p2;
            p2 = target->lchild;
            p1 = p2->rchild;
            while(p1->rchild != NULL)//循环找到最大值结点
            {
                p2 = p1;
                p1 = p1->rchild;
            }
            target->data = p1->data;
            return Delete1(&(p2->rchild),p1->data);
        }
    }
}
复制代码

 

然后写完之后感觉自己的算法篇幅好大,貌似有点麻烦,于是在网上找了一下相关的二叉搜索树的删除算法,发现一个很精妙小巧的算法,将递归用的非常漂亮。

当然,算法思路都是差不多的,所以效率上应该没有什么很大的差别,不过这个算法递归思想用的很赞,值得学习一下。

建议先把上面我写的算法看明白了,在看下面的这个。

复制代码
//a:删除叶子结点,只要将其双亲结点链接到它的指针置空即可。
//b:删除单支结点,只要将其后继指针链接到它所在的链接位置即可
//c:删除双支结点,一般采用的方法是首先把它的中序前驱结点的值赋给该结点的值域,
//然后再删除它的中序前驱结点,若它的中序前驱结点还是双支结点,继续对其做同样的操作,
//若是叶子结点或单支结点则做对应的操作,若是根结点则结束。

int Delete(BSTree *T,data_type data)
{
    BSTree temp;
    if(data < (*T)->data)//继续在左子树中查找
    {
        return Delete(&(*T)->lchild,data);
    }
    if(data > (*T)->data)//继续在右子树中查找
    {
        return Delete(&(*T)->rchild,data);
    }
    //代码运行到此处,则找到data,即为(*T)->data
    temp = *T;//*T:删除结点地址,T:记录删除结点地址的指针,即为删除结点的父结点的左/右指针
    if((*T)->lchild == NULL)//删除结点的左子树为空,将整个右子树作为树根(此处也包含叶子结点情况)
    {
        (*T) = (*T)->rchild;
        free(temp);
        return 1;
    }
    else if((*T)->rchild == NULL)//删除结点的右子树为空,将整个左子树作为树根
    {
        (*T) = (*T)->lchild;
        free(temp);
        return 1;
    }
    else//删除结点的左右子树都不为空,找左子树的的最大值结点
    {
        if((*T)->lchild->rchild == NULL)//最大值结点为左孩子的情况
        {
            (*T)->data = (*T)->lchild->data;
            Delete(&((*T)->lchild),(*T)->data);
        }
        else        //最大值结点为最深的右孩子结点情况
        {
            BSTree p1,p2;
            p2 = (*T)->lchild;
            p1 = p2->rchild;
            while(p1->rchild != NULL)
            {
                p2 = p1;
                p1 = p1->rchild;
            }
            (*T)->data = p1->data;
            Delete(&(p2->rchild),p1->data);
        }
    }
}
复制代码

二:二叉搜索树完整代码(C语言)

复制代码
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>

typedef int data_type;

typedef struct bst
{
    data_type data;
    struct bst *lchild,*rchild;
}BSNode,*BSTree;

BSTree Find(BSTree T,data_type data,BSTree *target) //查找函数,并返回父亲结点地址
{
    if(T == NULL)//二叉树为空
    {
        *target = NULL;
        return NULL;
    }
    else if(T->data == data)//树根即为要查找的结点
    {
        *target = T;
        return NULL;
    }
    else
    {
        while(T)
        {
            if(T->lchild && T->lchild->data == data)
            {
                *target = T->lchild;
                return T;
            }
            if(T->rchild && T->rchild->data == data)
            {
                *target = T->rchild;
                return T;
            }
            if(data > T->data)
            {
                T = T->rchild;
            }
            if(data < T->data)
            {
                T = T->lchild;
            }
        }
        return NULL;
    }
}

int Insert(BSTree *T,data_type data)//插入数据
{
    BSTree newnode,p;
    newnode = (BSTree)malloc(sizeof(BSNode));
    newnode->lchild = newnode->rchild = NULL;
    newnode->data = data;
    if(*T == NULL)
    {
        *T = newnode;
    }
    else
    {
        p = *T;
        while(1)
        {
            if(data == p->data)
            {
                return 0;//数值已存在,不能插入
            }
            else if(data > p->data)
            {
                if(p->rchild == NULL)//右孩子为空,插入
                {
                    p->rchild = newnode;
                    return 1;
                }
                else        //继续向下找
                {
                    p = p->rchild;
                }
            }
            else
            {
                if(p->lchild == NULL)//左孩子为空,插入
                {
                    p->lchild = newnode;
                    return 1;
                }
                else        //继续向下找
                {
                    p = p->lchild;
                }
            }
        }
    }
}


int Delete1(BSTree *T,data_type data)//删除
{
    BSTree fa,target;
    if(*T == NULL)//树为空
    {
        return 0;
    }
    fa = Find(*T,data,&target);//fa为删除结点的父结点,target为删除结点
    if(target->lchild == NULL)    //删除结点左子树为空,右子树不为空的情况(左右子树都为空的情况也适用)
    {
        if(fa == NULL && target->rchild == NULL)//树只存在根结点的情况
        {
            free(*T);
            *T = NULL;
            return 1;
        }
        if(fa->rchild == target)
        {
            fa->rchild = target->rchild;
            free(target);
            return 1;
        }
        if(fa->lchild == target)
        {
            fa->lchild = target->rchild;
            free(target);
            return 1;
        }
    }
    else if(target->rchild == NULL)//删除结点右子树为空,左子树不为空的情况
    {
        if(fa->rchild == target)
        {
            fa->rchild = target->lchild;
            free(target);
            return 1;
        }
        if(fa->lchild == target)
        {
            fa->lchild = target->lchild;
            free(target);
            return 1;
        }
    }
    else    //左右子树都不为空的情况
    {
        if(target->lchild->rchild == NULL)    //孩子结点中最大值结点为target->lchild
        {
            target->data = target->lchild->data;
            return Delete1(&(target->lchild),target->data);
        }
        else        //孩子结点中最大值结点为target->lchild->rchild.....->rchild
        {
            BSTree p1,p2;
            p2 = target->lchild;
            p1 = p2->rchild;
            while(p1->rchild != NULL)//循环找到最大值结点
            {
                p2 = p1;
                p1 = p1->rchild;
            }
            target->data = p1->data;
            return Delete1(&(p2->rchild),p1->data);
        }
    }
}


//a:删除叶子结点,只要将其双亲结点链接到它的指针置空即可。
//b:删除单支结点,只要将其后继指针链接到它所在的链接位置即可
//c:删除双支结点,一般采用的方法是首先把它的中序前驱结点的值赋给该结点的值域,
//然后再删除它的中序前驱结点,若它的中序前驱结点还是双支结点,继续对其做同样的操作,
//若是叶子结点或单支结点则做对应的操作,若是根结点则结束。

int Delete(BSTree *T,data_type data)
{
    BSTree temp;
    if(data < (*T)->data)//继续在左子树中查找
    {
        return Delete(&(*T)->lchild,data);
    }
    if(data > (*T)->data)//继续在右子树中查找
    {
        return Delete(&(*T)->rchild,data);
    }
    //代码运行到此处,则找到data,即为(*T)->data
    temp = *T;//*T:删除结点地址,T:记录删除结点地址的指针,即为删除结点的父结点的左/右指针
    if((*T)->lchild == NULL)//删除结点的左子树为空,将整个右子树作为树根(此处也包含叶子结点情况)
    {
        (*T) = (*T)->rchild;
        free(temp);
        return 1;
    }
    else if((*T)->rchild == NULL)//删除结点的右子树为空,将整个左子树作为树根
    {
        (*T) = (*T)->lchild;
        free(temp);
        return 1;
    }
    else//删除结点的左右子树都不为空,找左子树的的最大值结点
    {
        if((*T)->lchild->rchild == NULL)//最大值结点为左孩子的情况
        {
            (*T)->data = (*T)->lchild->data;
            Delete(&((*T)->lchild),(*T)->data);
        }
        else        //最大值结点为最深的右孩子结点情况
        {
            BSTree p1,p2;
            p2 = (*T)->lchild;
            p1 = p2->rchild;
            while(p1->rchild != NULL)
            {
                p2 = p1;
                p1 = p1->rchild;
            }
            (*T)->data = p1->data;
            Delete(&(p2->rchild),p1->data);
        }
    }
}


void CreateBSTree(BSTree *T)//创建二叉树,调用插入算法创建
{
    data_type data;
    char ch;
    printf("请输入要创建的二叉搜索树的数据(数据之间用空格隔开,输入完毕按回车):");
    do
    {
        scanf("%d",&data);
        ch = getchar();
        Insert(T,data);
    }
    while (ch != 10);
}

void Inorder(BSTree T)
{
    if(T)
    {
        Inorder(T->lchild);
        printf("%d ",T->data);
        Inorder(T->rchild);
    }
}


int main()
{
    BSTree T,fa,target;
    T = NULL;
    CreateBSTree(&T);
    Inorder(T);
    int select;
    data_type data;
    while(1)
    {
        printf("1.插入  2.删除 3.中序遍历\n");
        scanf("%d",&select);
        if(select == 1)
        {
            printf("请输入要插入的数据:");
            scanf("%d",&data);
            Insert(&T,data);
            Inorder(T);
            getch();
        }
        else if(select == 2)
        {
            printf("删除数据:");
            scanf("%d",&data);
            Delete1(&T,data);
            Inorder(T);
            getch();
        }
        else if(select == 3)
        {
            Inorder(T);
            getch();
        }
    }            
    return 0;
}
/* 50 30 80 20 40 90 35 85 32 88*/
复制代码
 
http://www.cnblogs.com/ecizep/p/4778241.html

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
LeetCode 145 Binary Tree Postorder Traversal(二叉树的后续遍历)+(二叉树、迭代)
版权声明:转载请联系本人,感谢配合!本站地址:http://blog.csdn.net/nomasp https://blog.csdn.net/NoMasp/article/details/50933610 翻译 给定一个二叉树,返回其后续遍历的节点的值。
693 0
LeetCode 94 Binary Tree Inorder Traversal(二叉树的中序遍历)+(二叉树、迭代)
版权声明:转载请联系本人,感谢配合!本站地址:http://blog.csdn.net/nomasp https://blog.csdn.net/NoMasp/article/details/50930671 翻译 给定一个二叉树,返回其中序遍历的节点的值。
727 0
C语言中使用大括号与给函数命名的正确方法(转载)
使用大括号的正确方法: 在C中,使用大括号的方法无所谓对还是错——只要每个开括号后都有一个闭括号,你的程序中就不再会出现与大括号有关的问题。
977 0
+关注
developerguy
A code cleanliness code farmers, A programmer concentrate on elegant design, A want to do with the product architect
1663
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
《Nacos架构&原理》
立即下载
《看见新力量:二》电子书
立即下载
云上自动化运维(CloudOps)白皮书
立即下载