唯一的確定一棵二叉樹

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

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

3、（ 1）函數(shù)調(diào)用關(guān)系圖： main InitiateCreateTree PrintBiTreePreOrder VisitInOrder Visit PostOrder( 2)函數(shù)接口規(guī)格說明：void Initiate(BiTNode *root)/ 初始化二叉樹的頭結(jié)點(diǎn)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)建二叉樹實(shí)現(xiàn)注釋（ 1）根據(jù)前序遍歷和后序遍歷創(chuàng)建二叉樹，并后序遍歷該二叉樹。（ 2）二叉樹逆轉(zhuǎn)90 度來顯示。詳細(xì)設(shè)計(jì)總體來說，本程序設(shè)計(jì)相對(duì)比較簡單，主要包括七個(gè)功能模塊：初始化函數(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é)點(diǎn)same+;interval+;if(interval=0)&&(pre_f=pre_l) / 找到了葉節(jié)點(diǎn)，也是遞歸出口T->data=prepre_f;T->LeftChild=NULL;T->RightChild=NULL;if(interval!=0)&&(interval<pre_l-pre_f) /同時(shí)存在左子樹和右子樹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(" 請(qǐng)輸入前序序列：n");scanf("%s",&Pre);Pre_len=strlen(Pre);printf(" 請(qǐng)輸入中序序列：

12、n");scanf("%s",&In);In_len=strlen(In);Initiate(&T);CreateTree(T,0,Pre_len-1,0,In_len-1,Pre,In);printf(" 二叉樹構(gòu)造成功！n");printf("逆時(shí)針旋轉(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)試分析：本程序在設(shè)計(jì)過程中遇到一個(gè)難題，那就是如何正確顯示所構(gòu)造的二叉樹，試了幾種方法都不理想，最后想到讓二叉樹逆時(shí)針旋轉(zhuǎn)后再顯示，具備可行性，同時(shí)也使之更美觀。經(jīng)驗(yàn)和體會(huì)經(jīng)過第一次一元稀疏多項(xiàng)式加法的課程設(shè)計(jì)，這次課程設(shè)計(jì)就顯得輕車熟路了，運(yùn)算的主要設(shè)計(jì)思路很容易想到，大體設(shè)計(jì)結(jié)構(gòu)在較短時(shí)間內(nèi)能夠完成，但當(dāng)設(shè)計(jì)到具體細(xì)節(jié)代碼時(shí)遇到了一些困難，主要困難是進(jìn)行結(jié)點(diǎn)操作時(shí)，對(duì)指針考慮得不夠細(xì)致，調(diào)試時(shí)常出現(xiàn)指針指錯(cuò)的情況，沒有認(rèn)真理清條件層次，另一個(gè)困難是如何正確

14、顯示所構(gòu)造的二叉樹。雖然程序可能并不是最高效的，而且不夠健壯，但也符合題目的要求，總的來說本次課程設(shè)計(jì)還算圓滿。本次課程設(shè)計(jì)培養(yǎng)了我對(duì)實(shí)際問題的分析能力以及解決一些實(shí)際問題的能力， 鞏固了我的編程思想和寫程序的能力。課程設(shè)計(jì)是對(duì)我們的學(xué)習(xí)很有利的一個(gè)環(huán)節(jié)， 在這個(gè)階段，我們學(xué)會(huì)把理論與實(shí)際的結(jié)合、懂得人與人溝通的重要性，通過這次課程設(shè)計(jì)中，我加深了對(duì)課本知識(shí)的理解。四、用戶手冊(cè)：本 程 序 在 Vi sual C + 6. 0 下 運(yùn) 行 。先輸入前序遍歷序列，回車，再輸入中序遍歷序列，再回車，即可得出結(jié)果。五、運(yùn)行結(jié)果：六、源程序清單：#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é)點(diǎn)same+;interval+;if(interval=0)&&(pre_f=pre_l)

19、 / 找到了葉節(jié)點(diǎn)，也是遞歸出口T->data=prepre_f;T->LeftChild=NULL;T->RightChild=NULL;if(interval!=0)&&(interval<pre_l-pre_f) /同時(shí)存在左子樹和右子樹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