二叉樹(shù)的建立與遍歷

1、實(shí)踐考核題第二題設(shè)計(jì)報(bào)告書(shū)學(xué)生姓名XXX學(xué)生學(xué)號(hào)09XXX所在地區(qū)XXX提交日期（年/月）2014/6實(shí)踐題目實(shí)現(xiàn)二叉樹(shù)的建立與遍歷需求分析（1）以二叉鏈表作為存儲(chǔ)結(jié)構(gòu)，定義二叉樹(shù)類型 Bitree 定義二叉鏈表的存儲(chǔ)結(jié)構(gòu)，可以更好地對(duì)二叉表的操作，在二叉鏈表中，data域用于存儲(chǔ)二叉樹(shù)節(jié)點(diǎn)中的數(shù)據(jù)信息；lchild是指向左孩子的指針（左指針）。類似的，rchild是指向右孩子的指針（右指針）。此外，每個(gè)二叉鏈表還必須有一個(gè)指向根節(jié)點(diǎn)的指針，該指針?lè)Q為根指針。與鏈表頭指針類似，根指針具有標(biāo)識(shí)二叉鏈表的作用，對(duì)二叉鏈表的訪問(wèn)只能從根指針開(kāi)始。若果某個(gè)節(jié)點(diǎn)的右孩子或者左孩子不存在時(shí)，則相應(yīng)指針數(shù)據(jù)

2、域?yàn)榭眨?）。由此可知葉節(jié)點(diǎn)的左右指針必為空（#）。（2）實(shí)現(xiàn)二叉樹(shù)的以下運(yùn)算 建立 void CreateBiTree(BiTree *T) 輸入二叉樹(shù)的結(jié)點(diǎn)元素，建立二叉鏈表 建立void CreateBiTree(BiTree *T)函數(shù)可以往二叉鏈表中輸入數(shù)據(jù)和向左右指針的指向是否為#，只有建立了二叉鏈表才能通過(guò)調(diào)用先序遍歷、中序遍歷和后序遍歷的函數(shù)遍歷出二叉樹(shù)中的數(shù)據(jù)。 選擇一種遍歷方式（先序、中序、后序）遍歷這棵二叉樹(shù) 通過(guò)選擇遍歷方式，遍歷同一顆二叉樹(shù)，遍歷的次序是不同的，遍歷的方法也是不一樣的，通過(guò)不同的遍歷方式的得到二叉樹(shù)的順序是不一樣，但是都是為了得到二叉樹(shù)最后的排序。通過(guò)

