C语言数据结构-11顺序二叉树

引入定义二叉排序树又称二叉搜索树二叉查找树Binary Search TreeBST在二叉树的基础上人为增加以下规定对于任意一个结点如果其左子节点存在则左子结点的数据比该结点小对于任意一个结点如果其右子节点存在则右子结点的数据比该结点大如图所示注规定不是唯一的例如每个结点满足左大右小也是一种二叉排序树可以发现二叉排序树的递归特性性质中序遍历有序中序遍历顺序为左子结点本结点右子结点而二叉排序树结点满足左中右。如图中序遍历结果是1 2 3 4 6 7 8 9而先序遍历中左右和后序遍历左右中是无序的查找效率高有n个结点的普通二叉树最多需要找n次但是二叉排序树最多只需要找h高度次。如图中9首先找6比9小于是去6的右子结点再找88比9小于是去8的右子结点最后找到9找到目标。整个过程只需要3次查找。若是常规查找需要遍历整棵树到最后才能找到。实现二叉树结点与之前一致#includestdio.h #includestdlib.h ​ //二叉树结点 typedef struct Node{ int data;//数据域 struct Node* l;//左子结点 struct Node* r;//右子结点 }TNode,*BST;查找递归版如果空树返回null跟根结点比较为根结点返回不为则下一步如果目标值小于根结点则向左子树查找如果目标值大于根结点则向右子树查找非递归版指针指向根结点循环循环条件指针不为null且不等于目标值循环体如果目标值小于指针数据指针指向左子节点如果目标值小于指针数据指针指向左子节点返回指针的结点//查找--递归 TNode* find1(BST root,int x){ if(rootNULL||root-datax) return root;//查找根结点 if(root-l!NULLxroot-data) return find1(root-l,x);//查找左子树 if(root-r!NULLxroot-data) return find1(root-r,x);//查找右子树 } ​ //查找--非递归 TNode* find2(BST root,int x){ TNode* proot; while(p!NULLp-data!x){//一层层循环匹配 if(xp-data) pp-l; else if(xp-data) pp-r; } return p; }如图查找7插入数据不考虑数据重复递归版如果是空树那么创建根结点令k为根结点数据非空树k根结点就去根结点左子树中插入返回值为当前根节点的左子节点k根结点就去根结点右子树中插入返回值为当前根节点的右子节点非递归插入结点之前需要确定应该插入的位置即使用指针去一个一个确定是否满足条件这个逻辑类似于查找的过程。我们需要一个指针p指向目标位置null和一个指针pre指向目标位置p的父结点之后只需要循环查找就行。如果是空树那么创建根结点令k为根结点数据声明指针p和pre循环查找循环条件p不为null循环体preppre向后移动如果数据kp的数据p就指向p左子节点反之就指向右子结点循环结束p为null此时pre为应插入数据k的父结点。插入数据kkpre数据则插入左子节点反之插入为右子结点//插入数据--递归 BST insert1(BST root,int x){ if(rootNULL){//空树 递归出口 BST s (BST)malloc(sizeof(TNode)); s-datax; s-ls-rNULL; return s; }else{//非空树 if(xroot-data){ root-linsert1(root-l,x); }else{ root-rinsert1(root-r,x); } return root; } } ​ //插入数据--非递归 BST insert2(BST root,int x){ if(rootNULL){//空树 BST s (BST)malloc(sizeof(TNode)); s-datax; s-ls-rNULL; return s; } ​ //非空树 TNode* pre NULL; TNode* proot; while(p!NULL){//循环匹配 prep;//pre向后移动 //p向后移动分两种情况 if(xp-data) pp-l; else pp-r; } TNode* s (TNode*)malloc(sizeof(TNode)); s-datax; s-ls-rNULL; //插入结点到指定位置 if(xpre-data) pre-ls; else pre-rs; return root; }删除数据x非递归查找x所在的结点p删除结点p。删除操作根据p的度分为两大类度为0或1若度为0以删除17为例将指向p的父结点f对应指针赋值为null再删除结点pp为null若度为1以删除15为例则让p唯一的子节点继承p的关系。即先将f对应指针指向p唯一的子节点ch再删除结点pp为null于是这两种删除情况可以进行统一首先声明一个指针ch若p的左子节点不为nullch指向该左子节点否则ch指向右子结点让f指向p的指针指向ch子结点继承p的关系删除p结点度为2如图中序遍历的结果1 7 9 11 13 15 17 1920 21 2324 25 28 30删除21效果就是20前驱或22后继继承21位置这里采用前驱去继承。前驱位于结点p的左子树的最右端。继承只需要将前驱的数据代替p的数据即可操作简单。在继承之后还需要找到并删除原来的前驱结点此时该结点20的度只可能为0或1若度为2该结点不可能为p的前驱前驱还需要再往右找因此又回到删除结点的度为0或1的情况因此删除结点的操作查找p的前驱节点t左子树的最右端让t继承p的关系只需要改变数据删除t问题转化为删除结点的度为0或1的情况//删除数据--非递归 BST delete1(BST root,int x){ if(rootNULL){ printf(空树无法删除\n); return root; } //1.找到x所在结点p及其父结点f TNode* proot; TNode* fNULL; while(p!NULLp-data!x){ fp; if(xp-data) pp-l; else pp-r; } if(pNULL){//找不到数据x printf(数据不存在无法删除\n); return root; } //2.1 p的度为2,前驱结点继承p的关系只需要将前驱的数据代替 if(p-l!NULLp-r!NULL){ TNode* tp-l;//找前驱:在左子树的最右端 TNode* tfp;//前驱的父结点 while(t-r!NULL){ tft; tt-r; } p-datat-data;//前驱t继承p的关系只需要将前驱的数据代替 pt;//为了使用同一组代码方便在度不为2的情况进行删除操作 ftf; } ​ //2.2 现在需要删除pp的度为1或0 TNode* chNULL;//找到p的子结点 if(p-l!NULL) chp-l; else chp-r; ​ //ch继承p的关系:注意此时p一定不为null但是f可能为nullp为根结点且p的度为1 if(f!NULL){ if(pf-l) f-lch; else f-rch; }else{//f为nullp为根结点:让p的子结点作为根结点 rootch; } ​ //删除p free(p); pNULL; return root; }递归空树递归出口没找到如果x根结点数据先判断结点的度根据度的情况进行操作参考非递归的删除操作如果度为2这里采用后继来实现如果x根结点数据去根结点的左子树删除如果x根结点数据去根结点的左子树删除//删除数据--递归 BST delete2(BST root,int x){ //1.不存在 if(rootNULL){ printf(空树无法删除\n); return root; } ​ //2.x根结点数据 if(xroot-data){ //根结点度为2,使用后继结点继承根结点的关系 if(root-l!NULLroot-r!NULL){ TNode* troot-r;//找后继 while(t-l!NULL){ tt-l;//往左走 } root-datat-data; root-rdelete2(root-r,t-data);//注意删除后继也是采用递归 }else{//度为0或1:根指针指向唯一的子节结点然后删除根结点 TNode* proot; //根指针指向唯一的子节结点 if(root-l!NULL) rootroot-l; else rootroot-r; //删除原来的根结点 free(p); pNULL; } } ​ else if(xroot-data){//3.x根结点数据 root-ldelete2(root-l,x); } ​ else{//3.x根结点数据 root-rdelete2(root-r,x); } ​ return root; ​ }效果演示//中序遍历 void MediaOrderBT(BST t){ if(tNULL) return; MediaOrderBT(t-l); printf(%d ,t-data); MediaOrderBT(t-r); } ​ ​ int main(){ BST tNULL; int n,x;//n个数据 scanf(%d,n); for(int i0;in;i){//插入数据 getchar(); scanf(%d,x); t insert2(t,x); } ​ //测试两个find函数 scanf(%d,x); /*TNode* r1 find1(t,x); if(r1!NULL) printf(%d ,r1-data); else printf(该数据不存在 ); */ /* TNode* r2 find2(t,x); if(r2!NULL) printf(%d\n,r2-data); else printf(该数据不存在\n); */ //中序遍历查看是否是顺序二叉树 MediaOrderBT(t); printf(\n); ​ //非递归删除 /* tdelete1(t,x); MediaOrderBT(t); */ //递归删除 tdelete1(t,x); MediaOrderBT(t); return 0; } ​ /* 15 13 9 21 7 11 15 23 1 19 25 17 20 24 30 28 21 */结果1 7 9 11 13 15 17 19 20 21 23 24 25 28 30 1 7 9 11 13 15 17 19 20 23 24 25 28 30感谢您的阅读您的点赞是我坚持下去的动力