實(shí)驗(yàn)三：二叉樹操作

1、實(shí)驗(yàn)報(bào)告學(xué)院（系）名稱：計(jì)算機(jī)與通信工程學(xué)院姓名* *學(xué)號(hào)* *專業(yè)計(jì)算機(jī)科學(xué)與技術(shù)班級(jí)2015級(jí)*班實(shí)驗(yàn)項(xiàng)目實(shí)驗(yàn)三：二叉樹操作 課程名稱數(shù)據(jù)結(jié)構(gòu)與算法課程代碼0661013實(shí)驗(yàn)時(shí)間年 月 日第節(jié)實(shí)驗(yàn)地點(diǎn)7-*考核標(biāo)準(zhǔn)實(shí)驗(yàn)過程25分程序運(yùn)行20分回答問題15分實(shí)驗(yàn)報(bào)告30分特色功能5分考勤違紀(jì)情況5分成績(jī)成績(jī)欄其它批改意見: 教師簽字：考核內(nèi)容評(píng)價(jià)在實(shí)驗(yàn)課堂中的表現(xiàn)，包括實(shí)驗(yàn)態(tài)度、編寫程序過程等內(nèi)容等。功能完善, 功能不全有小錯(cuò)無法運(yùn)行正確基本正確有提示無法回答完整較完整一般內(nèi)容極少無報(bào)告有無有無 一、實(shí)驗(yàn)?zāi)康睦斫舛鏄涞倪壿嬏攸c(diǎn)和二叉樹的性質(zhì)；掌握二叉樹的二叉鏈表存儲(chǔ)結(jié)構(gòu)，掌握二叉樹 的創(chuàng)建

2、算法、遍歷算法的遞歸與非遞歸實(shí)現(xiàn)，并能在遍歷算法基礎(chǔ)上實(shí)現(xiàn)較復(fù)雜算法設(shè)計(jì)。二、實(shí)驗(yàn)題目與要求1.每位同學(xué)按下述要求實(shí)現(xiàn)相應(yīng)算法：以二叉鏈表為存儲(chǔ)結(jié)構(gòu)，實(shí)現(xiàn)二叉樹的創(chuàng)建、遍歷算法 1）問題描述：在主程序中提供下列菜單： 1建立樹 2前序遍歷樹 3中序(非遞歸)遍歷樹 4后序遍歷樹 0結(jié)束 2）實(shí)驗(yàn)要求： 定義下列過程： CreateTree(): 按從鍵盤輸入的前序序列，創(chuàng)建樹 PreOrderTree()：前序遍歷樹（遞歸） InOrderTree()：中序(非遞歸)遍歷樹 LaOrderTree(): 后序遍歷樹（遞歸） 每位同學(xué)在實(shí)驗(yàn)過程中要單步運(yùn)行程序，跟蹤二叉樹的創(chuàng)建過程與前序遍歷的遞

3、歸過程。 3）注意問題: 注意理解遞歸算法的執(zhí)行步驟。 注意字符類型數(shù)據(jù)在輸入時(shí)的處理。 重點(diǎn)理解如何利用棧結(jié)構(gòu)實(shí)現(xiàn)非遞歸算2. 編寫算法交換二叉樹中所有結(jié)點(diǎn)的左、右子樹 1）問題描述：編寫一算法，交換二叉樹中所有結(jié)點(diǎn)的左、右子樹 2）實(shí)驗(yàn)要求：以二叉鏈表作為存儲(chǔ)結(jié)構(gòu)3. 試編寫按層次順序遍歷二叉樹的算法 1）問題描述：編寫按層次順序遍歷二叉樹的算法 2）實(shí)驗(yàn)要求：以二叉鏈表作為存儲(chǔ)結(jié)構(gòu)4. 編寫算法求二叉樹高度及寬度。 1） 問題描述：二叉樹高度是指樹中所有節(jié)點(diǎn)的最大層數(shù)，二叉樹寬度是指在二叉樹的各層上， 具有節(jié)點(diǎn)數(shù)最多的那一層上的節(jié)點(diǎn)總數(shù)。 2） 實(shí)驗(yàn)要求：以二叉鏈表作為存儲(chǔ)結(jié)構(gòu)三、實(shí)驗(yàn)過

