二叉排序树(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、数据库研发、幽默程序员等。
预览时标签不可点收录于话题#个上一篇下一篇