二叉树 源代码 txt格式

二叉树源代码#include<stdio.h> # include<stdlib.h> 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(key<t->data) 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(key<p->data) 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) ; } 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->data>key) 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)<-1) *i=dep1-dep2;/*用i值记录是否存在不平衡现象*/ if(dep1>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("\n\n---the menu of the opperation---\n"); /*主程序菜单*/ printf("\n 0: exit" ); printf("\n 1: inorder travel the tree"); printf("\n 2: the average search length for the tree"); printf("\n 3: delete"); printf("\n 4: judge the balance"); while(ch==ch) { printf("\n choose the opperation to continue:"); scanf("%d",&ch); switch(ch){ case 0: exit(0); /*0－－退出*/ case 1: printf(" The result of the inorder traverse is:\n "); inorderTraverse(&T); /*1－－中序遍历*/ break; case 2: s=0;j=0;i=0; calculateASL(&T,&s,&j,i); /*2－－计算平均查找长度*/ printf(" ASL=%d/%d",s,j); break; case 3: printf(" Please input the number you want to delete:"); 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("无%d ",num); break; case 4: i=0; balanceBST(T,&i); /*判断是否为平衡二插树*/ if(i==0) printf(" OK!The tree is a balanced tree!"); else printf(" NO!"); break; default: printf("Your input is wrong!please input again!\n"); break; /*输入无效字符*/ } } }