课程设计 排序二叉树.doc

#include# include typedef struct Tnode int 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); /*在左子树中继续查找*/else searchBST(t-rchild,key,t,p); /*在右子树中继续查找*/ insertBST(node *t,int key) /*插入函数*/ node p=NULL,s=NULL; if(!searchBST(*t,key,NULL,&p) /*查找不成功*/ s=(node)malloc(sizeof(BSTnode); 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);/*树中已有关键字相同的结点，不再插入*/ inorderTraverse(node *t) /*中序遍历函数*/ if(*t) if(inorderTraverse(&(*t)-lchild) /*中序遍历根的左子树*/ printf(%d ,(*t)-data); /*输出根结点*/ if(inorderTraverse(&(*t)-rchild); /*中序遍历根的右子树*/ return(1) ;pnorderTraverse(node *t) /*先序遍历函数*/ if(*t) printf(%d ,(*t)-data); if(pnorderTraverse(&(*t)-lchild) ; if(pnorderTraverse(&(*t)-rchild); return(1) ;qnorderTraverse(node *t) /*后序遍历函数*/ if(*t) if(qnorderTraverse(&(*t)-lchild) ; if(qnorderTraverse(&(*t)-rchild); 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(&(*t)-lchild,s,j,i)/*计算左子树的ASL*/ (*j)+; /*j记录树中结点的数目*/ if(calculateASL(&(*t)-rchild,s,j,i) /*计算右子树的ASL*/ i-; return(1); else return(1); node Delete(node t,int key) /*删除函数*/ node 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的右孩子*/ 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-lchild,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:); do scanf(%d,&num); if(!num) printf(you have finished your input!n); else insertBST(&T,num); 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,&ch); switch(ch) case 0: exit(0); /*0退出*/ case 1: printf( 中序遍历:n ); inorderTraverse(&T); /*1中序遍历*/ break;case 2: printf( 先序遍历:n ); pnorderTraverse(&T); /*1中序遍历*/ break;case 3: printf( 后序遍历:n ); qnorderTraverse(&T); /*1中序遍历*/ break; case 4: s=0;j=0;i=0; calculateASL(&T,&s,&j,i); /*2计算平均查找长度*/ printf( ASL=%d/%d,s,j); break; case 5: printf( 输入您所需要删除的节点:); scanf(%d,&num); /*3删除某个结点*/ if(searchBST(T,num,NULL,&p) T=Delete(T,num); printf( You have delete the number successfully!n ); inorderTraverse(&T); else printf( No node %d you want to delete!,num); break; case 6: