《二叉排序树与平衡二叉树.doc》由会员分享，可在线阅读，更多相关《二叉排序树与平衡二叉树.doc（11页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、#include #include#define maxsize 100#define EQ(a,b) (a)=(b)#define LT(a,b) (a)(b)#define LH 1 /左高#define EH 0 /等高#define RH -1 /右高typedef struct node /定义二叉树排序的结点int data; /数据域struct node *left,*right; /left指向左孩子，ringt指向右孩子们dnode;typedef struct BSTNode /定义二叉平衡树的结点int data;int bf; /结点的平衡因子struct BSTNo
2、de *left,*right;BSTNode,*BSTree;int n=0,m=0,total=0;int a30;int n1=0,m1=0,total1=0;int n2=0,m2=0,total2=0;void sort(dnode *t,int c) / 将c插入到二叉排序树t中dnode *p;if(c=t-data)if(t-right=NULL)p=(dnode *)malloc(sizeof(dnode);p-data=c;p-left=p-right=NULL;t-right=p;else sort(t-right,c);if(cdata)if(t-left=NULL)p
3、=(dnode *)malloc(sizeof(dnode);p-data=c;p-left=p-right=NULL;t-left=p;elsesort(t-left,c);dnode *creat() /创建二叉排序树dnode *ht;int c;char k;ht=(dnode *)malloc(sizeof(dnode);printf(输入数据，按回车键结束:);scanf(%d%c,&c,&k);ht-data=c;n+;ht-left=ht-right=NULL;if(k!=n)while(1) scanf(%d%c,&c,&k);sort(ht,c); n+; if(k=n)
4、break;return ht;void inorder(dnode *t) /中序遍历二叉排序树if(t!=NULL)m+;inorder(t-left);printf(%d ,t-data);total+=m;inorder(t-right);m-; void asl(int x) /计算平均查找长度float s;if(x=1)s=(float)total/n; printf(n: %d,total: %d,asl: %3.2fn,n,total,s);else if(x=2)s=(float)total1/n1; printf(n: %d,total: %d,asl: %3.2fn,n
5、1,total1,s);elses=(float)total2/n2; printf(n: %d,total: %d,asl: %3.2fn,n2,total2,s);void find(dnode *t,int x,dnode *a) /将数据域为x的结点的地址给a0,其父结点的地址给a1dnode *p,*q;p=t;if(p-data=x)a0=p;a1=NULL;return;for(;)if(xp-data)q=p;if(p-right=NULL)a0=a1=NULL;return;p=p-right;if(p-data=x)a0=p; a1=q; return;if(xdata)q
6、=p;if(p-left=NULL)a0=a1=NULL;return;p=p-left; if(p-data=x) a0=p; a1=q; return; dnode *del(dnode *t) /删除x结点dnode *p,*q,*s,*f,*a2;int flag=0,x;p=(dnode *)malloc(sizeof(dnode);f=(dnode *)malloc(sizeof(dnode);printf(enter x:);scanf(%d,&x);find(t,x,a);p=a0;f=a1;if(p=NULL)printf(NO FOUND!n);exit(0); if(p-
7、left=NULL) /左子树为空，重接右子树s=p-right;else if(p-right=NULL) /右子树为空，重接左子树s=p-left;else /左右子树均不空q=p;s=p-left;while(s-right!=NULL) /转左，然后向右走到尽头q=s;s=s-right;if(q=p) /结点P是倒数第二层次q-left=s-left; /重接*q的左子树elseq-right=s-left; /重接*q的右子树p-data=s-data;free(s);flag=1;if(flag=0)if(f=NULL)t=s;else if(f-left=p)f-left=s;
8、elsef-right=s;return t;void L_Rotate(BSTree &p) /对以*p为根的二叉排序树作左旋转处理，处理之后p指向新的树根结点，即旋转处理之前的右子树的根结点BSTree rc;rc=p-right; /rc指向*p的右子树根结点p-right=rc-left; /rc的左子树挂接为*p的右子树rc-left=p; /p指向新的根结点p=rc;void R_Rotate(BSTree &p) /对以*p为根的二叉排序树作右旋转处理，处理之后p指向新的树根结点，即旋转处理之前的左子树的根结点BSTree rc;rc=p-left; /rc指向*p的左子树根结点
9、p-left=rc-right; /rc的右子树挂接为*p的左子树rc-right=p; /p指向新的根结点p=rc;void LeftBalance(BSTree &T) /对以指针T所指结点为根的二叉树作左平衡旋转处理，本算法结束时，指针T指向新的根结点BSTree rc,rd;rc=T-left; /rc指向*T的左子树根结点switch(rc-bf) /检查*T的左子树平衡度，并作相应平衡处理case LH: /新结点插入在*T的左孩子的左子树上，要作单右旋转处理T-bf=rc-bf=EH;R_Rotate(T);break;case RH: /新结点插入在*T的左孩子的右子树上，要作
10、双旋转处理rd=rc-right; /rd指向*T的左孩子的右子树根switch(rd-bf) /修改*T及其左孩子的平衡因子case LH:T-bf=RH;rc-bf=EH;break;case EH:T-bf=rc-bf=EH;break;case RH: T-bf=EH;rc-bf=LH;break;rd-bf=EH;L_Rotate(T-left); /对*T的左孩子作左旋转平衡处理R_Rotate(T); /对*T作右旋转平衡处理void RightBalance(BSTree &T) /对以指针T所指结点为根的二叉树作右平衡旋转处理，本算法结束时，指针T指向新的根结点BSTree
11、rc,rd;rc=T-right; /rc指向*T的右子树根结点switch(rc-bf) /检查*T的右子树平衡度，并作相应平衡处理case RH: /新结点插入在*T的右孩子的右子树上，要作单左旋转处理T-bf=rc-bf=EH;L_Rotate(T);break;case LH: /新结点插入在*T的右孩子的左子树上，要作双旋转处理rd=rc-left; /rd指向*T的右孩子的左子树根switch(rd-bf) /修改*T及其右孩子的平衡因子case LH:T-bf=EH;rc-bf=RH;break;case EH:T-bf=rc-bf=EH;break;case RH:T-bf=L
12、H;rc-bf=EH;break;rd-bf=EH;R_Rotate(T-right); /对*T的左孩子作左旋转平衡处理L_Rotate(T); /对*T作右旋转平衡处理/若在平衡的二叉树排序树T中不存在和e有相同关键字的结点，则插入一个数据元素/为e的新结点，并返回1，否则返回0.若因插入而使二叉排序树失去平衡，则作平衡/旋转处理，布尔变量taller反映Tbool InsertAVL(BSTree &T,int e,bool &taller) if(!T)T=(BSTree)malloc(sizeof(BSTNode);T-data=e;T-left=T-right=NULL;T-bf=
13、EH;taller=true;elseif(EQ(e,T-data) /树中已存在和e有相同关键字的结点则不再插入taller=false;return 0;if(LT(e,T-data) /应继续在*T的左子树中进行搜索if(!InsertAVL(T-left,e,taller) /未插入return 0;if(taller) /已插入到*T的左子树中且左子树“长高”switch(T-bf) /检查*T的平衡度case LH: /原本左子树比右子树，需要作左平衡处理LeftBalance(T);taller=false;break;case EH: /原本左、右子树等高，现因左子树增高而使树
14、增高T-bf=LH;taller=true;break;case RH: /原本右子树比左子树高，现左、右子树等高T-bf=EH;taller=false;break;else /应继续在*T的右子树中进行搜索if(!InsertAVL(T-right,e,taller) /未插入return 0;if(taller) /以插入到*T的右子树且右子树长高switch(T-bf) /检查*T的平衡度case LH: /原本左子树比右子树高，现左、右子树等高T-bf=EH;taller=false;break;case EH: /原本左、右子树等高，现因右子树增高而使树增高T-bf=RH;tall
15、er=true;break;case RH: /原本右子树比左子树高，需要作右平衡处理RightBalance(T);taller=false;break;return 1;BSTNode *creat_balance(BSTNode *T) /建立平衡二叉树int a,f=1;char k;bool taller=false; printf(输入数列，按回车键结束:);scanf(%d%c,&a,&k);while(f=1) InsertAVL(T,a,taller);n1+;taller=false;if(k=n) f=0;elsescanf(%d%c,&a,&k);return T;vo
16、id inorder_balance(BSTNode *T) /中序遍历平衡二叉树if(T!=NULL)m1+; inorder_balance(T-left);printf(%d ,T-data);total1+=m1;inorder_balance(T-right);m1-;dnode *create1() /建立二叉排序树（数组）dnode *t;int i=0;t=(dnode*)malloc(sizeof(dnode);t-left=NULL;t-right=NULL;t-data=ai;i+;for(i=1;ileft);printf(%d ,t-data);total2+=m2;
17、inoder_1(t-right);m2-;main()dnode *h,*h2;BSTree T;bool taller=false;int select;T=(BSTree)malloc(sizeof(BSTNode);T=NULL;doprintf(1.用链表作存储结构，建立二叉排序树。n);printf(2.中序遍历二叉排序树。n);printf(3.计算二叉排序树的平均查找长度。n);printf(4.删除x结点。n);printf(5.建立平衡二叉树n);printf(6.计算平衡二叉树的平均查找长度。n);printf(7.用数组作存储结构，建立二叉排序树。n);printf(8
18、.中序遍历二叉排序树（数组作存储结构）。n);printf(9.计算二叉排序树的平均查找长度（数组作存储结构）。n); printf(10.删除x结点（数组作存储结构）。n);printf(0.退出。n);printf(n选择:);scanf(%d,&select);switch(select)case 1:h=creat();printf(n);break;case 2:printf(中序遍历:); if(!h) printf(空树！); else inorder(h); printf(nn);break;case 3:asl(1);printf(n);break;case 4:h=del(
19、h);printf(结果:); if(!h) printf(空树！); else inorder(h); printf(nn);break;case 5:T=creat_balance(T); printf(中序遍历:); inorder_balance(T); printf(nn);break;case 6:asl(2);printf(n);break;case 7:printf(输入数据,按回车键结束:);shuzu(a);h2=create1();printf(n);break;case 8:printf(中序遍历:); if(!h2) printf(空树！); else inoder_1(h2); printf(nn);break;case 9:asl(3);printf(n);break;case 10:h2=del(h2);printf(结果:); if(!h2)printf(空树！);elseinorder(h2);printf(nn);break;case 0:break;while(select=1&select=10);