4、程與實(shí)驗(yàn)結(jié)果 應(yīng)包括如下主要內(nèi)容： 數(shù)據(jù)結(jié)構(gòu)定義 二叉樹是個(gè)節(jié)點(diǎn)的有限集合，該集合或者為空，或者由一個(gè)根節(jié)點(diǎn)及兩個(gè)分別稱為左子樹和右子樹的互不相交的二叉樹組成。當(dāng)集合為空時(shí)，稱該二叉樹為空二叉樹。 算法設(shè)計(jì)思路簡(jiǎn)介 1、利用遞歸算法前序建立二叉樹，并完成二叉樹的前序、中序和后序遍歷。其中前序遍歷和后序遍歷均用遞歸算法，中序遍歷借助棧的機(jī)制，實(shí)現(xiàn)非遞歸遍歷。 2、在前序遍歷的過程中利用中間變量交換左右子樹。 3、利用隊(duì)列。當(dāng)上一層中的數(shù)據(jù)全部出隊(duì)（遍歷）完畢再遍歷本層節(jié)點(diǎn)。 4、高度：獲取所有節(jié)點(diǎn)到根節(jié)點(diǎn)的最長(zhǎng)路徑。寬度：在層次遍歷的基礎(chǔ)上，返回最多節(jié)點(diǎn)的層的節(jié)點(diǎn)數(shù)。 算法描述：可以用自然語言、

5、偽代碼或流程圖等方式 1、創(chuàng)建樹： （1）聲明節(jié)點(diǎn) （2）輸入當(dāng)前節(jié)點(diǎn)，若輸入為#則當(dāng)前節(jié)點(diǎn)為空，否則為當(dāng)前節(jié)點(diǎn)申請(qǐng)空間。 （3）將輸入的值賦給當(dāng)前節(jié)點(diǎn)的data域，并前序建立當(dāng)前節(jié)點(diǎn)的左子樹和右子樹。 （4）返回當(dāng)前節(jié)點(diǎn)。 前序遍歷樹： （1）若當(dāng)前節(jié)點(diǎn)為空則返回上一級(jí)函數(shù)，否則打印當(dāng)前節(jié)點(diǎn)。 （2）前序遍歷當(dāng)前節(jié)點(diǎn)的左子樹。 （3）前序遍歷當(dāng)前節(jié)點(diǎn)的右子樹。 中序遍歷樹： （1）聲明一個(gè)順序棧，并用p指針指向當(dāng)前節(jié)點(diǎn)。 （2）若當(dāng)前節(jié)點(diǎn)和棧不同時(shí)為空則重復(fù)進(jìn)行下一步。否則程序結(jié)束 （3）若當(dāng)前節(jié)點(diǎn)不為空則重復(fù)進(jìn)行第四步，否則執(zhí)行第五步。 （4）在棧不滿的情況下將當(dāng)前節(jié)點(diǎn)入棧，并把p指針指向

6、當(dāng)前節(jié)點(diǎn)左子樹的根節(jié)點(diǎn)。 （5）若棧為空則執(zhí)行第三步，否則執(zhí)行第六步。 （6）將棧頂元素出棧，并打印棧頂元素的data，將p指向棧頂元素的右子樹的根節(jié)點(diǎn)。執(zhí)行第二步。 前序遍歷樹： （1）若當(dāng)前節(jié)點(diǎn)為空則返回上一級(jí)函數(shù)否則執(zhí)行下一步。 （2）后序遍歷當(dāng)前節(jié)點(diǎn)的左子樹。 （3）后序遍歷當(dāng)前節(jié)點(diǎn)的右子樹。 （3）打印當(dāng)前節(jié)點(diǎn)的data。 2、 （1）若當(dāng)前節(jié)點(diǎn)為空則返回NULL,結(jié)束。否則執(zhí)行下一步。 （2）利用中間變量temp交換當(dāng)前節(jié)點(diǎn)的左右子樹。 （3）交換當(dāng)前的點(diǎn)左子樹根節(jié)點(diǎn)的左右子樹。 （4）交換當(dāng)前節(jié)點(diǎn)右子樹根節(jié)點(diǎn)的左右子樹。 （4）返回根節(jié)點(diǎn)。 3、 （1）利用指針temp指向根節(jié)點(diǎn)

7、，并初始化一個(gè)隊(duì)列。 （2）將temp指向的當(dāng)點(diǎn)節(jié)點(diǎn)入隊(duì)。 （3）重復(fù)指向以下所有步驟，直到遇到break語句。 （4）用變量len記錄隊(duì)列中二叉樹當(dāng)前層的節(jié)點(diǎn)數(shù)。 （5）若len為0則結(jié)束整個(gè)程序，否則執(zhí)行第六步。 （6）當(dāng)len0（即隊(duì)列中還有前層的節(jié)點(diǎn)時(shí)）重復(fù)指向以下所有步驟。否則執(zhí)行第三步。 （7）將當(dāng)前對(duì)頭出棧，len+，打印出隊(duì)元素 （8）如果出隊(duì)元素的左子樹的根節(jié)點(diǎn)不為空則入隊(duì),len-. （9）如果出隊(duì)元素的右子樹的根節(jié)點(diǎn)不為空則入隊(duì),len-. 4、 （1）利用指針temp指向根節(jié)點(diǎn)，并初始化一個(gè)隊(duì)列。 （2）將temp指向的當(dāng)點(diǎn)節(jié)點(diǎn)入隊(duì)。并聲明當(dāng)前層最大節(jié)點(diǎn)數(shù)為0 （3）重

