二叉樹的建立與遍歷.doc

《二叉樹的建立與遍歷.doc》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、個人收集整理勿做商業(yè)用途實踐考核題第二題設(shè)計報告書學(xué)生姓名?XXX學(xué)生學(xué)號0９XXX所在地區(qū)XXX提交日期(年/月）２014/6實踐題目實現(xiàn)二叉樹的建立與遍歷?需求分析?（1）以二叉鏈表作為存儲結(jié)構(gòu),定義二叉樹類型Ｂitｒee　定義二叉鏈表的存儲結(jié)構(gòu),可以更好地對二叉表的操作，在二叉鏈表中,datａ域用于存儲二叉樹節(jié)點中的數(shù)據(jù)信息；lchiｌｄ是指向左孩子的指針(左指針）。類似的，rchild是指向右孩子的指針（右指針）。此外，每個二叉鏈表還必須有一個指向根節(jié)點的指針，該指針稱為根指針。與鏈表頭指針類似,根指針具有標識二叉鏈表

2、的作用，對二叉鏈表的訪問只能從根指針開始。若果某個節(jié)點的右孩子或者左孩子不存在時,則相應(yīng)指針數(shù)據(jù)域為空(#)。由此可知葉節(jié)點的左右指針必為空（#）。(２)實現(xiàn)二叉樹的以下運算<1＞建立vｏid　CreateBiＴree（BiTreｅ＊T）　輸入二叉樹的結(jié)點元素,建立二叉鏈表　　　　建立voｉｄ?。胷eateBｉTree(BiTrｅe?。?函數(shù)可以往二叉鏈表中輸入數(shù)據(jù)和向左右指針的指向是否為#,只有建立了二叉鏈表才能通過調(diào)用先序遍歷、中序遍歷和后序遍歷的函數(shù)遍歷出二叉樹中的數(shù)據(jù)。<２>選擇一種遍歷方式（先序、中序、后序)遍歷這

3、棵二叉樹通過選擇遍歷方式，遍歷同一顆二叉樹，遍歷的次序是不同的，遍歷的方法也是不一樣的，通過不同的遍歷方式的得到二叉樹的順序是不一樣,但是都是為了得到二叉樹最后的排序。通過先序遍歷，先訪問的是根節(jié)點，然后是左子樹,最后是右子樹。中序遍歷，先遍歷左子樹，在訪問根節(jié)點，最后遍歷右子樹。后序遍歷,先遍歷左子樹,在遍歷右子樹,左后訪問根節(jié)點。通過不同的排序方式可以確定一棵唯一的二叉樹。概要設(shè)計個人收集整理勿做商業(yè)用途（1）建立二叉鏈表:　voidCreateBiTreｅ(BｉTree　*T)　　首先，定義一個結(jié)構(gòu)體,存儲每個節(jié)點的信息

4、，并給這個結(jié)構(gòu)體定義別名為Bittree;這個結(jié)構(gòu)體中的數(shù)據(jù)元素有，保存數(shù)據(jù)的類型,還有指向左右孩子的指針它的類型和結(jié)構(gòu)體的類型一樣。（2）實現(xiàn)二叉樹的以下運算選擇一種遍歷方式（先序、中序、后序)遍歷這棵二叉樹　先序遍歷:void　PrｅＯrder（BiTree　T)若被遍歷的二叉樹為空,執(zhí)行空操作；否則，依次執(zhí)行下列操作:　　訪問根節(jié)點；　　　　先序遍歷左子樹;　　　　　先序遍歷右子樹。中序遍歷：ｖoid　InOrdeｒ（BiTｒｅｅT若被遍歷的二叉樹為空，執(zhí)行空操作;否則，依次執(zhí)行下列操作：中序遍歷左子樹;訪問根節(jié)點；中序

5、遍歷右子樹。后序遍歷:ｖoｉｄ　PｏstOｒｄer(BiTｒeeT)若被遍歷的二叉樹為空,執(zhí)行空操作;否則,依次執(zhí)行下列操作:后序遍歷左子樹；后序遍歷右子樹;訪問根節(jié)點。上面給出的先序遍歷、中序遍歷和后序遍歷的定義都是遞歸的，因而根據(jù)定義很容易得到相應(yīng)遍歷的遞歸算法。詳細設(shè)計個人收集整理勿做商業(yè)用途?#include#include＃inclｕdｅ<ｍａｌloc.h>typedefcharTElｅｍTｙpｅ;typedef　sｔruct?。樱耰ＴNｏde{　　TEleｍTypｅdａｔａ;ｓ

6、ｔructSBiTＮode*lchilｄ,＊rchild;}BiTNodｅ,*ＢiTree;//采用左序遍歷創(chuàng)建二叉樹，用到的是遞歸算法，參數(shù)指針T有點晦澀難懂。ｖoidCreａt(yī)eBｉTree(ＢｉTreｅ*Ｔ）{　ＴElｅｍＴypeｃｈ;　　scanｆ(＂%c＂,&ch);if(cｈ＝＝'＃'）　　　*T=ＮULL;　　　else{　　*T=(BiTree)ｍalloc（siｚeoｆ(BｉTNoｄe)　)；　　　　if(！*T)　　　　　　exit(-1);?。?T）->datａ＝cｈ;　　　Creａt(yī)eBiＴreｅ(＆(

7、＊T)-＞lchild);個人收集整理勿做商業(yè)用途　CreateBiTｒeｅ(&(*T)->rｃｈｉｌd）;　?。齷//輸出函數(shù)voidVｉｓit(BｉTree　T)｛?if（T－>ｄａｔa!='＃'){?printｆ("％ｃ",Ｔ->ｄata)；?}}//先序遍歷ｖｏidＰrｅOrｄer(BiTreeT){if(T！=NULL）{?／/訪問根節(jié)點?Vｉsiｔ（Ｔ);?／／訪問左子結(jié)點?PreOrdｅr(T->lchild);?／／訪問右子結(jié)點PreOｒｄｅr(T->ｒcｈild);}}//中序遍歷vｏiｄInOrder（Ｂi

8、TreeT){個人收集整理勿做商業(yè)用途　?。?判斷是否為空ｉf(T!=NULＬ)　　?。?/中序訪問左子樹InOrdeｒ(Ｔ->lchiｌd);　　　/／訪問根節(jié)點?。謎sit(T);　　//中序訪問右子樹　　InOrder(T-＞ｒｃhiｌd);　｝}/／后序遍歷voidP