3、先序遍歷，先訪問(wèn)的是根節(jié)點(diǎn)，然后是左子樹(shù)，最后是右子樹(shù)。中序遍歷，先遍歷左子樹(shù)，在訪問(wèn)根節(jié)點(diǎn)，最后遍歷右子樹(shù)。后序遍歷，先遍歷左子樹(shù)，在遍歷右子樹(shù)，左后訪問(wèn)根節(jié)點(diǎn)。通過(guò)不同的排序方式可以確定一棵唯一的二叉樹(shù)。概要設(shè)計(jì)（1） 建立二叉鏈表： void CreateBiTree(BiTree *T) 首先，定義一個(gè)結(jié)構(gòu)體，存儲(chǔ)每個(gè)節(jié)點(diǎn)的信息，并給這個(gè)結(jié)構(gòu)體定義別名為Bittree；這個(gè)結(jié)構(gòu)體中的數(shù)據(jù)元素有，保存數(shù)據(jù)的類型，還有指向左右孩子的指針?biāo)念愋秃徒Y(jié)構(gòu)體的類型一樣。（2） 實(shí)現(xiàn)二叉樹(shù)的以下運(yùn)算 選擇一種遍歷方式（先序、中序、后序）遍歷這棵二叉樹(shù) 先序遍歷：void PreOrder(BiTr

4、ee T)若被遍歷的二叉樹(shù)為空，執(zhí)行空操作；否則，依次執(zhí)行下列操作： 訪問(wèn)根節(jié)點(diǎn)； 先序遍歷左子樹(shù)； 先序遍歷右子樹(shù)。中序遍歷：void InOrder(BiTree T若被遍歷的二叉樹(shù)為空，執(zhí)行空操作；否則，依次執(zhí)行下列操作：中序遍歷左子樹(shù)；訪問(wèn)根節(jié)點(diǎn)；中序遍歷右子樹(shù)。后序遍歷：void PostOrder(BiTree T)若被遍歷的二叉樹(shù)為空，執(zhí)行空操作；否則，依次執(zhí)行下列操作：后序遍歷左子樹(shù)；后序遍歷右子樹(shù)；訪問(wèn)根節(jié)點(diǎn)。 上面給出的先序遍歷、中序遍歷和后序遍歷的定義都是遞歸的，因而根據(jù)定義很容易得到相應(yīng)遍歷的遞歸算法。詳細(xì)設(shè)計(jì)#include#include#includetypede

5、f char TElemType;typedef struct SBiTNode TElemType data; struct SBiTNode *lchild,*rchild;BiTNode,*BiTree;/采用左序遍歷創(chuàng)建二叉樹(shù)，用到的是遞歸算法，參數(shù)指針T有點(diǎn)晦澀難懂。void CreateBiTree(BiTree *T) TElemType ch; scanf(%c,&ch); if(ch=#) *T=NULL; else *T=(BiTree)malloc( sizeof(BiTNode) ); if(!*T) exit(-1); (*T)-data=ch; CreateBiTr

6、ee(&(*T)-lchild); CreateBiTree(&(*T)-rchild); /輸出函數(shù)void Visit(BiTree T)if(T-data != #)printf(%c ,T-data);/先序遍歷void PreOrder(BiTree T)if(T != NULL)/訪問(wèn)根節(jié)點(diǎn)Visit(T);/訪問(wèn)左子結(jié)點(diǎn)PreOrder(T-lchild);/訪問(wèn)右子結(jié)點(diǎn)PreOrder(T-rchild);/中序遍歷void InOrder(BiTree T) /判斷是否為空 if(T!=NULL) /中序訪問(wèn)左子樹(shù) InOrder(T-lchild); /訪問(wèn)根節(jié)點(diǎn) Visi

7、t(T); /中序訪問(wèn)右子樹(shù) InOrder(T-rchild); /后序遍歷void PostOrder(BiTree T) /判斷是否為空 if(T!=NULL) /后序訪問(wèn)左子樹(shù) PostOrder(T-lchild); /后序訪問(wèn)右子樹(shù) PostOrder(T-rchild); /訪問(wèn)根節(jié)點(diǎn) Visit(T); /主函數(shù) int main() BiTree T; printf(清數(shù)據(jù)數(shù)據(jù)（#代表空數(shù)據(jù)位，結(jié)束前不要使用回車鍵）：n); CreateBiTree(&T); /創(chuàng)建二叉樹(shù) if(T!=NULL) printf(前序遍歷n); PreOrder(T); /先序遍歷 print

8、f(n); printf(中序遍歷n); InOrder(T); /中序遍歷 printf(n); printf(后序遍歷n); PostOrder(T); /后序遍歷 printf(n); elseprintf(二叉樹(shù)為空！);getch(); return 0;調(diào)試分析輸入數(shù)據(jù)6253檢查程序執(zhí)行是否正確：輸入數(shù)據(jù)為空時(shí)，檢查程序的執(zhí)行：設(shè)計(jì)總結(jié)在二叉樹(shù)上無(wú)論采用哪種遍歷方法，都能夠訪問(wèn)遍樹(shù)中的所有結(jié)點(diǎn)。由于訪問(wèn)結(jié)點(diǎn)的順序不同，前序遍歷和中序遍歷都很難達(dá)到設(shè)計(jì)的要求（求路徑）；但采用后序遍歷二叉樹(shù)是可行的，因?yàn)楹笮虮闅v是最后訪問(wèn)根結(jié)點(diǎn)，按這個(gè)順序?qū)⒃L問(wèn)過(guò)的結(jié)點(diǎn)存儲(chǔ)到一個(gè)順序棧中，然后再輸出即可。因此，我們可以非遞歸地后序遍歷二叉樹(shù)T，