實驗三：二叉樹操作.doc

實驗報告學院（系）名稱：計算機與通信工程學院姓名* *學號* *專業(yè)計算機科學與技術班級2015級*班實驗項目實驗三：二叉樹操作 課程名稱數據結構與算法課程代碼0661013實驗時間年 月 日第節(jié)實驗地點7-*考核標準實驗過程25分程序運行20分回答問題15分實驗報告30分特色功能5分考勤違紀情況5分成績成績欄其它批改意見: 教師簽字：考核內容評價在實驗課堂中的表現，包括實驗態(tài)度、編寫程序過程等內容等。功能完善, 功能不全有小錯無法運行正確基本正確有提示無法回答完整較完整一般內容極少無報告有無有無 一、實驗目的理解二叉樹的邏輯特點和二叉樹的性質；掌握二叉樹的二叉鏈表存儲結構，掌握二叉樹 的創(chuàng)建算法、遍歷算法的遞歸與非遞歸實現，并能在遍歷算法基礎上實現較復雜算法設計。二、實驗題目與要求1.每位同學按下述要求實現相應算法：以二叉鏈表為存儲結構，實現二叉樹的創(chuàng)建、遍歷算法 1）問題描述：在主程序中提供下列菜單： 1建立樹 2前序遍歷樹 3中序(非遞歸)遍歷樹 4后序遍歷樹 0結束 2）實驗要求： 定義下列過程： CreateTree(): 按從鍵盤輸入的前序序列，創(chuàng)建樹 PreOrderTree()：前序遍歷樹（遞歸） InOrderTree()：中序(非遞歸)遍歷樹 LaOrderTree(): 后序遍歷樹（遞歸） 每位同學在實驗過程中要單步運行程序，跟蹤二叉樹的創(chuàng)建過程與前序遍歷的遞歸過程。 3）注意問題: 注意理解遞歸算法的執(zhí)行步驟。 注意字符類型數據在輸入時的處理。 重點理解如何利用棧結構實現非遞歸算2. 編寫算法交換二叉樹中所有結點的左、右子樹 1）問題描述：編寫一算法，交換二叉樹中所有結點的左、右子樹 2）實驗要求：以二叉鏈表作為存儲結構3. 試編寫按層次順序遍歷二叉樹的算法 1）問題描述：編寫按層次順序遍歷二叉樹的算法 2）實驗要求：以二叉鏈表作為存儲結構4. 編寫算法求二叉樹高度及寬度。 1） 問題描述：二叉樹高度是指樹中所有節(jié)點的最大層數，二叉樹寬度是指在二叉樹的各層上， 具有節(jié)點數最多的那一層上的節(jié)點總數。 2） 實驗要求：以二叉鏈表作為存儲結構三、實驗過程與實驗結果 應包括如下主要內容： 數據結構定義 二叉樹是個節(jié)點的有限集合，該集合或者為空，或者由一個根節(jié)點及兩個分別稱為左子樹和右子樹的互不相交的二叉樹組成。當集合為空時，稱該二叉樹為空二叉樹。 算法設計思路簡介 1、利用遞歸算法前序建立二叉樹，并完成二叉樹的前序、中序和后序遍歷。其中前序遍歷和后序遍歷均用遞歸算法，中序遍歷借助棧的機制，實現非遞歸遍歷。 2、在前序遍歷的過程中利用中間變量交換左右子樹。 3、利用隊列。當上一層中的數據全部出隊（遍歷）完畢再遍歷本層節(jié)點。 4、高度：獲取所有節(jié)點到根節(jié)點的最長路徑。寬度：在層次遍歷的基礎上，返回最多節(jié)點的層的節(jié)點數。 算法描述：可以用自然語言、偽代碼或流程圖等方式 1、創(chuàng)建樹： （1）聲明節(jié)點 （2）輸入當前節(jié)點，若輸入為#則當前節(jié)點為空，否則為當前節(jié)點申請空間。 （3）將輸入的值賦給當前節(jié)點的data域，并前序建立當前節(jié)點的左子樹和右子樹。 （4）返回當前節(jié)點。 前序遍歷樹： （1）若當前節(jié)點為空則返回上一級函數，否則打印當前節(jié)點。 （2）前序遍歷當前節(jié)點的左子樹。 （3）前序遍歷當前節(jié)點的右子樹。 中序遍歷樹： （1）聲明一個順序棧，并用p指針指向當前節(jié)點。 （2）若當前節(jié)點和棧不同時為空則重復進行下一步。否則程序結束 （3）若當前節(jié)點不為空則重復進行第四步，否則執(zhí)行第五步。 （4）在棧不滿的情況下將當前節(jié)點入棧，并把p指針指向當前節(jié)點左子樹的根節(jié)點。 （5）若棧為空則執(zhí)行第三步，否則執(zhí)行第六步。 （6）將棧頂元素出棧，并打印棧頂元素的data，將p指向棧頂元素的右子樹的根節(jié)點。執(zhí)行第二步。 前序遍歷樹： （1）若當前節(jié)點為空則返回上一級函數否則執(zhí)行下一步。 （2）后序遍歷當前節(jié)點的左子樹。 （3）后序遍歷當前節(jié)點的右子樹。 （3）打印當前節(jié)點的data。 2、 （1）若當前節(jié)點為空則返回NULL,結束。否則執(zhí)行下一步。 （2）利用中間變量temp交換當前節(jié)點的左右子樹。 （3）交換當前的點左子樹根節(jié)點的左右子樹。 （4）交換當前節(jié)點右子樹根節(jié)點的左右子樹。 （4）返回根節(jié)點。 3、 （1）利用指針temp指向根節(jié)點，并初始化一個隊列。 （2）將temp指向的當點節(jié)點入隊。 （3）重復指向以下所有步驟，直到遇到break語句。 （4）用變量len記錄隊列中二叉樹當前層的節(jié)點數。 （5）若len為0則結束整個程序，否則執(zhí)行第六步。 （6）當len0（即隊列中還有前層的節(jié)點時）重復指向以下所有步驟。否則執(zhí)行第三步。 （7）將當前對頭出棧，len+，打印出隊元素 （8）如果出隊元素的左子樹的根節(jié)點不為空則入隊,len-. （9）如果出隊元素的右子樹的根節(jié)點不為空則入隊,len-. 4、 （1）利用指針temp指向根節(jié)點，并初始化一個隊列。 （2）將temp指向的當點節(jié)點入隊。并聲明當前層最大節(jié)點數為0 （3）重復指向以下所有步驟，直到遇到break語句。若遇到break語句則結束整個程序并返回最大節(jié)點數。 （4）用變量len記錄隊列中二叉樹當前層的節(jié)點數。 （5）若len為0則結束整個程序，否則執(zhí)行第六步。 （6）當len0（即隊列中還有前層的節(jié)點時）重復七九步。否則執(zhí)行第十步。 （7）將當前對頭出棧，len+，打印出隊元素 （8）如果出隊元素的左子樹的根節(jié)點不為空則入隊,len-. （9）如果出隊元素的右子樹的根節(jié)點不為空則入隊,len-. （10）當前層最大節(jié)點數等于上一層最大節(jié)點數和當前隊列中的節(jié)點數中較大的一個。 執(zhí)行第三步。 算法的實現和測試結果：包括算法運行時的輸入、輸出，實驗中出現的問題及解決辦法等 1、 輸入：ABH#FD#E#CK#G# 輸出： 2、 輸入：ABH#FD#E#CK#G# 輸出： 3、 輸入：ABH#FD#E#CK#G# 輸出： 4、 輸入：ABH#FD#E#CK#G# 輸出： 算法時間復雜度分析 1、O(n). 2、O(n). 3、O(n). 4、O(n).四、收獲與體會學了二叉樹之后頓時感覺之前的內容有多簡單了。二叉樹中用到很多遞歸算法，看起來很難懂。需要一步一步的跟下去才能理解，但是理解還遠遠不夠，關鍵是是自己能寫出來屬于自己的遞歸算法。經過長時間的練習，我已經能寫出來一些簡單的遞歸算法了，但是稍微難一點的就寫不出來了。后面的圖還更難。革命尚未成功，諸君還需努力吶。我相信經過自己不屑的練習，我會提高的！五、源代碼清單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(BitNode)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(BitNode *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(前序遍歷結果);PreOrder(root);printf(n);printf(中序遍歷結果);InOrder(root);printf(n);printf(后序遍歷結果);PostOrder(root);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();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;int 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;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;/*以上為樹*/QueueNode *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;else return 0;QueueNode *Push(QueueNode *Q,Elementtype *ele)if(QueueFull(Q)printf(隊列已滿，無法入隊！); else *(Q-base + Q-rear) = *ele;Q-rear = (Q-rear+1) % MaxSize;return Q;QueueNode *Pop(QueueNode *Q,Elementtype *ele)if(QueueEmpty(Q)printf(隊列為空，無法出隊); else *ele = *(Q-base+Q-front);Q-front = (Q-front+1) % MaxSize;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)queue = Push(queue,temp-rchild);while(!QueueEmpty(queue);/*以上為隊列*/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 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;/*以上為樹*/QueueNode *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;else return 0;int 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(隊列已滿，無法入隊！); else *(Q-base + Q-rear) = *ele;Q-rear = (Q-rear+1) % MaxSize;return Q;QueueNode *Pop(QueueNode *Q,Elementtype *ele)if(QueueEmpty(Q)printf(隊列為空，無法出隊！); else *ele = *(Q-base+Q-front);Q-front = (Q-fron