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

引入

定义

二叉排序树（又称二叉搜索树，二叉查找树）：Binary Search Tree（BST）

在二叉树的基础上，人为增加以下规定：

1. 对于任意一个结点，如果其左子节点存在，则左子结点的数据比该结点小

2. 对于任意一个结点，如果其右子节点存在，则右子结点的数据比该结点大

如图所示：

注：

1. 规定不是唯一的，例如每个结点满足左大右小，也是一种二叉排序树

2. 可以发现二叉排序树的递归特性

性质

1. 中序遍历有序：中序遍历顺序为左子结点，本结点，右子结点，而二叉排序树结点满足左＜中＜右。

如图：中序遍历结果是1 2 3 4 6 7 8 9

而先序遍历（中＞左＜右）和后序遍历（左＜右＞中）是无序的

1. 查找效率高：

有n个结点的普通二叉树，最多需要找n次，但是二叉排序树最多只需要找h（高度）次。如图中9，首先找6，比9小，于是去6的右子结点；再找8，8比9小，于是去8的右子结点；最后找到9，找到目标。整个过程只需要3次查找。若是常规查找，需要遍历整棵树，到最后才能找到。

实现

二叉树结点

与之前一致

#include<stdio.h> #include<stdlib.h> ​ //二叉树结点 typedef struct Node{ int data;//数据域 struct Node* l;//左子结点 struct Node* r;//右子结点 }TNode,*BST;

查找

递归版：

1. 如果空树，返回null

2. 跟根结点比较，为根结点返回，不为则下一步

3. 如果目标值小于根结点，则向左子树查找

4. 如果目标值大于根结点，则向右子树查找

非递归版：

1. 指针指向根结点

2. 循环：

循环条件：指针不为null且不等于目标值

循环体：如果目标值小于指针数据，指针指向左子节点；如果目标值小于指针数据，指针指向左子节点

1. 返回指针的结点

//查找--递归 TNode* find1(BST root,int x){ if(root==NULL||root->data==x) return root;//查找根结点 if(root->l!=NULL&&x<root->data) return find1(root->l,x);//查找左子树 if(root->r!=NULL&&x>root->data) return find1(root->r,x);//查找右子树 } ​ //查找--非递归 TNode* find2(BST root,int x){ TNode* p=root; while(p!=NULL&&p->data!=x){//一层层循环匹配 if(x<p->data) p=p->l; else if(x>p->data) p=p->r; } return p; }

如图：查找7

插入数据（不考虑数据重复）

递归版：

1. 如果是空树，那么创建根结点，令k为根结点数据

2. 非空树：

k＜根结点，就去根结点左子树中插入，返回值为当前根节点的左子节点

k＞根结点，就去根结点右子树中插入，返回值为当前根节点的右子节点

非递归：

插入结点之前需要确定应该插入的位置，即使用指针去一个一个确定是否满足条件，这个逻辑类似于查找的过程。我们需要一个指针p指向目标位置（null），和一个指针pre指向目标位置p的父结点，之后只需要循环查找就行。

1. 如果是空树，那么创建根结点，令k为根结点数据

2. 声明指针p和pre

3. 循环查找

循环条件：p不为null

循环体：pre＝p，pre向后移动；如果数据k＜p的数据p就指向p左子节点，反之就指向右子结点

1. 循环结束，p为null，此时pre为应插入数据k的父结点。插入数据k：k＜pre数据则插入左子节点；反之插入为右子结点

//插入数据--递归 BST insert1(BST root,int x){ if(root==NULL){//空树 递归出口 BST s= (BST)malloc(sizeof(TNode)); s->data=x; s->l=s->r=NULL; return s; }else{//非空树 if(x<root->data){ root->l=insert1(root->l,x); }else{ root->r=insert1(root->r,x); } return root; } } ​ //插入数据--非递归 BST insert2(BST root,int x){ if(root==NULL){//空树 BST s= (BST)malloc(sizeof(TNode)); s->data=x; s->l=s->r=NULL; return s; } ​ //非空树 TNode* pre= NULL; TNode* p=root; while(p!=NULL){//循环匹配 pre=p;//pre向后移动 //p向后移动，分两种情况 if(x<p->data) p=p->l; else p=p->r; } TNode* s= (TNode*)malloc(sizeof(TNode)); s->data=x; s->l=s->r=NULL; //插入结点到指定位置 if(x<pre->data) pre->l=s; else pre->r=s; return root; }

