二叉樹其他典型算法

1、題目：假設(shè)二叉樹采用二叉鏈表結(jié)構(gòu)。設(shè)計(jì)并實(shí)現(xiàn)如下算法：輸入某棵二叉樹 的廣義表形式，建立該二叉樹，并按層次遍歷該二叉樹。一、需求分析用戶可以根據(jù)自己的需求分別輸入任意的一個(gè)以廣義表表示的二叉樹，并且以此創(chuàng)建一 個(gè)二叉樹。通過已有的二叉樹用層次遍歷該樹，并輸出。并且以廣義表的形式輸出該二叉樹程序執(zhí)行的命令包括：輸入廣義表 (2)構(gòu)造二叉樹T(2)層次遍歷二叉樹(3)二叉樹以廣義表的形式輸出(4)求二叉樹的結(jié)點(diǎn)數(shù)(輔助功能，為了輸出二叉樹)二、概要設(shè)計(jì)為實(shí)現(xiàn)上述算法，需要鏈表的抽象數(shù)據(jù)類型：ADT Binarytree 數(shù)據(jù)對(duì)象：D是具有相同特性的數(shù)據(jù)元素的集合數(shù)據(jù)關(guān)系R：若D為空集，則R為空集，

2、稱binarytree為空二叉樹；若D不為空集，則R為H，H是如下二元關(guān)系；在D中存在唯一的稱為根的數(shù)據(jù)元素root，它在關(guān)系H下無前驅(qū)；若 Droot不為空，則存在Droot = D1，Dr，且D1HDr 為空集;若D1不為空，則D1中存在唯一的元素x1，eH，且存在D1 上的關(guān)系H1是H的子集；若Dr不為空集，則Dr中存在唯一的元素Xr， H，且存在 Dr 上的關(guān)系 Hr 為 H 的子集；H=,H1,Hr;(D1,H1)是一顆符合本定義的二叉樹，稱為根的左子樹，(Dr,Hr)是一顆符合本定義的二叉樹，稱為根的右子樹。基本操作：Creatbitree(&S， definition)初始條件：

3、definition給出二叉樹S的定義操作結(jié)果：按definition構(gòu)造二叉樹S counter(T)初始條件：二叉樹T已經(jīng)存在操作結(jié)果：返回二叉樹的總的結(jié)點(diǎn)數(shù) Printbitree (T)初始條件：二叉樹T已存在操作結(jié)果：以廣義表的形式輸出T Clearbintree(S)初始條件：二叉樹S已經(jīng)存在操作結(jié)果：將二叉樹S清為空樹Bitreeempty(S)初始條件：二叉樹S已經(jīng)存在操作結(jié)果：若S為空二叉樹，則返回TRUE，否則返回FALSEBitreedepth(S,&e)初始條件：二叉樹S已經(jīng)存在操作結(jié)果：返回S的深度Parent(S)初始條件：二叉樹S已經(jīng)存在，e是S中的某個(gè)結(jié)點(diǎn)操作結(jié)

4、果：若e是T的非根結(jié)點(diǎn)，則返回它的雙親，否則返回空 Preordertraverse(S)初始條件：二叉樹S已經(jīng)存在，Visit是對(duì)結(jié)點(diǎn)操作的應(yīng)用函數(shù)。操作結(jié)果：先序遍歷S，對(duì)每個(gè)結(jié)點(diǎn)調(diào)用函數(shù)visit 一次且僅一次。一旦visit失敗，則操作失敗。Inordertraverse (S,&e)初始條件：二叉樹S已經(jīng)存在，Visit是對(duì)結(jié)點(diǎn)操作的應(yīng)用函數(shù)。操作結(jié)果：中序遍歷S，對(duì)每個(gè)結(jié)點(diǎn)調(diào)用函數(shù)visit 一次且僅一次。一旦visit失敗，則操作失敗。Postordertraverse (&S,e)初始條件：二叉樹S已經(jīng)存在，Visit是對(duì)結(jié)點(diǎn)操作的應(yīng)用函數(shù)。操作結(jié)果：后序遍歷S，對(duì)每個(gè)結(jié)點(diǎn)調(diào)用

5、函數(shù)visit 一次且僅一次。一旦visit失敗，則操作失敗。ADT Binarytree本程序有三個(gè)模塊：主程序模塊main()初始化；接受命令；顯示結(jié)果；廣義表形式建樹的模塊：主要建立一棵二叉樹；層次遍歷模塊：輸出中序遍歷的結(jié)果；(4)輸出二叉樹模塊：廣義表輸出二叉樹。三、詳細(xì)設(shè)計(jì)1 .元素類型，結(jié)點(diǎn)類型/*定義二叉樹*/typedef struct bitree char node;struct bitree *lchild,*rchild;bitree;/*定義隊(duì)列元素類型*/typedef struct qnode bitree *q;qnode;/*定義隊(duì)列*/typedef st

