16.二叉排序树
程序员文章站
2022-05-16 19:09:34
...
一、二叉排序树 如果要查找的数据集是有序线性表且是顺序存储的,查找可以用折半、插值、斐波那契等查找算法来实现。然后,由于有序,当我们在插入和删除操作上,就需要耗费大量的时间。下面将要学习的二叉排序树,就是一种既可以使得插入和删除效率不错,又
一、二叉排序树 如果要查找的数据集是有序线性表且是顺序存储的,查找可以用折半、插值、斐波那契等查找算法来实现。然后,由于有序,当我们在插入和删除操作上,就需要耗费大量的时间。下面将要学习的二叉排序树,就是一种既可以使得插入和删除效率不错,又可以比较高效率地实现查找的算法。为此,构造一棵二叉排序树的目的并不是为了排序,而是为了提供查找和插入删除关键字的速度。 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实例: 假如有一数据集合={62,88,58,47,35,73,51,99,37,93},查找的关键字key=93。 使用二叉排序树查找算法步骤如下: ①根据二叉排序树定义将该数据集合构造成一棵二叉排序树(中序遍历);data) return SearchBST(T->lchild,key,T,p); //在左子树继续查找 else return SearchBST(T->rchild,key,T,p); //在右子树继续查找 }
②调用二叉排序树查询算法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(key
⑦此时第二层SearchBST,因93比88大,所以执行else{....}语句,再次递归调用SearchBST(T->rchild,key,T,p)。此时T指向了88的右孩子99。
⑧此时第三层SearchBST,因93比99小,所以执行else if(key
⑨第四层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举例:假如我们调用函数是"InsertBST(T,93);",那么结果就是FALSE;假如调用函数为"InsertBST(T,95);",那么一定是就是在93的结点增加一个右孩子95,并返回TRUE。需要注意的是,由于插入算法事先调用了SearchBST(*T,key,NULL,&p)查找算法且使用中序遍历二叉树,最终我们可知指针p指向的结点为93. 3.构建二叉排序树算法data)//若关键字小于p结点数据值,插入s为结点p的左孩子 p->lchild = s; else //若关键字大于p结点数据值,插入s为结点p的右孩子 p->rchild=s; } /*树中已有关键字相同的结点,不再插入*/ else { return FALSE; } }
/*假如有一个数据集={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 4.二叉排序树删除操作算法
(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(keydata) 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次,即跟结点就是要找的结点,最多也不会超过树的深度,即二叉排序树的查找性能取决于二叉排序树的形状。