8、復(fù)指向以下所有步驟，直到遇到break語句。若遇到break語句則結(jié)束整個(gè)程序并返回最大節(jié)點(diǎn)數(shù)。 （4）用變量len記錄隊(duì)列中二叉樹當(dāng)前層的節(jié)點(diǎn)數(shù)。 （5）若len為0則結(jié)束整個(gè)程序，否則執(zhí)行第六步。 （6）當(dāng)len0（即隊(duì)列中還有前層的節(jié)點(diǎn)時(shí)）重復(fù)七九步。否則執(zhí)行第十步。 （7）將當(dāng)前對(duì)頭出棧，len+，打印出隊(duì)元素 （8）如果出隊(duì)元素的左子樹的根節(jié)點(diǎn)不為空則入隊(duì),len-. （9）如果出隊(duì)元素的右子樹的根節(jié)點(diǎn)不為空則入隊(duì),len-. （10）當(dāng)前層最大節(jié)點(diǎn)數(shù)等于上一層最大節(jié)點(diǎn)數(shù)和當(dāng)前隊(duì)列中的節(jié)點(diǎn)數(shù)中較大的一個(gè)。 執(zhí)行第三步。 算法的實(shí)現(xiàn)和測(cè)試結(jié)果：包括算法運(yùn)行時(shí)的輸入、輸出，實(shí)驗(yàn)中出現(xiàn)的問

9、題及解決辦法等 1、 輸入：ABH#FD#E#CK#G# 輸出： 2、 輸入：ABH#FD#E#CK#G# 輸出： 3、 輸入：ABH#FD#E#CK#G# 輸出： 4、 輸入：ABH#FD#E#CK#G# 輸出： 算法時(shí)間復(fù)雜度分析 1、O(n). 2、O(n). 3、O(n). 4、O(n).四、收獲與體會(huì)學(xué)了二叉樹之后頓時(shí)感覺之前的內(nèi)容有多簡(jiǎn)單了。二叉樹中用到很多遞歸算法，看起來很難懂。需要一步一步的跟下去才能理解，但是理解還遠(yuǎn)遠(yuǎn)不夠，關(guān)鍵是是自己能寫出來屬于自己的遞歸算法。經(jīng)過長(zhǎng)時(shí)間的練習(xí)，我已經(jīng)能寫出來一些簡(jiǎn)單的遞歸算法了，但是稍微難一點(diǎn)的就寫不出來了。后面的圖還更難。革命尚未成功，

10、諸君還需努力吶。我相信經(jīng)過自己不屑的練習(xí)，我會(huì)提高的！五、源代碼清單1、#include#include#define MaxSize 100typedef char Elemtype;typedef struct BitNodeElemtype data;struct BitNode *lchild;struct BitNode *rchild;BitNode;BitNode *CreateTree()char ch;BitNode *T;scanf(%c,&ch);if(ch = #) T = NULL;else if(!(T = (BitNode*)malloc(sizeof(BitNo

