數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)五(二叉樹(shù)的建立及遍歷)題目和源程序

《數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)五(二叉樹(shù)的建立及遍歷)題目和源程序》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在工程資料-天天文庫(kù)。

1、實(shí)驗(yàn)5：二叉樹(shù)的建立及遍歷（第十三周星期三7、8節(jié)）一、實(shí)驗(yàn)?zāi)康?．學(xué)會(huì)實(shí)現(xiàn)二叉樹(shù)結(jié)點(diǎn)結(jié)構(gòu)和對(duì)二叉樹(shù)的基本操作。2．掌握對(duì)二叉樹(shù)每種操作的具體實(shí)現(xiàn)，學(xué)會(huì)利用遞歸方法編寫(xiě)對(duì)二叉樹(shù)這種遞歸數(shù)據(jù)結(jié)構(gòu)進(jìn)行處理的算法。二、實(shí)驗(yàn)要求1．認(rèn)真閱讀和掌握和本實(shí)驗(yàn)相關(guān)的教材內(nèi)容。2．編寫(xiě)完整程序完成下面的實(shí)驗(yàn)內(nèi)容并上機(jī)運(yùn)行。3．整理并上交實(shí)驗(yàn)報(bào)告。三、實(shí)驗(yàn)內(nèi)容1．編寫(xiě)程序任意輸入二叉樹(shù)的結(jié)點(diǎn)個(gè)數(shù)和結(jié)點(diǎn)值，構(gòu)造一棵二叉樹(shù)，采用三種遞歸遍歷算法(前序、中序、后序)對(duì)這棵二叉樹(shù)進(jìn)行遍歷并計(jì)算出二叉樹(shù)的高度。2.編寫(xiě)程序生成下面所示的二叉樹(shù)，并采用中序遍歷的非遞歸算法對(duì)此二叉樹(shù)進(jìn)行遍歷。四、思考與提高1．如何計(jì)

2、算二叉鏈表存儲(chǔ)的二叉樹(shù)中度數(shù)為1的結(jié)點(diǎn)數(shù)？2．已知有—棵以二叉鏈表存儲(chǔ)的二叉樹(shù)，root指向根結(jié)點(diǎn)，p指向二叉樹(shù)中任一結(jié)點(diǎn)，如何求從根結(jié)點(diǎn)到p所指結(jié)點(diǎn)之間的路徑?/*----------------------------------------*05-1_遞歸遍歷二叉樹(shù).cpp--遞歸遍歷二叉樹(shù)的相關(guān)操作*對(duì)遞歸遍歷二叉樹(shù)的每個(gè)基本操作都用單獨(dú)的函數(shù)來(lái)實(shí)現(xiàn)*水上飄2009年寫(xiě)----------------------------------------*///ds05.cpp:Definestheentrypointfortheconsoleapplication.//#inclu

3、de"stdafx.h"#includetypedefcharElemType;usingnamespacestd;typedefstructBiTNode{ElemTypedata;//左右孩子指針BiTNode*lchild,*rchild;}BiTNode,*BiTree;//動(dòng)態(tài)輸入字符按先序創(chuàng)建二叉樹(shù)voidCreateBiTree(BiTree&T){charch;ch=cin.get();if(ch==''){T=NULL;}else{if(ch==''){cout<<"輸入未結(jié)束前不要輸入回車，""要結(jié)束分支請(qǐng)輸入空格！"<

4、{//生成根結(jié)點(diǎn)T=(BiTNode*)malloc(sizeof(BiTNode));if(!T)cout<<"內(nèi)存分配失敗！"<data=ch;//構(gòu)造左子樹(shù)CreateBiTree(T->lchild);//構(gòu)造右子樹(shù)CreateBiTree(T->rchild);}}}//輸出e的值ElemTypePrintElement(ElemTypee){cout<data);//遍歷左孩子Pre

5、OrderTraverse(T->lchild);//遍歷右孩子PreOrderTraverse(T->rchild);}}//中序遍歷voidInOrderTraverse(BiTreeT){if(T!=NULL){//遍歷左孩子InOrderTraverse(T->lchild);//打印結(jié)點(diǎn)的值PrintElement(T->data);//遍歷右孩子InOrderTraverse(T->rchild);}}//后序遍歷voidPostOrderTraverse(BiTreeT){if(T!=NULL){//遍歷左孩子PostOrderTraverse(T->lchild);//

6、遍歷右孩子PostOrderTraverse(T->rchild);//打印結(jié)點(diǎn)的值PrintElement(T->data);}}//按任一種遍歷次序輸出二叉樹(shù)中的所有結(jié)點(diǎn)voidTraverseBiTree(BiTreeT,intmark){if(mark==1){//先序遍歷PreOrderTraverse(T);cout<

7、結(jié)束！"<>mark;if(mark>0&&mark<4){TraverseBiTree(T,mark);ChoiceMark(T);}elsecout<<"此操作已跳過(guò)！"<