二叉樹功能代碼

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);/* 求葉子結(jié)點數(shù)目。*/void Leafnum(BTNode *bt)if(bt) if(bt-lchild=NULL&bt-rchild=NULL) count+;Leafnum(bt-lchild); Leafnum(bt-rchild);/* 求二叉樹總結(jié)點數(shù)目 。*/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);/* 二叉樹的排序總函數(shù)。*/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、迎來到二叉排序樹系統(tǒng)!n）；printf（二叉排序樹 n）；printf（=n）；printf（1.建立二叉排序樹n）；printf（2.插入一個元素n ）；printf（3.刪除一個元素n ）；printf(4.查找一個元素n );printf(5.求葉子結(jié)點數(shù)目n );printf(6.求二叉樹總結(jié)點數(shù)目n );printf(7.求樹深度n );printf(8.二叉樹的排序n );printf(0.返回n);printf(=n);printf(請輸入序號(0-8)選擇要進行的操作：n);/*主函數(shù)*/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(請輸入要生成二叉排序樹的關(guān)鍵字的個數(shù)：n);scanf(%d,&n);printf(請輸入二叉排序樹的各個關(guān)鍵字：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