6、ruct queue qnode *base;int front;int rear;int size;queue;/*全局變量*/bitree *T;queue *Q;int i=0,a;char s100;/*存放廣義表數(shù)組*/對(duì)抽象數(shù)據(jù)類型中的部分基本操作的偽碼算法如下：/*廣義表創(chuàng)建二叉樹*/struct bitree *creatbitree2(bitree *T) struct bitree *r;struct bitree *a100; /*定義數(shù)組棧，存放根節(jié)點(diǎn)*/char ch;int top = -1;int k;/*用k作為處理結(jié)點(diǎn)的左子樹和右子樹，k = 1處理左子樹，k

7、 = 2處理右子樹 */int j = 0;T=NULL;while(sj != 0) ch=sj;switch(ch) case ,#: break; /* #表示沒有左孩子或右孩子*/case (: if(top = 99) printf(stack size full！ n)； exit(1); top+;atop = r;k = 1; break;case ): if(top = -1) printf(btree biao error!n)； exit(1); top-; break;case ,: k = 2; break;default: r = (bitree *)malloc(

8、sizeof(bitree);r-node = ch;r-lchild = r-rchild = NULL;if(T = NULL) T = r; else if( k = 1) atop-lchild = r; else atop-rchild = r; j+;return T;/*求二叉樹的結(jié)點(diǎn)總數(shù)*/int counter(struct bitree *T) int num1,num2,num;if(T=NULL) return 0;else num1=counter(T-lchild);num2=counter(T-rchild);num=num1+num2+1;return num;