11、de)exit(1);T-data = ch;T-lchild = CreateTree();T-rchild = CreateTree();return T;void PreOrder(BitNode *T)if(T = NULL) return;printf(%c,T-data);PreOrder(T-lchild);PreOrder(T-rchild);void PostOrder(BitNode *T)if(T = NULL) return;PostOrder(T-lchild);PostOrder(T-rchild);printf(%c,T-data);void InOrder(Bi

12、tNode *T)BitNode *p,*q;BitNode *StackMaxSize;int top = 0;p = T;while(!(p = NULL & top = 0)while(p != NULL)if(top lchild;if(top data);p = p-rchild;int main()BitNode *root;root = CreateTree();printf(前序遍歷結(jié)果);PreOrder(root);printf(n);printf(中序遍歷結(jié)果);InOrder(root);printf(n);printf(后序遍歷結(jié)果);PostOrder(root);

13、printf(n);return 0;2、#include#includetypedef char Elemtype;typedef struct BitTreeElemtype data;struct BitTree *lchild;struct BitTree *rchild;BitTree;BitTree *CreateTree()char ch;BitTree *T;scanf(%c,&ch);if(ch = #) T = NULL;else T = (BitTree*)malloc(sizeof(BitTree);T-data = ch;T-lchild = CreateTree()

14、;T-rchild = CreateTree();return T;void InOrder(BitTree *T)if(T = NULL) return;InOrder(T-lchild);printf(%c,T-data);InOrder(T-rchild);BitTree *Exchange(BitTree *T)BitTree *temp;if(T = NULL) return NULL;temp = T-lchild;T-lchild = T-rchild;T-rchild = temp;Exchange(T-lchild);Exchange(T-rchild);return T;i

15、nt main()BitTree *root;root = CreateTree();printf(中序遍歷原二叉樹：);InOrder(root);root = Exchange(root);printf(n中序遍歷交換后的二叉樹：);InOrder(root);printf(n);return 0;3、#include#include#define MaxSize 100typedef char Elemtype;typedef struct BitTreeElemtype data;struct BitTree *lchild;struct BitTree *rchild;BitTree

16、;typedef BitTree Elementtype;typedef struct QueueNodeElementtype *base;int front;int rear;QueueNode;BitTree *CreateTree()char ch;BitTree *T;scanf(%c,&ch);if(ch = #) T = NULL;else T = (BitTree*)malloc(sizeof(BitTree);T-data = ch;T-lchild = CreateTree(); T-rchild = CreateTree();return T;/*以上為樹*/QueueN

17、ode *InitQueue()QueueNode *Q;Q = (QueueNode*)malloc(sizeof(QueueNode);Q-base = (Elementtype*)malloc(MaxSize*sizeof(Elementtype);Q-rear = Q-front = 0;return Q;int QueueFull(QueueNode *Q)if(Q-rear+1) % MaxSize = Q-front) return 1;else return 0;int QueueEmpty(QueueNode *Q)if(Q-rear = Q-front) return 1;

18、else return 0;QueueNode *Push(QueueNode *Q,Elementtype *ele)if(QueueFull(Q)printf(隊(duì)列已滿，無法入隊(duì)！); else *(Q-base + Q-rear) = *ele;Q-rear = (Q-rear+1) % MaxSize;return Q;QueueNode *Pop(QueueNode *Q,Elementtype *ele)if(QueueEmpty(Q)printf(隊(duì)列為空，無法出隊(duì)); else *ele = *(Q-base+Q-front);Q-front = (Q-front+1) % M

19、axSize;return Q;void display(BitTree *T)if(T = NULL) return;Elementtype elem;BitTree *temp;temp = T;QueueNode *queue;queue = InitQueue();queue = Push(queue,temp);doqueue = Pop(queue,&elem);temp = &elem;printf(%c,temp-data);if(temp-lchild != NULL)queue = Push(queue,temp-lchild);if(temp-rchild != NULL

20、)queue = Push(queue,temp-rchild);while(!QueueEmpty(queue);/*以上為隊(duì)列*/int main()BitTree *root;root = CreateTree();display(root);return 0;4、#include#include#define MaxSize 100typedef char Elemtype;typedef struct BitTreeElemtype data;struct BitTree *lchild;struct BitTree *rchild;BitTree;typedef BitTree E

21、lementtype;typedef struct QueueNodeElementtype *base;int front;int rear;QueueNode;BitTree *CreateTree()char ch;BitTree *T;scanf(%c,&ch);if(ch = #) T = NULL;else T = (BitTree*)malloc(sizeof(BitTree);T-data = ch;T-lchild = CreateTree(); T-rchild = CreateTree();return T;/*以上為樹*/QueueNode *InitQueue()Qu

22、eueNode *Q;Q = (QueueNode*)malloc(sizeof(QueueNode);Q-base = (Elementtype*)malloc(MaxSize*sizeof(Elementtype);Q-rear = Q-front = 0;return Q;int QueueFull(QueueNode *Q)if(Q-rear+1) % MaxSize = Q-front) return 1;else return 0;int QueueEmpty(QueueNode *Q)if(Q-rear = Q-front) return 1;else return 0;int

23、GetLength(QueueNode *Q)int i = Q-front;int j = 1;while(i != Q-rear)i = (i+1)%MaxSize;j+;return (j-1);QueueNode *Push(QueueNode *Q,Elementtype *ele)if(QueueFull(Q)printf(隊(duì)列已滿，無法入隊(duì)！); else *(Q-base + Q-rear) = *ele;Q-rear = (Q-rear+1) % MaxSize;return Q;QueueNode *Pop(QueueNode *Q,Elementtype *ele)if(QueueEmpty(Q)printf(隊(duì)列為空，無法出隊(duì)！); else *ele = *(Q-base+Q-front);Q-front = (Q-fron