實(shí)習(xí)二 【唯一的確定一顆二叉樹】

1、實(shí)習(xí)二1.需求分析：【問題描述】：如果給出了遍歷二叉樹的前序序列和中序序列，則可以構(gòu)造出唯一的二叉樹。試編寫實(shí)現(xiàn)上述功能的程序。【基本要求】：已知一顆二叉樹的前序和中序序列，試設(shè)計完成下列任務(wù)的一個算法。（1）構(gòu)造一顆二叉樹。（2）證明構(gòu)造正確（即分別以前序和中序遍歷該樹，將得到的結(jié)果與給出的序列進(jìn)行比較）。（3）對該二叉樹進(jìn)行后序遍歷，輸出后續(xù)遍歷序列。（4）用凹入法輸出該二叉樹?！鹃_發(fā)環(huán)境】：系統(tǒng)：windows7編程軟件：VC+6.02.設(shè)計： 給定二叉樹結(jié)點(diǎn)的前序序列和中序序列，可以唯一確定該二叉樹。因?yàn)榍靶蛐蛄械牡谝粋€元素是根結(jié)點(diǎn)，該元素將二叉樹中序序列分成兩部分，左邊（設(shè)l個元素）

2、表示左子樹，若左邊無元素，則說明左子樹為空；右邊（設(shè)r個元素）是右子樹，若為空，則右子樹為空。根據(jù)前序遍歷中“根左子樹右子樹”的順序，則由從第二元素開始的l個結(jié)點(diǎn)序列和中序序列根左邊的l個結(jié)點(diǎn)構(gòu)成左子樹，由前序序列最后r個元素序列與中序序列根右邊的r個元素序列構(gòu)造右子樹。假設(shè)一棵二叉樹中結(jié)點(diǎn)的個數(shù)為n, 即該棵二叉樹的前序遍歷序列為q1, q2, q3, , qn , 中序遍歷序列為z 1, z 2, z 3, , z n , 用數(shù)學(xué)歸納法證明由這兩個序列能夠唯一地確定一棵二叉樹B t.當(dāng)n= 1 時, 即前序遍歷序列和中序遍歷序列均只有一個元素, 且相同, 即為樹的根, 由此唯一地確定了一棵

3、二叉樹?，F(xiàn)在假設(shè)n< m - 1 時命題成立, 則需要證明當(dāng)n= m 時亦成立。當(dāng)n= m 時, 前序序列為q1, q2, q3, , qm , 中序序列為z 1, z 2, z 3, , zm. 因?yàn)榍靶蛐蛄杏汕靶虮闅v二叉樹所得, 則q1必為根結(jié)點(diǎn)這個元素; 又中序序列由中序遍歷二叉樹所得, 則在中序序列中必能找到和q1相同的元素, 設(shè)為z j , 由此z 1, z 2, , z j - 1 為左子樹的中序序列, z j+ 1, z j+ 2, , zm 為右子樹的中序序列。若j= 1, 即z 1 為根, 此時二叉樹的左子樹為空, q2, q3, , qm 為左子樹的前序序列, z 2

4、, z 3, , zm 為右子樹的中序序列。右子樹的結(jié)點(diǎn)數(shù)為m - 1, 根據(jù)假設(shè), 這兩個序列唯一確定了一棵右子樹。因此,唯一確定的一棵二叉樹是由z 1 為根, 該棵右子樹為右子樹(唯一確定的這棵二叉樹無左子樹) 來構(gòu)成。若j= m , 即zm 為根, 此時二叉樹的右子樹為空, q1, q2, , qm - 1 為左子樹的前序序列, z 1, z 2, ,zm - 1 為左子樹的中序序列。 左子樹的結(jié)點(diǎn)數(shù)為m - 1, 根據(jù)假設(shè), 這兩個序列唯一地確定了一棵左子樹。因此, 唯一確定的一棵二叉樹是由zm 為根, 該棵左子樹為左子樹(唯一確定的這棵二叉樹無右子樹) 來構(gòu)成。若2< j<

5、; m - 1, 則子序列q1, q2, ,qj - 1 和z 1, z 2, , z j - 1 根據(jù)假設(shè)可知, 它們唯一地確定了一棵左子樹。 同理, 子序列qj+ 1, qj+ 2, qm 和z j+ 1, z j+ 2 , , zm 唯一地確定了一棵右子樹。 前者確定的左子樹與后者確定的右子樹及z j可唯一地確定一棵二叉樹。 由此, 從理論上證明了由一棵二叉樹的前序遍歷序列和中序遍歷序列能夠唯一確定一棵二叉樹。 同理, 即由一棵二叉樹的后序遍歷序列和中序遍歷序列, 也能夠唯一地確定一棵二叉樹。具體思想例如： 前序序列為ABDEGCFHIJ， 中序遍歷為DBGEAHFIJC由前序遍歷可確定

6、根為A，中序遍歷可得A的左右子樹分別包含結(jié)點(diǎn)有DBGE、HFIJC構(gòu)造A的左子樹：A的左子樹分別包含結(jié)點(diǎn)有DBGE，由前序遍歷可知B為根結(jié)點(diǎn)，B的左右子樹分別包含結(jié)點(diǎn)有D、GE。則B的左子樹為就為D，然后構(gòu)造B右子樹，由前序遍歷可知E為根結(jié)點(diǎn)，B的右子樹的中序遍歷知G為E的左孩子。同理可以構(gòu)造出A的右孩子結(jié)構(gòu)體定義：typedef struct NodeDataType data;struct Node *leftChild;/左指數(shù)指針struct Node *rightChild;/右指數(shù)指針BiTreeNode;/結(jié)點(diǎn)的結(jié)構(gòu)體定義創(chuàng)建二叉樹函數(shù)：BiTreeNode *TreeCreat

