数据结构二叉排序树BinaryS [复制链接]

二叉排序树(BinarySortTree)，又称二叉查找树。它是一颗空树，或者具有下列性质：

若它的左子树不为空，则左子树上所有结点的值均小于它的根结点的值；

若它的右子树不为空，则右子树上所有结点的值均大于它的根结点的值；

它的左、右子树分别为二叉排序树。

构造二叉排序树的目的

提高查找和插入删除关键字的速度。

二叉排序树的查找可以用递归来实现；

先将要查找的关键字和根节点进行比较;

若和根节点值相同，则返回根节点值；若比根节点小，就递归查找左子树，若比根节点大，则递归查找右子树。

#defineTRUE1#defineFALSE0#defineMAXSIZEtypedefstructBiTNode{//二叉树的儿二叉链表结点结构intdata;//结点结构structBiTNode*lchild,*rchild;//左右孩子指针}BiTNode,*BiTree;/***递归查找二叉排序树T中是否存在key*指针f指向T的双亲，其初始调用值为NULL*若查找成功，则指针p指向该数据元素结点，并返回TRUE*若查找不成功，则指针p指向查找路径上访问的最后一个结点并返回FALSE*/intSearchBST(BiTreeT,intkey,BiTreef,BiTree*p){if(!T){//查找不成功*p=f;returnFALSE;}elseif(key==T-data){*p=T;returnTRUE;}elseif(keyT-data){//在左子树中继续查找returnSearchBST(T-lchild,key,T,p);}else{//在右子树中鸡血查找returnSearchBST(T-rchild,key,T,p);}}二、二叉排序树的插入操作

先调用查找操作将要插入的关键字进行比较

如果在原有的二叉排序树中没有要插入的关键字，则将关键字与查找的结点p（在查找操作中返回的结点）的值进行比较

若p为空，则插入关键字赋值给该节点

若小于结点p的值，则插入关键字作为结点p的左子树；

若大于结点p的值，则插入关键字作为结点p的右子树；

二叉排序树的插入操作代码实现

/***二叉排序树的插入*当二叉排序树中不存在关键字等于key的数据元素时，插入key并返回TRUE*/intInsertBST(BiTree*T,intkey){BiTreep,s;if(!SearchBST(*T,key,NULL,p)){//没找到keys=(BiTree)malloc(sizeof(BiTNode));s-data=key;s-lchild=s-rchild=NULL;if(!p)*T=s;//插入s为新的根结点elseif(keyp-data)p-lchild=s;//插入s为左孩子elsep-rchild=s;//插入s为右孩子returnTRUE;}elsereturnFALSE;}三、二叉排序树的删除操作

二叉排序树的删除操作相对复杂，因为不能因为删除了结点，让这颗二叉排序树变得不满足二叉排序树的性质，所以对于二叉排序树的删除存在三种情况：

叶子结点；（很容易实现删除操作，直接删除结点即可）

仅有左或者右子树的结点；（容易实现删除操作，删除结点后，将它的左子树或者右子树整个移动到删除结点的位置）

左右子树都有的结点。（实现删除操作很复杂）

将它的直接前驱或者直接后继作为删除结点的数据

如图，要删除的结点为47

47的直接前驱是7，直接后继是48

如果用直接前驱7作为删除后结点的值，（由于结点7有一个左子树）那么（左子树）6就去替换到7结点上。

如果用直接后继47作为删除后结点的值，（由于结点47是叶子结点）那么直接将48替换到7结点上即可。

/***从二叉排序树中删除结点p，并重接它的左/右子树*/intDelete(BiTree*p){BiTreeq,s;if((*p)-rchild==NULL){//右子树空则只需要重接它的左子树q=*p;*p=(*p)-lchild;free(q);}elseif((*p)-lchild==NULL){//左子树空则只需要重接它的右子树q=*p;*p=(*p)-rchild;free(q);}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的右子树elseq-lchild=s-lchild;//重接q的左子树free(s);}returnTRUE;}/***二叉排序树的删除*当二叉排序树中存在关键字等于key的数据元素时，删除该数据元素并返回TRUE*/intDeleteBST(BiTree*T,intkey){if(!*T)//不存在关键字等于key的元素returnFALSE;else{if(key==(*T)-data)returnDelete(T);elseif(key(*T)-data)returnDeleteBST((*T)-lchild,key);elsereturnDeleteBST((*T)-rchild,key);}}四、测试代码

对于二叉排序树的建立，可以通过二叉排序树的插入操作来实现。

通过中序遍历二叉排序树，结果是从小到大输出。

/***中序递归遍历*/voidInOrderTraverse(BiTreeT){if(!T)return;InOrderTraverse(T-lchild);printf("%d",T-data);InOrderTraverse(T-rchild);}intmain(intargc,constchar*argv[]){inti;inta[10]={6,88,8,47,,7,1,99,7,9};BiTreeT=NULL;for(i=0;i10;i++){//通过插入操作来构建二叉排序树InsertBST(T,a);}printf("中序递归遍历二叉排序树：\n");InOrderTraverse(T);printf("\n\n");DeleteBST(T,9);printf("删除结点9后的结果为：\n");InOrderTraverse(T);printf("\n\n");printf("插入91后的结果为：\n");InsertBST(T,91);InOrderTraverse(T);printf("\n\n");return0;}二叉排序树总结

二叉排序树是以链接的方式存储，保持了链接存储结构在执行插入或删除操作时不用移动元素的优点。只要找到合适的插入和删除位置后，仅需要修改链接指针即可。插入删除的时间性能比较好。

对于二叉排序树的查找，走的是根结点到要查找结点的路径，其比较次数等于给定值的结点在二叉排序树的层次。

推荐↓↓↓

长

按

关

注

??都在这里！

涵盖：程序员大咖、源码共读、程序员共读、数据结构与算法、黑客技术和网络安全、大数据科技、编程前端、Java、Python、Web编程开发、Android、iOS开发、Linux、数据库研发、幽默程序员等。