首页 / MYSQL / 16.二叉排序树

16.二叉排序树

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了16.二叉排序树，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含6187字，纯文字阅读大概需要9分钟。

内容图文

一、二叉排序树 如果要查找的数据集是有序线性表且是顺序存储的，查找可以用折半、插值、斐波那契等查找算法来实现。然后，由于有序，当我们在插入和删除操作上，就需要耗费大量的时间。下面将要学习的二叉排序树，就是一种既可以使得插入和删除效率不错，又

一、二叉排序树 如果要查找的数据集是有序线性表且是顺序存储的，查找可以用折半、插值、斐波那契等查找算法来实现。然后，由于有序，当我们在插入和删除操作上，就需要耗费大量的时间。下面将要学习的二叉排序树，就是一种既可以使得插入和删除效率不错，又可以比较高效率地实现查找的算法。为此，构造一棵二叉排序树的目的并不是为了排序，而是为了提供查找和插入删除关键字的速度。 1.二叉排序树概念 二叉排序树(Binary Sort Tree)，又称为二叉查找树，或者是一棵空树，或者是具有下列性质的二叉树。 ◆若它的左子树不空，则左子树上所有结点的值均小于它的根结构(双亲结点)的值; ◆若它的右子树不空，则右子树上所有结点的值均大于它的根结点(双亲结点)的值; ◆它的左、右子树也分别为二叉排序树。 2.二叉树结点结构 
/*二叉树的二叉链表结点结构定义*/
typedef struct BiTNode                        //结点结构
{
    int data;                                            //结点数据
    Struct BiTNode *lchild,*rchild;       //左右孩子指针
}BiTNode,*BiTree;
二、二叉排序树操作算法 1.二叉排序树的查询操作 
/*递归查找二叉排序树T中是否存在key,
   * 指针f指向T的双亲，其初始调用值为NULL
    *若查找成功，则指针p指向该数据元素结点，并返回TRUE；否则指针p指向查找路径上访问的最后一个结点并返回FALSE*/
Status SearchBST(BiTree T,int key,BiTree f,BiTree *p)
{
    if(!T)                            //查找不成功(为空树)
    {
            *p=f;
            return FALSE;
    }
    else if(key==T->data)  //查找成功
    {
            *p=T;
            return TRUE;
    }
    else if(key<T->data)
            return SearchBST(T->lchild,key,T,p);        //在左子树继续查找
    else
            return SearchBST(T->rchild,key,T,p);        //在右子树继续查找  
}
实例： 假如有一数据集合={62,88,58,47,35,73,51,99,37,93}，查找的关键字key=93。 使用二叉排序树查找算法步骤如下： ①根据二叉排序树定义将该数据集合构造成一棵二叉排序树(中序遍历); 16.二叉排序树 - 文章图片
②调用二叉排序树查询算法SearchBST(T,93,NULL,P)查询关键字，其中，SearchBST函数是一个可递归运行的函数，参数T是一个二叉树链表、key代表要查询的关键字、二叉树f指向T的双亲。当T指向根结点时，f的初值就为NULL，它在递归时有用，最后的参数p是为了查找成功后可以得到查找到的结点位置。 ③ if(!T){ .... }语句。用来判断当前二叉树是否到叶子结点，此时当前T指向根结点62的位置，由于T不为空，故该语句片段不执行。 ④esle if(key==T->data)语句。即查找到相匹配的关键字执行语句，显然93!=62，故该语句片段不执行。 ⑤else if(keydata)语句。即当要查找关键字小于当前结点时执行语句，由于93>62，故该语句片段不执行。 ⑥else{....}语句。即当即当要查找关键字大于当前结点时执行语句，93>62,所以以递归调用SearchBST(T->rchild,key,T,p)。此时，T指向了62的右孩子88，f指向88的双亲结点，即62。如图： 16.二叉排序树 - 文章图片
⑦此时第二层SearchBST,因93比88大，所以执行else{....}语句，再次递归调用SearchBST(T->rchild,key,T,p)。此时T指向了88的右孩子99。 16.二叉排序树 - 文章图片
16.二叉排序树 - 文章图片 ⑧此时第三层SearchBST,因93比99小，所以执行else if(keydata)语句，再次递归调用SearchBST(T->lchild,key,T,p)。此时T指向了99的左孩子93。 16.二叉排序树 - 文章图片
⑨第四层SearchBST,因key等于T->data，所以执行第10~11行，此时指针p指向93所在的结点并返回True到第三层、第二层、第一层，最终返回函数True。 2.二叉排序树的插入操作 所谓二叉排序树的插入，即将关键字放到树中的合适位置。 (1)二叉排序树的插入算法 
/*当二叉排序树T中不存在关键字等于key的数据元素时，
 *    插入key并返回TRUE，否则返回FALSE*/
