通軟答辯_二叉樹遍歷問題

1、通信軟件基礎(chǔ)選題：5 二叉樹練習(xí)小組成員：三枚銅錢94keyboard 時(shí)間：2015/6/1實(shí)訓(xùn)答辯二叉樹練習(xí)THE LAST TIME二叉樹練習(xí) 以先序輸入方式創(chuàng)建二叉樹； 對(duì)該二叉樹進(jìn)行先序遍歷； 用程序?qū)崿F(xiàn)由先序序列和中序序列確定該二叉樹；1分析問題2確定框架3實(shí)現(xiàn)程序1分析問題p 算法思想：p 先序創(chuàng)建二叉樹 若二叉樹為空，返回空，創(chuàng)建結(jié)束；否則進(jìn)行以下操作1) 輸入根節(jié)點(diǎn)；2) 先序遞歸 輸入創(chuàng)建根節(jié)點(diǎn)的左子樹；3) 先序遞歸 輸入創(chuàng)建根節(jié)點(diǎn)的右子列；分析1p 使用遞歸的方法，實(shí)現(xiàn)二叉樹的前序輸入創(chuàng)建及遍歷p 輸入：一顆樹的前序遍歷，用#代替節(jié)點(diǎn)的左（右）孩子為空p 例如，前序序列

2、：ABD#E#C#ABCDE#p 算法思想：p 先序遍歷二叉樹 若二叉樹為空，遍歷結(jié)束；否則進(jìn)行以下操作1) 訪問根節(jié)點(diǎn)；2) 先序遍歷根節(jié)點(diǎn)的左子樹；3) 先序遍歷根節(jié)點(diǎn)的右子列；分析2p 一個(gè)先序遍歷序列和一個(gè)中序遍歷序列可以確定一顆唯一的二叉樹。 u 根據(jù)先序遍歷的特點(diǎn)可知先序序列(DLR)的首個(gè)元素(Pre 0)為二叉樹的根(root)u 然后在中序序列(LDR)中查找此根(root)u 根據(jù)中序遍歷特點(diǎn)可知在查找到的根(root) 前邊的序列為根的左子樹的中序遍歷序列, 后邊的序列為根的右子樹的中序遍歷序列 u 設(shè)在中序遍歷序列(LDR)根前邊有l(wèi)eft個(gè)元素，則在前序序列(DLR)

3、中，緊跟著根(root)的left個(gè)元素序列(即Pre 1.left) 為根的左子樹的先序遍歷序列，在后邊的為根的右子樹的先序遍歷序列；而構(gòu)造左子樹問題其實(shí)跟構(gòu)造整個(gè)二叉樹問題一樣，只是此時(shí)前序序列為Pre 1.left)，中序序列為In 0.left-1，分別為原序列的子串，構(gòu)造右子樹同樣， 顯然可以用遞歸方法解決 先序： root | 左子樹 | 右子樹 中序： 左子樹 | root | 右子樹p 遞歸實(shí)現(xiàn)： 遞歸函數(shù)輸入：二叉樹的先序序列和中序序列；返回：建好的二叉樹的根節(jié)點(diǎn)。p 算法思想：1) 若二叉樹空，返回空；2) 若不空，取先序序列第一個(gè)元素，建立根節(jié)點(diǎn)；3) 在中序序列中查找根

4、節(jié)點(diǎn)，以此確定左右子樹的先序序列和中序序列；4) 遞歸調(diào)用自己，建左子樹；5) 遞歸調(diào)用自己，建右子樹。 1定義字符指針變量指向字符串2輸入前序、中序序列的字符串3遞歸實(shí)現(xiàn)恢復(fù)二叉樹4后序遍歷以確定二叉樹p 確定二叉樹的方法： 恢復(fù)二叉樹后對(duì)它進(jìn)行后序遍歷 來(lái)確定唯一的二叉樹；2確定框架開始Flag=1Flag=0?是否你的輸入有誤 ;Switch(case)DLRcreat（）；結(jié)束case=1 case=2case=3default否否否BTreeFronMid()；LRD(tree);Flag=-1；break ;是是是是/按照前序遍歷的順序創(chuàng)建二叉樹BTNode *CreateTree

5、( ) 創(chuàng)建根節(jié)點(diǎn)； CreateTree (左子樹)； CreateTree (右子樹)； /先序+中序恢復(fù)二叉樹，遞歸MakeBTree(.) 得到root 根結(jié)點(diǎn) MakeBTree( 左子樹 ); MakeBTree( 右子樹 ); 是否root=NULL;return;當(dāng)前節(jié)點(diǎn)創(chuàng)建為 root當(dāng)前節(jié)點(diǎn)=NULL ?當(dāng)前節(jié)點(diǎn)指向左子樹開始當(dāng)前節(jié)點(diǎn)指向右子樹結(jié)束 / 按照前序遍歷的順序創(chuàng)建二叉樹節(jié)點(diǎn) getroot(前序，中序)c= （前序第 0 個(gè)字符）pos= （c 在中序中的位置）len1= 中序pos左半部分長(zhǎng)度len2= 中序pos右半部分長(zhǎng)度新建節(jié)點(diǎn) r，令 r 的元素等于c

