1、課程設計唯一的確定一棵二叉樹設計時間：2011 年 4 月 18樹、圖及其應用題目：唯一的確定一棵二叉樹實習時間：2011.4.15一、需求分析：1. 如果給出了遍歷二叉樹的前序序列和中序序列，則可以構造出唯一的一棵二叉樹。 試編寫實現上述功能的程序。已知一棵二叉樹的前序和中序序列，設計完成下列任務的一個算法：（ 1）構造一棵二叉樹；（ 2）證明構造正確（即分別以前序和中序遍歷該樹，將得到的結果與給出的序列進行比較）。2. 測試數據：前序序列為ABDEGCFH，中序序列為IJDBGEAHFIJ。 C二、設計：設計思想（ 1）存儲結構: 二叉樹 ，用兩個一維數組A 和 B 分別存放前序和中序序列

2、。（ 2）主要算法基本思想：將前序和中序序列分別讀入數組A和 B。根據定義，前序序列中第一個元素一定是樹根，在中序序列中該元素之前的所有元素一定在左子樹中，其余元素則在右子樹中。所以， 首先從數組A中取出第一個元素A0 作根結點，然后在數組B 中找到 A0 ，以它為界，在其前面的是左子樹中序序列，在其后面的是右子樹中序序列。若左子樹不為空，沿前序序列向后移動，找到左子樹根結點，轉。左子樹構造完畢后，若右子樹不為空，沿前序序列向后移動，找到右子樹根結點，轉。前序序列中各元素取完則二叉樹構造完畢。對二叉樹進行前序和中序遍歷，并將結果分別與數組A和 B進行比較，若相同，則證明二叉樹構造正確。設計表示

