唯一的確定一棵二叉樹

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

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

3、（ 1）函數(shù)調(diào)用關系圖： main InitiateCreateTree PrintBiTreePreOrder VisitInOrder Visit PostOrder( 2)函數(shù)接口規(guī)格說明：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)/ 按要求創(chuàng)建二叉樹實現(xiàn)注釋（ 1）根據(jù)前序遍歷和后序遍歷創(chuàng)建二叉樹，并后序遍歷該二叉樹。（ 2）二叉樹逆轉(zhuǎn)90 度來顯示。詳細設計總體來說，本程序設計相對比較簡單，主要包括七個功能模塊：初始化函數(shù)、 前序遍歷二叉樹函數(shù)、中序遍歷二叉樹函數(shù)、后序遍歷二叉樹函數(shù)、顯示函數(shù)、創(chuàng)建二叉樹函數(shù)、主函數(shù)。下面

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

6、nOrder(BiTNode *T,void Visit(char item)if(T!=NULL)InOrder(T->LeftChild,Visit);Visit(T->data);InOrder(T->RightChild,Visit);后序遍歷二叉樹函數(shù)void PostOrder(BiTNode *T,void Visit(char item) if(T!=NULL)PostOrder(T->LeftChild,Visit);PostOrder(T->RightChild,Visit);Visit(T->data);顯示函數(shù)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);創(chuàng)建二叉樹函數(shù)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)/ 在中序序列中找到根節(jié)點same+;interval+;if(interval=0)&&(pre_f=pre_l) / 找到了葉節(jié)點，也是遞歸出口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);主函數(shù)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("逆時針旋轉(zhuǎn)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");三、調(diào)試分析：本程序在設計過程中遇到一個難題，那就是如何正確顯示所構造的二叉樹，試了幾種方法都不理想，最后想到讓二叉樹逆時針旋轉(zhuǎn)后再顯示，具備可行性，同時也使之更美觀。經(jīng)驗和體會經(jīng)過第一次一元稀疏多項式加法的課程設計，這次課程設計就顯得輕車熟路了，運算的主要設計思路很容易想到，大體設計結構在較短時間內(nèi)能夠完成，但當設計到具體細節(jié)代碼時遇到了一些困難，主要困難是進行結點操作時，對指針考慮得不夠細致，調(diào)試時常出現(xiàn)指針指錯的情況，沒有認真理清條件層次，另一個困難是如何正確

14、顯示所構造的二叉樹。雖然程序可能并不是最高效的，而且不夠健壯，但也符合題目的要求，總的來說本次課程設計還算圓滿。本次課程設計培養(yǎng)了我對實際問題的分析能力以及解決一些實際問題的能力， 鞏固了我的編程思想和寫程序的能力。課程設計是對我們的學習很有利的一個環(huán)節(jié)， 在這個階段，我們學會把理論與實際的結合、懂得人與人溝通的重要性，通過這次課程設計中，我加深了對課本知識的理解。四、用戶手冊：本 程 序 在 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)/ 在中序序列中找到根節(jié)點same+;interval+;if(interval=0)&&(pre_f=pre_l)

19、 / 找到了葉節(jié)點，也是遞歸出口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