Status InsertBST(BiTree *T,int key)
{
    BiTree p,s;
    /*调用查找函数查找是否存在该关键字*/
    //a.若查找不成功
    if(!SearchBST(*T,key,NULL,&p))    
    {
          s=(BiTree)malloc(sizeof(BiTNode));    //为结点s开辟一段内存空间
          s->data=key;                                       //将关键字存放到s指向结点的数据域中
          s->lchid=s->rchild=NULL;                //初始化结点s的左右指针域
         if(!p)
                *T=s;                //插入s为新的根结点
         else if(key<p->data)//若关键字小于p结点数据值，插入s为结点p的左孩子
                p->lchild = s;   
          else                        //若关键字大于p结点数据值，插入s为结点p的右孩子
                p->rchild=s;   
    }
    /*树中已有关键字相同的结点，不再插入*/
    else
    {
            return FALSE;    
    }
}
举例：假如我们调用函数是"InsertBST(T,93);"，那么结果就是FALSE;假如调用函数为"InsertBST(T,95);"，那么一定是就是在93的结点增加一个右孩子95，并返回TRUE。需要注意的是，由于插入算法事先调用了SearchBST(*T,key,NULL,&p)查找算法且使用中序遍历二叉树，最终我们可知指针p指向的结点为93. 3.构建二叉排序树算法
/*假如有一个数据集={62,88,58,47,35,73,51,99,37,93}
    * 构建一个二叉排序树*/
int i;
int a[0]={62,88,58,47,35,73,51,99,37,93};
BiTree T=NULL;
for(i=0;i<10;i++)
{
    InsertBST(&T,a[i]);
}
4.二叉排序树删除操作算法 16.二叉排序树 - 文章图片
(1)采用递归方式对二叉排序树T查找key，找到后调用Delete函数删除该结点 /*若二叉排序树T中存在关键字等于key的数据元素时，则删除该数据元素结点 * 并返回TRUE；否则返回FALSE*/ 
Status DeleteBST(BiTree *T,int key)
{
     if(!*T)    //不存在关键字等于key的数据元素
            return FALSE;
    else
    {
        if(key==(*T)->data)    //找到关键字等于key的数据元素
                return Delete(T);    //调用Delete函数删除该结点
        else if(key<(*T)->data)
                return DeleteBST(&(*T)->lchild,key);    
        else
                return DeleteBST(&(*T)->rchild,key);
    }   
}
(2)Delete删除算法 
/*从二叉排序树中删除结点p,并重接它的左或右子树*/
Status Delete(BiTree *p)
{
     BiTree q,s;
    /*情况二：删除结点p的右子树或左子树为空*/
    if((*p)->lchild==NULL)               //a.右子树空则只需重接它的左子树
    {
            q=*p;    *p=(*p)->lchild;    free(q);
    }    
    else if((*p)->rchild==NULL)        //b.只需重接它的右子树
 【本文来自鸿网互联 (http://www.68idc.cn)】   {
            q=*p;    *p=(*p)->rchild;    free(q);    //将指针p指向的结点
    }
    //情况三：左右子树均不为空
    else
    {
            q=*p;    s=(*p)->lchild;
            while(s->rchild)            //转左，然后向右到尽头(找待删结点的前驱)
            {
                 q=s;    s=s->rchild;           
            }
            (*p)->data=s->data;    //s指向被删结点的直接前驱
            if(q!=*p)
                    q->rchild=s->lchild;    //重接q的右子树
            else
                    q->lchild=s->lchild;    //重接q的左子树
            free(s);
    }
    return TRUE;
}
源码分析： q=*p; *p=(*p)->rchild; free(q); 作用：将指针p指向的结点赋值给新结点q，并使p指针指向的左结点，即实现了重接右子树，再释放结点q.
三、二叉排序树总结 二叉排序树是以链接的方式存储，保持了链接存储结构在执行插入或删除操作时不用移动元素的优点，只要找到合适的插入和删除位置后，仅需修改链接指针即可。插入删除的时间性能比较好，而对于二叉排序树的查找，走的就是从根结点到要查找的结点的路径，其比较次数等于给定值的结点在二叉排序树的层数。极端情况，最少为1次，即跟结点就是要找的结点，最多也不会超过树的深度，即二叉排序树的查找性能取决于二叉排序树的形状。

内容总结

以上是互联网集市为您收集整理的16.二叉排序树全部内容，希望文章能够帮你解决16.二叉排序树所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/559588.html

来源：【匿名】