二叉排序树与平衡二叉树.doc

#include stdio.h #includestdlib.h #define maxsize 100 #define EQ(a,b) ((a)==(b)) #define LT(a,b) ((a)(b)) #define LQ(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 BSTNode *left,*right; }BSTNode,*BSTree; int n=0,m=0,total=0; int a[30]; 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(ct-data) if(t-left==NULL) { p=(dnode *)malloc(sizeof(dnode)); p-data=c; p-left=p-right=NULL; t-left=p; } else sort(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) 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.2f\n,n,total,s); } else if(x==2) { s=(float)total1/n1; printf(n: %d,total: %d,asl: %3.2f\n,n1,total1,s); } else { s=(float)total2/n2; printf(n: %d,total: %d,asl: %3.2f\n,n2,total2,s); } } void find(dnode *t,int x,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(xp-data) { q=p; if(p-right==NULL) { a[0]=a[1]=NULL; return; } p=p-right; if(p-data==x) { a[0]=p; a[1]=q; return; } } if(xp-data) {