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

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

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

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

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

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

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

7、子樹 遞歸調用 參數(shù)設置 fl+1；fr；pos+1；mr輸入錯誤結束結束否是3實現(xiàn)程序/ 二叉樹的節(jié)點定義typedef struct node char data; struct node *rchild; / 左孩子節(jié)點struct node *lchild; / 右孩子節(jié)點 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é)點 root=(BTNode *)malloc(sizeof(BTNode); root-data=ch; /節(jié)點數(shù)據(jù)root-lchild=DLRcreate(); /構造左子樹root-rchild=DLRcreate(); /構造右子樹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é)點確定即先序第一個元素(*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ù)前序序列中序序列恢復唯一的二叉樹/定義二叉樹根節(jié)點指針TNode *tree；/前序、中序字符串指針char char *Fron，char *Mid；/前序序列位置號（開始、結束位置）int fl，int fr；/中序序列位置號（開始

11、、結束位置）int ml，int mr void main() int i, cycle=0; / 選擇和結束標志位 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)建并先序輸出 請按：1n); printf( 由先序中序確定二叉樹并后序輸出 請按：2n); printf(“ 退出 請按：3nn);

12、printf(*n); 主函數(shù)/將創(chuàng)建二叉樹的函數(shù)的首地址賦給指針變量t;/前序遍歷t; printf(n); printf(請選擇你的操作：n);scanf(%d,&i);switch(i) case 1: printf(input the string:);t=DLRcreate();printf(The preorder is:);DLR(t); printf(n); break;調用恢復二叉樹函數(shù)；p 輸入前序，中序序列p 判斷兩個序列長度是否一致p 調用函數(shù)恢復二叉樹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;調試 1p 例如，前