删除数据x

非递归

1. 查找x所在的结点p

2. 删除结点p。删除操作根据p的度分为两大类：

• 度为0或1：

若度为0，以删除17为例，将指向p的父结点f对应指针赋值为null，再删除结点p，p为null

若度为1，以删除15为例，则让p唯一的子节点继承p的关系。即先将f对应指针指向p唯一的子节点ch，再删除结点p，p为null

于是这两种删除情况可以进行统一

1. 首先声明一个指针ch，若p的左子节点不为null，ch指向该左子节点；否则ch指向右子结点

2. 让f指向p的指针指向ch（子结点继承p的关系）

3. 删除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的情况

因此删除结点的操作：

1. 查找p的前驱节点t（左子树的最右端），让t继承p的关系（只需要改变数据）

2. 删除t（问题转化为删除结点的度为0或1的情况）

//删除数据--非递归 BST delete1(BST root,int x){ if(root==NULL){ printf("空树，无法删除\n"); return root; } //1.找到x所在结点p及其父结点f TNode* p=root; TNode* f=NULL; while(p!=NULL&&p->data!=x){ f=p; if(x<p->data) p=p->l; else p=p->r; } if(p==NULL){//找不到数据x printf("数据不存在，无法删除\n"); return root; } //2.1 p的度为2,前驱结点继承p的关系：只需要将前驱的数据代替 if(p->l!=NULL&&p->r!=NULL){ TNode* t=p->l;//找前驱:在左子树的最右端 TNode* tf=p;//前驱的父结点 while(t->r!=NULL){ tf=t; t=t->r; } p->data=t->data;//前驱t继承p的关系：只需要将前驱的数据代替 p=t;//为了使用同一组代码，方便在度不为2的情况进行删除操作 f=tf; } ​ //2.2 现在需要删除p，p的度为1或0 TNode* ch=NULL;//找到p的子结点 if(p->l!=NULL) ch=p->l; else ch=p->r; ​ //ch继承p的关系:注意，此时p一定不为null，但是f可能为null（p为根结点且p的度为1） if(f!=NULL){ if(p==f->l) f->l=ch; else f->r=ch; }else{//f为null（p为根结点）:让p的子结点作为根结点 root=ch; } ​ //删除p free(p); p=NULL; return root; }

递归

1. 空树（递归出口）：没找到

2. 如果x==根结点数据：

   • 先判断结点的度

   • 根据度的情况进行操作（参考非递归的删除操作，如果度为2，这里采用后继来实现）

3. 如果x<根结点数据：去根结点的左子树删除

4. 如果x>根结点数据：去根结点的左子树删除

//删除数据--递归 BST delete2(BST root,int x){ //1.不存在 if(root==NULL){ printf("空树，无法删除\n"); return root; } ​ //2.x==根结点数据 if(x==root->data){ //根结点度为2,使用后继结点继承根结点的关系 if(root->l!=NULL&&root->r!=NULL){ TNode* t=root->r;//找后继 while(t->l!=NULL){ t=t->l;//往左走 } root->data=t->data; root->r=delete2(root->r,t->data);//注意：删除后继也是采用递归 }else{//度为0或1:根指针指向唯一的子节结点，然后删除根结点 TNode* p=root; //根指针指向唯一的子节结点 if(root->l!=NULL) root=root->l; else root=root->r; //删除原来的根结点 free(p); p=NULL; } } ​ else if(x<root->data){//3.x<根结点数据 root->l=delete2(root->l,x); } ​ else{//3.x>根结点数据 root->r=delete2(root->r,x); } ​ return root; ​ }

效果演示

//中序遍历 void MediaOrderBT(BST t){ if(t==NULL) return; MediaOrderBT(t->l); printf("%d ",t->data); MediaOrderBT(t->r); } ​ ​ int main(){ BST t=NULL; int n,x;//n个数据 scanf("%d",&n); for(int i=0;i<n;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"); ​ //非递归删除 /* t=delete1(t,x); MediaOrderBT(t); */ //递归删除 t=delete1(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

感谢您的阅读，您的点赞是我坚持下去的动力