资源描述：
《二叉排序树与平衡二叉树》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、#include#include#definemaxsize100#defineEQ(a,b)((a)==(b))#defineLT(a,b)((a)<(b))#defineLQ(a,b)((a)>(b))#defineLH1//左高#defineEH0//等高#defineRH-1//右高typedefstructnode//定义二叉树排序的结点{intdata;//数据域structnode*left,*right;//left指向左孩子，ringt指向右孩子们}dnode;t
2、ypedefstructBSTNode//定义二叉平衡树的结点{intdata;intbf;//结点的平衡因子structBSTNode*left,*right;}BSTNode,*BSTree;intn=0,m=0,total=0;inta[30];intn1=0,m1=0,total1=0;intn2=0,m2=0,total2=0;voidsort(dnode*t,intc)//将c插入到二叉排序树t中{dnode*p;if(c>=t->data)if(t->right==NULL){p=(dnode*)mall
3、oc(sizeof(dnode));p->data=c;p->left=p->right=NULL;t->right=p;}elsesort(t->right,c);if(cdata)if(t->left==NULL){p=(dnode*)malloc(sizeof(dnode));p->data=c;p->left=p->right=NULL;t->left=p;}elsesort(t->left,c);}dnode*creat()//创建二叉排序树{dnode*ht;intc;chark;ht=(dnode
4、*)malloc(sizeof(dnode));printf("输入数据，按回车键结束:");scanf("%d%c",&c,&k);ht->data=c;n++;ht->left=ht->right=NULL;if(k!='')while(1){scanf("%d%c",&c,&k);sort(ht,c);n++;if(k=='')break;}returnht;}voidinorder(dnode*t)//中序遍历二叉排序树{if(t!=NULL){m++;inorder(t->left);printf("
5、%d",t->data);total+=m;inorder(t->right);m--;}}voidasl(intx)//计算平均查找长度{floats;if(x==1){s=(float)total/n;printf("n:%d,total:%d,asl:%3.2f",n,total,s);}elseif(x==2){s=(float)total1/n1;printf("n:%d,total:%d,asl:%3.2f",n1,total1,s);}else{s=(float)total2/n2;printf(
6、"n:%d,total:%d,asl:%3.2f",n2,total2,s);}}voidfind(dnode*t,intx,dnode*a[])//将数据域为x的结点的地址给a[0],其父结点的地址给a[1]{dnode*p,*q;p=t;if(p->data==x){a[0]=p;a[1]=NULL;return;}for(;;){if(x>p->data){q=p;if(p->right==NULL){a[0]=a[1]=NULL;return;}p=p->right;if(p->data==x){a[0]=
7、p;a[1]=q;return;}}if(xdata){q=p;if(p->left==NULL){a[0]=a[1]=NULL;return;}p=p->left;if(p->data==x){a[0]=p;a[1]=q;return;}}}}dnode*del(dnode*t)//删除x结点{dnode*p,*q,*s,*f,*a[2];intflag=0,x;p=(dnode*)malloc(sizeof(dnode));f=(dnode*)malloc(sizeof(dnode));printf("en
8、terx:");scanf("%d",&x);find(t,x,a);p=a[0];f=a[1];if(p==NULL){printf("NOFOUND!");exit(0);}if(p->left==NULL)//左子树为空，重接右子树s=p->right;elseif(p->right==NULL)//右子树为空，重接左子
