二叉树功能代码

1、#includestdio.h #includestdlib.h #includemalloc.h #define MAXSIZE 100 int count=0;typedef int KeyType; typedef struct treenode KeyType key;struct treenode *lchild,*rchild; BTNode;/* 在二叉树中插入一个元素。*/BTNode *BSTInsert(BTNode *bt,KeyType k) BTNode *f,*p=bt; while(p!=NULL) f=p; if(p-keyk) p=p-lchild;else

2、p=p-rchild;p=(BTNode *)malloc(sizeof(BTNode); p-key=k;p-lchild=p-rchild=NULL; if(bt=NULL)bt=p;else if(kkey) f-lchild=p;elsef-rchild=p; return bt;/* 建立二叉树。*/BTNode *CreateBST(KeyType str,int n)int i=0;BTNode *bt=NULL;while(ikey); if(bt-lchild!=NULL) printf();DispBStree(bt-lchild);if(bt-rchild!=NULL)p

3、rintf(,);DispBStree(bt-rchild);printf();elseif(bt-rchild!=NULL)printf();DispBStree(bt-lchild);if(bt-rchild!=NULL)printf(,);DispBStree(bt-rchild);printf();/*在二叉树中删除一个元素。*/BTNode *BSTDelete(BTNode *bt,KeyType k)BTNode *p,*f,*s,*q;p=bt;f=NULL;while(p)if(p-key=k)break;f=p;if(p-keyk)p=p-lchild;elsep=p-rc

4、hild;if(p=NULL)return bt;if(p-lchild=NULL)if(f=NULL)bt=p-rchild;else if(f-lchild=p)f-lchild=p-rchild;elsef-rchild=p-rchild;free(p);elseq=p;s=p-lchild;while(s-rchild)q=s;s=s-rchild;if(q=p)q-lchild=s-lchild;elseq-rchild=s-lchild; p-key=s-key; free(s); return bt;/* 在二叉树中查找一个元素。*/BTNode *BSTSearch(BTNod

5、e *bt,KeyType k) if(bt=NULL) return(NULL);elseif(k=bt-key) return(bt);else if(kkey)return(BSTSearch(bt-lchild,k);elsereturn(BSTSearch(bt-rchild,k);/* 求叶子结点数目。*/void Leafnum(BTNode *bt)if(bt) if(bt-lchild=NULL&bt-rchild=NULL) count+;Leafnum(bt-lchild); Leafnum(bt-rchild);/* 求二叉树总结点数目 。*/void Nodenum(

6、BTNode *bt)if(bt)count+;Nodenum(bt-lchild);Nodenum(bt-rchild);/*求树深度。*/int TreeDepth(BTNode *bt)int ldep=0,rdep=0;if(bt=NULL)return 0;elseldep=TreeDepth(bt-lchild); rdep=TreeDepth(bt-rchild); if(ldeprdep)return ldep+1;elsereturn rdep+1;/* 前序遍历二叉树，递归方法。*/void PreOrder1(BTNode *bt)if(bt=NULL)return;el

7、seprintf(%d,bt-key); printf(,);PreOrder1(bt-lchild);PreOrder1(bt-rchild); /*前序遍历二叉树，非递归方法。*/void PreOrder2(BTNode *bt)BTNode *p=bt;BTNode *stack30;int num=0;while(NULL!=p|num0)while(NULL!=p)printf(%d ,p-key);stacknum+=p;p=p-lchild;num-;p=stacknum;p=p-rchild;printf(n);/*中序遍历二叉树，递归方法。*/void InOrder1(B

8、TNode *bt)if(bt=NULL)return;elseInOrder1(bt-lchild); printf(%d ,bt-key); printf(,);InOrder1(bt-rchild);/*中序遍历二叉树，非递归方法，使用栈*/void InOrder2(BTNode *bt)BTNode *p=bt;int num=0;BTNode *stack30; while(NULL!=p|num0) while(NULL!=p)stacknum+=p;p=p-lchild;num-; p=stacknum; printf(%d ,p-key); p=p-rchild;printf

9、(n);/* 后序遍历二叉树，递归方法。*/void PostOrder1(BTNode *bt)if(bt=NULL)return;elsePostOrder1(bt-lchild);PostOrder1(bt-rchild);printf(%d ,bt-key); printf(,);/* 后序遍历二叉树，非递归方法*/void PostOrder2(BTNode *bt)BTNode *p=bt;BTNode *stack30;int num=0;BTNode *have_visited=NULL;while(NULL!=p|num0)while(NULL!=p)stacknum+=p;

10、p=p-lchild;p=stacknum-1;if(NULL=p-rchild|have_visited=p-rchild)printf(%d ,p-key);num-;have_visited=p;p=NULL;elsep=p-rchild;printf(n);/*层次遍历二叉树，非递归方法。*/void LevelOrder(BTNode *bt)int f,r;BTNode *p,*qMAXSIZE;p=bt;if(p!=NULL)f=1;qf=p;r=2;while(f!=r)p=qf;printf(%d,p-key);printf(,);if(p-lchild!=NULL)qr=p

11、-lchild;r=(r+1)%MAXSIZE;if(p-rchild!=NULL)qr=p-rchild; r=(r+1)%MAXSIZE;f=(f+1)%MAXSIZE; void menuOrder()printf(二叉树的排序n);printf(=n);printf(1.前序遍历二叉树，递归n);printf(2.前序遍历二叉树，非递归n);printf(3.中序遍历二叉树，递归n);printf(4.中序遍历二叉树，非递归n);printf(5.后序遍历二叉树，递归n);printf(6.后序遍历二叉树，非递归n);printf(7.层次遍历二叉树，非递归n);printf(0.返回

12、n);printf(=n);printf（请输入序号（0-7）选择要进行的操作:n);/* 二叉树的排序总函数。*/void OrderBTree(BTNode *bt)int menux;menuOrder(); scanf(%d,&menux);doswitch(menux)case 1:printf(二叉树的递归的前序遍历为：); PreOrder1(bt);break;case 2:printf(二叉树的非递归的前序遍历为：)；PreOrder2(bt);break；case 3:printf(二叉树的递归的中序遍历为：)；InOrder1(bt)；break；case 4:print

13、f(二叉树的非递归的中序遍历为：)；InOrder2(bt)；break；case 5:printf(二叉树的递归的后序遍历为：)；PostOrder1(bt)；break；case 6:printf(二叉树的非递归的后序遍历为：)；PostOrder2(bt)；break；case 7:printf(二叉树的层次遍历序列为：)；LevelOrder(bt)；break；case 0:return；break；default:printf(输入选项错误，请重新输入(0-7)!);menuOrder()；scanf(%d,&menux)；while(1)； void menu（）printf（欢

14、迎来到二叉排序树系统!n）；printf（二叉排序树 n）；printf（=n）；printf（1.建立二叉排序树n）；printf（2.插入一个元素n ）；printf（3.删除一个元素n ）；printf(4.查找一个元素n );printf(5.求叶子结点数目n );printf(6.求二叉树总结点数目n );printf(7.求树深度n );printf(8.二叉树的排序n );printf(0.返回n);printf(=n);printf(请输入序号(0-8)选择要进行的操作：n);/*主函数*/main()KeyType str100;BTNode *bt;int i,n,x;ch

15、ar ch1,a;int ch2;ch1=y;while(ch1=y|ch1=Y)menu();scanf(%d,&ch2);getchar();switch(ch2)case 1:printf(请输入要生成二叉排序树的关键字的个数：n);scanf(%d,&n);printf(请输入二叉排序树的各个关键字：n); for(i=0;in;i+) scanf(%d,&stri);bt=CreateBST(str,n);printf(二叉树建立成功!)；printf(建立的二叉排序树广义表表示法为：)；DispBStree(bt);break;case 2:printf (请输入要插入的元素值：)

16、；scanf(%d,&x);bt=BSTInsert(bt,x);printf(插入后的二叉排序树为：);DispBStree(bt); break;case 3:printf(请输入要删除的元素：);scanf(%d,&x); bt=BSTDelete(bt,x);printf(删除元素d后的二叉排序树为：,x);DispBStree(bt);break;case 4:printf(请输入查找的元素值：)； scanf(%d,&x);if(BSTSearch(bt,x)!=NULL)printf(在二叉排序树中存在元素%d!,x);elseprintf(在二叉排序树中不存在元素%d!,x); break;case 5:count=0;Leafnum(bt); printf(该二叉树有d(叶子。,count); break;case 6:c