6、r 的左兒子=getroot(前序位置1開始的len1長(zhǎng)度部分，中序pos位置的左半部分)r 的右兒子=getroot(前序位置len1的右半部分，中序pos位置的右半部分)return rfm/ 先序+中序恢復(fù)二叉樹，遞歸fl=0; fr=strlen(f);ml=0; mr=strlen(m);建立左子樹 遞歸調(diào)用參數(shù)設(shè)置 fl+1；fl+pos-ml；ml；pos-1m序列長(zhǎng)度 ?是否m序列中 pos從當(dāng)前序列首個(gè)位置ml移動(dòng)到 fl元素在m序列的位置左、右子樹設(shè)為NULL否當(dāng)前前序序列的第 fl 個(gè)元素創(chuàng)建為根節(jié)點(diǎn)是開始m序列長(zhǎng)度1 ?pos過序列邊界？fl 移動(dòng)至左子樹序列尾；建立右

7、子樹 遞歸調(diào)用 參數(shù)設(shè)置 fl+1；fr；pos+1；mr輸入錯(cuò)誤結(jié)束結(jié)束否是3實(shí)現(xiàn)程序/ 二叉樹的節(jié)點(diǎn)定義typedef struct node char data; struct node *rchild; / 左孩子節(jié)點(diǎn)struct node *lchild; / 右孩子節(jié)點(diǎn) BTNode,*TNode; / 樹的初始化void Init(BTNode *t) t-lchild = NULL; t-rchild=t-lchild;BTNode *DLRcreate() /先序輸入建立二叉樹 char ch;BTNode *root;ch=getchar();if(ch=#) root=N

8、ULL; /讀入#，返回空指針else / 生成節(jié)點(diǎn) root=(BTNode *)malloc(sizeof(BTNode); root-data=ch; /節(jié)點(diǎn)數(shù)據(jù)root-lchild=DLRcreate(); /構(gòu)造左子樹root-rchild=DLRcreate(); /構(gòu)造右子樹return root;二叉樹創(chuàng)建 LRD(TNode tree) /后序查找 if (tree!=NULL) LRD(tree-lchild); LRD(tree-rchild); printf(%c,tree-data); void DLR(BTNode *t) /先序遍歷 if(t=NULL) ret

9、urn; printf(%c,t-data); DLR(t-lchild); DLR(t-rchild); freetree(TNode tree) /釋放樹 if (tree!=NULL) freetree(tree-lchild); freetree(tree-rchild); 二叉樹基本操作算法BTreeFronMid ( TNode *tree,char *Fron,char *Mid,int fl,int fr,int ml,int mr ) int pos; if (mldata=Fronfl;/本棵樹根節(jié)點(diǎn)確定即先序第一個(gè)元素(*tree)-lchild=NULL; (*tree

10、)-rchild=NULL;if (mlmr) pos=ml;while(Midpos!=Fronfl&poslchild),Fron,Mid,fl+1,fl+pos-ml,ml,pos-1); /建左子樹fl+=pos-ml;BTreeFronMid(&(*tree)-rchild),Fron,Mid,fl+1,fr,pos+1,mr); /建右子樹 / 根據(jù)前序序列中序序列恢復(fù)唯一的二叉樹/定義二叉樹根節(jié)點(diǎn)指針TNode *tree；/前序、中序字符串指針char char *Fron，char *Mid；/前序序列位置號(hào)（開始、結(jié)束位置）int fl，int fr；/中序序列位置號(hào)（開始

11、、結(jié)束位置）int ml，int mr void main() int i, cycle=0; / 選擇和結(jié)束標(biāo)志位 BTNode *t; TNode tree=NULL; char *Fronarr=(char*)malloc(sizeof(char)*50); /前序序列 char *midarr=(char*)malloc(sizeof(char)*50); /中序序列 while(cycle!=(-1) printf(*n); printf(“ 先序創(chuàng)建并先序輸出 請(qǐng)按：1n); printf( 由先序中序確定二叉樹并后序輸出 請(qǐng)按：2n); printf(“ 退出 請(qǐng)按：3nn);

12、printf(*n); 主函數(shù)/將創(chuàng)建二叉樹的函數(shù)的首地址賦給指針變量t;/前序遍歷t; printf(n); printf(請(qǐng)選擇你的操作：n);scanf(%d,&i);switch(i) case 1: printf(input the string:);t=DLRcreate();printf(The preorder is:);DLR(t); printf(n); break;調(diào)用恢復(fù)二叉樹函數(shù)；p 輸入前序，中序序列p 判斷兩個(gè)序列長(zhǎng)度是否一致p 調(diào)用函數(shù)恢復(fù)二叉樹p 后序遍歷二叉樹p 釋放二叉樹case 2:while(1) printf(Please input preorde

13、r:);scanf(%s,Fronarr);printf(Please input midorder:);scanf(%s,midarr);if (strlen(Fronarr)!=strlen(midarr)printf(wrong input! Please input agin!n);else break; BTreeFronMid (&tree,Fronarr,midarr,0, strlen(Fronarr)-1,0,strlen(midarr)-1);printf(Postorder is:);poster(tree);printf(n);freetree(tree);break;指定 輸入3 為退出程序若輸入非指定（1、2、3外）值，提示輸入有誤，重新輸入case 3:cycle=(-1);break;default:printf(n); printf(你的輸入有誤!n);printf(n Press Enter Contiue! n);getchar();while(getchar()!=n);break;調(diào)試 1p 例如，前