7、(char *a,char b,int c)/創(chuàng)建二叉樹函數(shù)BiTreeNode *r; char pa100,pb100;int i,j,q,n;Initiate(&r);n=strlen(b);if(n=0)return NULL;elser->data=(*a);for(i=0;i<n;i+)if(bi=(*a)break;pai=bi; pai='0'q=i;for(j=0;j<c-i;j+)q+;pbj=bq;pbj='0'n=strlen(pa);r->leftChild=TreeCreat(a+1,pa,i);/插入

8、左子樹r->rightChild=TreeCreat(a+n+1,pb,c-i-1);/ 插入右子樹return r;打印二叉樹：void PrintBiTree(BiTreeNode *t,int n)/ 逆時針尋轉(zhuǎn)打印二叉樹，n為縮進(jìn)層數(shù)，初始值為0 int i;if(t=NULL)return;/遞歸出口PrintBiTree(t->rightChild,n+1);/ 遍歷打印右子樹/訪問根結(jié)點(diǎn)for(i=0;i<n;i+)printf(" ");if(n>=0)printf("-");printf("%cn&qu

9、ot;,t->data);PrintBiTree(t->leftChild,n+1);/遍歷打印左子樹void Destroy(BiTreeNode *p)/刪除二叉樹if(*p)!=NULL&&(*p)->leftChild!=NULL)Destroy(&(*p)->leftChild);if(*p)!=NULL&&(*p)->rightChild!=NULL)Destroy(&(*p)->rightChild);free(*p);3.調(diào)試分析唯一的確定一顆二叉樹在調(diào)試時，問題主要出現(xiàn)在創(chuàng)建二叉樹函數(shù)上，其中

10、需要在定義兩個數(shù)組 pa100,pb100分別存儲每次根結(jié)點(diǎn)的左右子樹。構(gòu)建二叉樹的左子樹和右子樹時，遞歸調(diào)用構(gòu)造二叉樹函數(shù)，容易出錯。后面前序，中序，后序遍歷二叉樹函數(shù)寫起來很簡單，但要理解其是怎么遞歸調(diào)用遍歷函數(shù)的，書上也給了一定的講解。二叉樹的打印函數(shù)是將二叉樹逆時針旋轉(zhuǎn)90度后得到的。4.用戶手冊運(yùn)行程序后，上面會提示你輸入二叉樹的前序序列a，輸完后回車后上面會提示你輸入二叉樹的中序序列b，然后回車后，便可以看到相應(yīng)的輸出結(jié)果，即前序遍歷，中序遍歷，后序遍歷的結(jié)果，和凹入法打印出二叉樹。5.測試結(jié)果 6.源代碼.BiTree.h.typedef struct NodeDataType

11、data;struct Node *leftChild;/左指數(shù)指針struct Node *rightChild;/右指數(shù)指針BiTreeNode;/結(jié)點(diǎn)的結(jié)構(gòu)體定義void Initiate(BiTreeNode *root)/初始化創(chuàng)建二叉樹的頭結(jié)點(diǎn)if(*root)=(BiTreeNode *)malloc(sizeof (BiTreeNode)=NULL) return ;(*root)->leftChild=NULL;(*root)->rightChild=NULL;BiTreeNode *TreeCreat(char *a,char b,int c)/創(chuàng)建二叉樹函數(shù)B

12、iTreeNode *r; char pa100,pb100;int i,j,q,n;Initiate(&r);n=strlen(b);if(n=0)return NULL;elser->data=(*a);for(i=0;i<n;i+)if(bi=(*a)break;pai=bi; pai='0'q=i;for(j=0;j<c-i;j+)q+;pbj=bq;pbj='0'n=strlen(pa);r->leftChild=TreeCreat(a+1,pa,i);/插入左子樹r->rightChild=TreeCreat(a

13、+n+1,pb,c-i-1);/ 插入右子樹return r;void PreOrder(BiTreeNode *t)/前序遍歷if(t!=NULL)printf("%c",t->data);PreOrder(t->leftChild);PreOrder(t->rightChild);void InOrder(BiTreeNode *t)/中序遍歷if(t!=NULL)InOrder(t->leftChild);printf("%c",t->data);InOrder(t->rightChild);void PostO

14、rder(BiTreeNode *t)/后序遍歷if(t!=NULL)PostOrder(t->leftChild); PostOrder(t->rightChild);printf("%c",t->data);void PrintBiTree(BiTreeNode *t,int n)/ 逆時針尋轉(zhuǎn)打印二叉樹，n為縮進(jìn)層數(shù)，初始值為0 int i;if(t=NULL)return;/遞歸出口PrintBiTree(t->rightChild,n+1);/ 遍歷打印右子樹/訪問根結(jié)點(diǎn)for(i=0;i<n;i+)printf(" &qu

15、ot;);if(n>=0)printf("-");printf("%cn",t->data);PrintBiTree(t->leftChild,n+1);/遍歷打印左子樹void Destroy(BiTreeNode *p)/刪除二叉樹if(*p)!=NULL&&(*p)->leftChild!=NULL)Destroy(&(*p)->leftChild);if(*p)!=NULL&&(*p)->rightChild!=NULL)Destroy(&(*p)->rig

16、htChild);free(*p);main.cpp#include<stdio.h>#include<malloc.h>#include<string.h>#define DataType char#include"BiTree.h"void main()BiTreeNode *root;char a100,b100;printf("請輸入前序序列a: n"); scanf("%s",a);printf("n"); printf("請輸入中序序列b: n"); scanf("%s",b);printf("nn");root=TreeCreat(a,b,strlen(a);printf("前序遍歷:n");PreOrder