二叉樹的建立與遍歷.doc

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

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

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

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

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

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

6、ｔructSBiTＮode*lchilｄ,＊rchild;}BiTNodｅ,*ＢiTree;//采用左序遍歷創(chuàng)建二叉樹，用到的是遞歸算法，參數(shù)指針T有點(diǎn)晦澀難懂。ｖoidCreａt(yī)eBｉTree(ＢｉTreｅ*Ｔ）{?。訣lｅｍＴ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);個(gè)人收集整理勿做商業(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é)點(diǎn)?Vｉsiｔ（Ｔ);?／／訪問左子結(jié)點(diǎn)?PreOrdｅr(T->lchild);?／／訪問右子結(jié)點(diǎn)PreOｒｄｅr(T->ｒcｈild);}}//中序遍歷vｏiｄInOrder（Ｂi

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