课程设计 排序二叉树.doc

1、#include# includetypedef struct Tnodeint data; /*输入的数据*/struct Tnode *lchild,*rchild; /*结点的左右指针，分别指向结点的左右孩子*/*node,BSTnode;searchBST(node t,int key,node f,node *p) /*查找函数*/if(!t) *p=f;return (0); /*查找不成功*/else if(key=t-data) *p=t;return (1); /*查找成功*/else if(keydata) searchBST(t-lchild,key,t,p); /*在左

2、子树中继续查找*/else searchBST(t-rchild,key,t,p); /*在右子树中继续查找*/insertBST(node *t,int key) /*插入函数*/node p=NULL,s=NULL;if(!searchBST(*t,key,NULL,s-data=key;s-lchild=s-rchild=NULL;if(!p) *t=s; /*被插结点*s 为新的根结点*/else if(keydata) p-lchild=s;/*被插结点*s 为左孩子*/else p-rchild=s; /*被插结点*s 为右孩子*/return (1);else return (0

3、);/*树中已有关键字相同的结点，不再插入*/inorderTraverse(node *t) /*中序遍历函数*/if(*t)if(inorderTraverse( /*输出根结点*/if(inorderTraverse( /*中序遍历根的右子树*/return(1) ;pnorderTraverse(node *t) /*先序遍历函数*/if(*t) printf(“%d “,(*t)-data); if(pnorderTraverse( if(pnorderTraverse( return(1) ;qnorderTraverse(node *t) /*后序遍历函数*/if(*t)if(q

4、norderTraverse( if(qnorderTraverse( printf(“%d “,(*t)-data); return(1) ;calculateASL(node *t,int *s,int *j,int i) /*计算平均查找长度 */if(*t)i+; /*i 记录当前结点的在当前树中的深度*/*s=*s+i; /*s 记录已遍历过的点的深度之和*/if(calculateASL( /*j 记录树中结点的数目*/if(calculateASL( return(1);else return(1); node Delete(node t,int key) /*删除函数*/nod

5、e p=t,q=NULL,s,f;while(p!=NULL) /*查找要删除的点*/if(p-data=key) break;q=p;if(p-datakey) p=p-lchild;else p=p-rchild;if(p=NULL) return t; /*查找失败*/if(p-lchild=NULL) /*p 指向当前要删除的结点*/if(q=NULL) t=p-rchild; /*q 指向要删结点的父母*/else if(q-lchild=p) q-lchild=p-rchild; /*p 为 q 的左孩子*/else q-rchild=p-rchild;/*p 为 q 的右孩子*/

6、free(p);else /*p 的左孩子不为空*/f=p;s=p-lchild;while(s-rchild) /*左拐后向右走到底*/f=s;s=s-rchild;if(f=p) f-lchild=s-lchild; /*重接 f 的左子树 */else f-rchild=s-lchild; /*重接 f 的右子树*/p-data=s-data;free (s);return t;int balanceBST(node t,int *i) /*判断是否为平衡二叉树的函数*/int dep1,dep2;if(!t) return(0);else dep1=balanceBST(t-lchil

7、d,i);dep2=balanceBST(t-rchild,i);if(dep1-dep2)1|(dep1-dep2)dep2) return(dep1+1);else return(dep2+1);void main()node T=NULL;int num;int s=0,j=0,i=0;int ch=0;node p=NULL;printf(“please input a list of numbers end with zero:“);doscanf(“%d“,if(!num) printf(“you have finished your input!n“);else insertBS

8、T(while(num);printf(“nn-the menu of the opperation-n“); /*主程序菜单*/printf(“n 0: exit“ );printf(“n 1: 中序遍历“);printf(“n 2: 先序遍历“);printf(“n 3: 后序遍历“);printf(“n 4: 计算平均查找长度“);printf(“n 5: 删除某个结点“);printf(“n 6: 判断是否为平衡二插树“);while(ch=ch)printf(“n choose the opperation to continue:“);scanf(“%d“,switch(ch)ca

9、se 0: exit(0); /*0退出*/case 1: printf(“ 中序遍历:n “);inorderTraverse( /*1中序遍历 */break;case 2: printf(“ 先序遍历:n “);pnorderTraverse( /*1中序遍历*/break;case 3: printf(“ 后序遍历:n “);qnorderTraverse( /*1中序遍历*/break;case 4: s=0;j=0;i=0;calculateASL( /*2计算平均查找长度 */printf(“ ASL=%d/%d“,s,j);break;case 5: printf(“ 输入您所

10、需要删除的节点:“);scanf(“%d“, /*3删除某个结点*/if(searchBST(T,num,NULL,printf(“ You have delete the number successfully!n “);inorderTraverse(else printf(“ No node %d you want to delete!“,num);break;case 6: i=0;balanceBST(T, /*判断是否为平衡二插树*/if(i=0) printf(“ 本棵树为平衡二叉树 !“);else printf(“ NO!“);break;default: printf(“Your input is wrong!please input again!n“);break; /*输入无效字符*/