9、/*創(chuàng)建空隊(duì)列*/queue *initqueue() Q-base=(qnode *)malloc(MAX*sizeof(qnode);Q-front=Q-rear=0;Q-size=MAX;return Q;/*判斷隊(duì)列是否為空*/int emptyqueue(queue *q) if(q-front=q-rear) return 1;else return 0;/*入隊(duì)列*/queue *enqueue(queue *q,bitree *p) q-baseq-rear.q=p;q-rear+;return q;/*出隊(duì)列*/bitree *dequeue(queue *q) int n;

10、if(q-front=q-rear) printf(the queue is NULL!n)； return 0;n=q-front;q-front+;return (q-basen.q);/*層次遍歷*/void levelorder(bitree *t) bitree *p;Q=initqueue();if(t!=NULL) enqueue(Q,t);while(!emptyqueue(Q) p=dequeue(Q);visit(p-node);if(p-lchild!=NULL)enqueue(Q,p-lchild);if(p-rchild!=NULL) enqueue(Q,p-rchi

11、ld);/*廣義表形式輸出二叉樹*/void printBTree( bitree *T) if(T!= NULL) /*樹為空時(shí)結(jié)束遞歸，否則執(zhí)行如下操作*/ printf(%c，T-node); /* 輸出根結(jié)點(diǎn)的值 */ if(T-lchild != NULL | T-rchild!= NULL) printf()；printBTree(T-lchild);if(T-rchild != NULL) printf(,)； printBTree(T-rchild);printf()；主函數(shù)和其他函數(shù)的偽碼算法int main(void) int sum;printf(nninput guan

12、g yi biao :n)； gets(s);/*輸入廣義表*/T=creatbitree2(T);/*廣義表創(chuàng)建樹 */printf(nnthe bitree de zong jie dian shu :n)； a=counter(T);printf(a=%dn，a); /*輸出樹的總結(jié)點(diǎn)數(shù)*/ printf(nnouput the btree biaon)； printBTree(T);/*二叉樹以廣義表輸出*/printf(nnceng ci bian li result:n)； levelorder(T);/*層次遍歷的結(jié)果*/getch();return 0;/*訪問元素*/void

13、 visit(char ch)if(i!=(a-1) printf(%c-,ch);i+；else printf(%c,ch);printf(n)；函數(shù)調(diào)用關(guān)系maincreatbitree2printBTreecounterlevelorderinitqueue dequeue enqueue visit四、調(diào)試分析開始的時(shí)候輸入字符串用的是scanf (” s” ,s)，因此在輸入廣義表的時(shí)候，發(fā)現(xiàn)空格以后的字符串沒有。通過查閱C語(yǔ)言書籍知道，利用scanf函數(shù)輸入字符串時(shí)，字符串 里不能包含空格，最后用gets函數(shù)代替scanf函數(shù)輸入字符串得以解決空格問題。在利用自定義的類型里的元素時(shí)

14、，不能很好的引用，特別是“”和“-”的區(qū)別。因此 寫q-baseq-rear.q=p;語(yǔ)句就用了比較長(zhǎng)的時(shí)間。在編寫層次遍歷函數(shù)比較容易，但是在用廣義表創(chuàng)建二叉樹的函數(shù)就比較吃力，主要是在 于遞歸不是很熟悉。還有開始時(shí)沒有想到要利用棧存放根節(jié)點(diǎn)，只想到遞歸，導(dǎo)致函數(shù)不 能實(shí)現(xiàn)其功能。最后在查考了資料才有了源程序中的creatbitree2 ()函數(shù)。算法的時(shí)空分析各操作的算法時(shí)間復(fù)雜度比較合理initqueue，emptyqueue，enqueue，dequeue，visit 為 O(1) ； creatbitree2, levelorder， counter， printBTree 為 O(

15、n),注：n為二叉樹的總結(jié)點(diǎn)數(shù)。本次實(shí)驗(yàn)采用數(shù)據(jù)抽象的程序設(shè)計(jì)方法，將程序化為三層次結(jié)構(gòu)，設(shè)計(jì)時(shí)思路清晰，使調(diào)試也較順利，各模塊有較好的可重用性。五、用戶手冊(cè)1本程序的運(yùn)行環(huán)境為windows xp操作系統(tǒng)，并且在TC2.0中運(yùn)行，執(zhí)行文件為Exp7.c；2.在輸入廣義表的時(shí)候，#表示為空，例如輸入廣義表：(A(B(D (札G),E (札H),C (札F(I,#).進(jìn)入演示程序后，完成編譯，再點(diǎn)擊超級(jí)工具集里的中文DOS環(huán)境運(yùn)行選項(xiàng)，進(jìn)入DOS環(huán)境中，用戶根據(jù)需求鍵入相應(yīng)的數(shù)據(jù)，可以看到相應(yīng)的結(jié)果。六、測(cè)試結(jié)果若想創(chuàng)建二叉樹:則因在 dos 界面輸入字符串(A(B(D(#,G),E(#,H),

16、C(#,F(I,#)，所以在 win tc 中運(yùn)行得到U的結(jié)果如下圖所示：運(yùn)行的結(jié)果是：結(jié)點(diǎn)的總數(shù)是9輸出的二叉樹廣義表為A(B(D(,G),E(,H),C(,F(I) 層次遍歷的結(jié)果 A-B-C-D-E-F-G-H-I七、附錄：源程序#include#include#include#define NULL 0#define MAX 100/*定義二叉樹*/typedef struct bitree char node;struct bitree *lchild,*rchild;bitree;/*定義隊(duì)列元素類型*/typedef struct qnode bitree *q;qnode;/*

17、定義隊(duì)列*/typedef struct queue qnode *base;int front;int rear;int size;queue;/*全局變量*/bitree *T;queue *Q;int i=0,a;char s100;/*存放廣義表數(shù)組*/*廣義表創(chuàng)建二叉樹*/struct bitree *creatbitree2(bitree *T) struct bitree *r;struct bitree *a100; /*定義數(shù)組棧，存放根節(jié)點(diǎn)*/ char ch;int top = -1;intk; /*用k作為處理結(jié)點(diǎn)的左子樹和右子樹，k=1處理左子樹，k = 2處理右子樹

18、*/ int j = 0;T=NULL;while(sj != 0) ch=sj;switch(ch) case ,#: break; /* #表示沒有左孩子或右孩子*/ case (: if(top = 99) printf(stack size full！ n)； exit(1); top+;atop = r;k = 1; break;case ): if(top = -1) printf(btree biao error!n)； exit(1); top-;break;case ,: k = 2; break;default: r = (bitree *)malloc(sizeof(bi

19、tree);r-node = ch;r-lchild = r-rchild = NULL;if(T = NULL) T = r; else if( k = 1) atop-lchild = r; else atop-rchild = r; j+;return T;/*訪問元素*/void visit(char ch) if(i!=(a-1) printf(%c-,ch);i+;else printf(%c,ch);printf(n)；/*求二叉樹的結(jié)點(diǎn)總數(shù)*/int counter(struct bitree *T) int num1,num2,num;if(T=NULL) return 0;

20、else num1=counter(T-lchild);num2=counter(T-rchild);num=num1+num2+1;return num;/*創(chuàng)建空隊(duì)列*/queue *initqueue() Q-base=(qnode *)malloc(MAX*sizeof(qnode);Q-front=Q-rear=0;Q-size=MAX;return Q;/*判斷隊(duì)列是否為空*/int emptyqueue(queue *q) if(q-front=q-rear) return 1;else return 0;/*入隊(duì)列*/queue *enqueue(queue *q,bitree

21、 *p) q-baseq-rear.q=p;q-rear+;return q;/*出隊(duì)列*/bitree *dequeue(queue *q) int n;if(q-front=q-rear) printf(the queue is NULL!n)； return 0;n=q-front;q-front+;return (q-basen.q);/*層次遍歷*/void levelorder(bitree *t) bitree *p;Q=initqueue();if(t!=NULL) enqueue(Q,t);while(!emptyqueue(Q) p=dequeue(Q);visit(p-n

22、ode);if(p-lchild!=NULL)enqueue(Q,p-lchild);if(p-rchild!=NULL)enqueue(Q,p-rchild);/*廣義表形式輸出二叉樹*/void printBTree( bitree *T) if(T!= NULL) /*樹為空時(shí)結(jié)束遞歸，否則執(zhí)行如下操作*/ printf(%c，T-node); /* 輸出根結(jié)點(diǎn)的值 */ if(T-lchild != NULL | T-rchild!= NULL) printf()；printBTree(T-lchild);if(T-rchild != NULL) printf(,)； printBTr

23、ee(T-rchild);printf()；/*主函數(shù)*/int main(void) int sum;printf(nninput guang yi biao :n)；gets(s);/*輸入廣義表*/T=creatbitree2(T);/*廣義表創(chuàng)建樹 */printf(nnthe bitree de zong jie dian shu :n);a=counter(T);printf(a=%dn，a); /*輸出樹的總結(jié)點(diǎn)數(shù)*/printf(nnouput the btree biaon)；printBTree(T);/*二叉樹以廣義表輸出*/printf(nnceng ci bian l

24、i result:n)；levelorder(T);/*層次遍歷的結(jié)果*/getch();return 0;線索二叉樹的基本操作實(shí)現(xiàn)線索二叉樹的基本操作實(shí)現(xiàn)的程序代碼如下：#includetypedef char DataType;#define MAXNODE 100typedef struct BiThrNodeDataType data;struct BiThrNode *lchild;struct BiThrNode *rchild;unsigned ltag;unsigned rtag;BiThrNode,*BiThrTree;BiThrTree pre;void Create_Bi

25、Tree(BiThrTree *T)夠造二叉樹DataType ch;cinch;if(ch=0)(*T)=NULL;else(*T)=new BiThrNode;(*T)-ltag=(*T)-rtag=0;(*T)-data=ch;Create_BiTree(&(*T)-lchild);Create_BiTree(&(*T)-rchild);void InThreading(BiThrTree p)中序遍歷進(jìn)行中序線索化if(p)InThreading(p-lchild);if(!p-lchild)p-ltag=1;p-lchild=pre;if(!pre-rchild)pre-rtag=1

26、;pre-rchild=p;pre=p;InThreading(p-rchild);int InOrderThr(BiThrTree *head,BiThrTree T)中序遍歷二叉樹T,并將其中序線索化，*head指向頭結(jié)點(diǎn)，pre為全局變量(*head)=new BiThrNode;if(!(*head)return 0;(*head)-ltag=0;(*head)-rtag=1;(*head)-rchild=*head;if(!T)(*head)-lchild=*head;else(*head)-lchild=T;pre=(*head);InThreading(T);pre-rchild

27、=*head;pre-rtag=1;(*head)-rchild=pre;return 1;void InOrderThr(BiThrTree head,BiThrTree T)中序遍歷進(jìn)行中序線索化if(!head)cout結(jié)點(diǎn)無法分配的到空間ltag=0;head-rtag=1;head-rchild=head;if(!T)head-lchild=head;elsehead-lchild=T;pre=head;InThreading(T);pre-rchild=head;pre-rtag=1;head-rchild=pre;BiThrTree InPreNode(BiThrTree p)/在中序線索二叉樹上p的前驅(qū)結(jié)點(diǎn)BiThrTree pre;pre=p-lchild;if(p-ltag!=1)while(pre-rtag=0)pre=pre-rchild;return pre;BiThrTree InPostNode(BiThrTree p)/在中序線索二叉樹上p的后繼結(jié)點(diǎn)BiThrTree post;post=p-rchild;if(p-rtag!=1)while(post-ltag=0)post=post-lchild;return post;BiThrTree IprePostNode(B