3、（ 1）函數調用關系圖： main InitiateCreateTree PrintBiTreePreOrder VisitInOrder Visit PostOrder( 2)函數接口規格說明：void Initiate(BiTNode *root)/ 初始化二叉樹的頭結點void Visit(char item)/ 訪問操作void PreOrder(BiTNode *T,void Visit(char item)/前序遍歷二叉樹void InOrder(BiTNode *T,void Visit(char item)/中序遍歷二叉樹void PostOrder(BiTNode *T,vo

4、id Visit(char item)/后序遍歷二叉樹void PrintBiTree(BiTNode *T,int n)/ 顯示二叉樹void CreateTree(BiTNode *T,int pre_f,int pre_l,int in_f,int in_l,char pre,char in)/ 按要求創建二叉樹實現注釋（ 1）根據前序遍歷和后序遍歷創建二叉樹，并后序遍歷該二叉樹。（ 2）二叉樹逆轉90 度來顯示。詳細設計總體來說，本程序設計相對比較簡單，主要包括七個功能模塊：初始化函數、 前序遍歷二叉樹函數、中序遍歷二叉樹函數、后序遍歷二叉樹函數、顯示函數、創建二叉樹函數、主函數。下面

5、分別給予介紹：初始化函數void Initiate(BiTNode *root)*root=(BiTNode *)malloc(sizeof(BiTNode);(*root)->LeftChild=NULL;(*root)->RightChild=NULL;前序遍歷二叉樹函數void PreOrder(BiTNode *T,void Visit(char item) if(T!=NULL)Visit(T->data);PreOrder(T->LeftChild,Visit);PreOrder(T->RightChild,Visit);中序遍歷二叉樹函數void I

6、nOrder(BiTNode *T,void Visit(char item)if(T!=NULL)InOrder(T->LeftChild,Visit);Visit(T->data);InOrder(T->RightChild,Visit);后序遍歷二叉樹函數void PostOrder(BiTNode *T,void Visit(char item) if(T!=NULL)PostOrder(T->LeftChild,Visit);PostOrder(T->RightChild,Visit);Visit(T->data);顯示函數void PrintBi

7、Tree(BiTNode *T,int n)int i;if(T=NULL) return;PrintBiTree(T->RightChild,n+1);for(i=0;i<n;i+) printf(" ");if(n>=0)printf(" ");printf("%cnn",T->data);PrintBiTree(T->LeftChild,n+1);創建二叉樹函數void CreateTree(BiTNode *T,int pre_f,int pre_l,int in_f,int in_l,char

8、pre,char in)int interval=0;/int same=in_f;if(prepre_f!=insame)while(prepre_f!=insame)/ 在中序序列中找到根節點same+;interval+;if(interval=0)&&(pre_f=pre_l) / 找到了葉節點，也是遞歸出口T->data=prepre_f;T->LeftChild=NULL;T->RightChild=NULL;if(interval!=0)&&(interval<pre_l-pre_f) /同時存在左子樹和右子樹T->L

9、eftChild=(BiTNode *)malloc(sizeof(BiTNode);T->RightChild=(BiTNode *)malloc(sizeof(BiTNode);T->data=prepre_f;CreateTree(T->LeftChild,pre_f+1,pre_f+interval,in_f,in_f+interval-1,p re,in);CreateTree(T->RightChild,pre_f+interval+1,pre_l,in_f+interval+1,in_l, pre,in);if(interval!=0)&&

10、(interval=pre_l-pre_f)/只有左子樹T->LeftChild=(BiTNode *)malloc(sizeof(BiTNode);T->data=prepre_f;CreateTree(T->LeftChild,pre_f+1,pre_l,in_f,in_f+interval-1,pre,in); T->RightChild=NULL;if(interval=0)&&(pre_f!=pre_l)/ 只有右子樹T->RightChild=(BiTNode *)malloc(sizeof(BiTNode);T->data=pr

11、epre_f;T->LeftChild=NULL;CreateTree(T->RightChild,pre_f+interval+1,pre_l,in_f+interval+1,in_l, pre,in);主函數void main()BiTNode *T;int Pre_len,In_len;char PreMaxSize;/ 前序序列char InMaxSize;/ 中序序列printf(" 請輸入前序序列：n");scanf("%s",&Pre);Pre_len=strlen(Pre);printf(" 請輸入中序序列：

12、n");scanf("%s",&In);In_len=strlen(In);Initiate(&T);CreateTree(T,0,Pre_len-1,0,In_len-1,Pre,In);printf(" 二叉樹構造成功！n");printf("逆時針旋轉90 度的二叉樹如下所示：n");PrintBiTree(T,0);printf("前序序列：n");PreOrder(T,Visit);printf("n中序序列：n");InOrder(T,Visit);prin

13、tf("n后序序列：n");PostOrder(T,Visit);printf("n");三、調試分析：本程序在設計過程中遇到一個難題，那就是如何正確顯示所構造的二叉樹，試了幾種方法都不理想，最后想到讓二叉樹逆時針旋轉后再顯示，具備可行性，同時也使之更美觀。經驗和體會經過第一次一元稀疏多項式加法的課程設計，這次課程設計就顯得輕車熟路了，運算的主要設計思路很容易想到，大體設計結構在較短時間內能夠完成，但當設計到具體細節代碼時遇到了一些困難，主要困難是進行結點操作時，對指針考慮得不夠細致，調試時常出現指針指錯的情況，沒有認真理清條件層次，另一個困難是如何正確

14、顯示所構造的二叉樹。雖然程序可能并不是最高效的，而且不夠健壯，但也符合題目的要求，總的來說本次課程設計還算圓滿。本次課程設計培養了我對實際問題的分析能力以及解決一些實際問題的能力， 鞏固了我的編程思想和寫程序的能力。課程設計是對我們的學習很有利的一個環節， 在這個階段，我們學會把理論與實際的結合、懂得人與人溝通的重要性，通過這次課程設計中，我加深了對課本知識的理解。四、用戶手冊：本 程 序 在 Vi sual C + 6. 0 下 運 行 。先輸入前序遍歷序列，回車，再輸入中序遍歷序列，再回車，即可得出結果。五、運行結果：六、源程序清單：#include <stdio.h>#inc

15、lude <Stdlib.h>#include <string.h>#define MaxSize 50 typedef struct Node char data;struct Node *LeftChild;struct Node *RightChild;BiTNode;void Initiate(BiTNode *root)*root=(BiTNode *)malloc(sizeof(BiTNode);(*root)->LeftChild=NULL;(*root)->RightChild=NULL;void Visit(char item)printf

16、("%c",item);void PreOrder(BiTNode *T,void Visit(char item)if(T!=NULL)Visit(T->data);PreOrder(T->LeftChild,Visit);PreOrder(T->RightChild,Visit);void InOrder(BiTNode *T,void Visit(char item)if(T!=NULL)InOrder(T->LeftChild,Visit);Visit(T->data);InOrder(T->RightChild,Visit);v

17、oid PostOrder(BiTNode *T,void Visit(char item)if(T!=NULL)PostOrder(T->LeftChild,Visit);PostOrder(T->RightChild,Visit);Visit(T->data);void PrintBiTree(BiTNode *T,int n)int i;if(T=NULL) return;PrintBiTree(T->RightChild,n+1);for(i=0;i<n;i+) printf(" ");if(n>=0) printf("

18、 ");printf("%cnn",T->data);PrintBiTree(T->LeftChild,n+1);void CreateTree(BiTNode *T,int pre_f,int pre_l,int in_f,int in_l,char pre,char in)int interval=0;/int same=in_f;if(prepre_f!=insame) while(prepre_f!=insame)/ 在中序序列中找到根節點same+;interval+;if(interval=0)&&(pre_f=pre_l)

19、 / 找到了葉節點，也是遞歸出口T->data=prepre_f;T->LeftChild=NULL;T->RightChild=NULL;if(interval!=0)&&(interval<pre_l-pre_f) /同時存在左子樹和右子樹T->LeftChild=(BiTNode *)malloc(sizeof(BiTNode);T->RightChild=(BiTNode *)malloc(sizeof(BiTNode);T->data=prepre_f;CreateTree(T->LeftChild,pre_f+1,pr

20、e_f+interval,in_f,in_f+interval-1,p re,in);CreateTree(T->RightChild,pre_f+interval+1,pre_l,in_f+interval+1,in_l, pre,in);if(interval!=0)&&(interval=pre_l-pre_f)/只有左子樹T->LeftChild=(BiTNode *)malloc(sizeof(BiTNode);T->data=prepre_f;CreateTree(T->LeftChild,pre_f+1,pre_l,in_f,in_f+interval-1,pre,in);T->RightChild=NULL;if(interval=0)&&(pre_f!=pre_l)/ 只有右子樹T->RightChild=(BiTNode *)malloc(sizeof(BiT