二叉樹(shù)的建立和遍歷的實(shí)驗(yàn)報(bào)告

#14(實(shí)驗(yàn)類(lèi)型：驗(yàn)證型)1)問(wèn)題描述：在主程序中設(shè)計(jì)一個(gè)簡(jiǎn)單的菜單，分別調(diào)用相應(yīng)的函數(shù)功能：1…建立樹(shù)2…前序遍歷樹(shù)3…中序遍歷樹(shù)4…后序遍歷樹(shù)5…求二叉樹(shù)的高度6…求二叉樹(shù)的葉子節(jié)點(diǎn)7…非遞歸中序遍歷樹(shù)0…結(jié)束實(shí)驗(yàn)要求：在程序中定義下述函數(shù)，并實(shí)現(xiàn)要求的函數(shù)功能：createbinTree(binTreestructnode*lchild,*rchild;}binTnode;元素類(lèi)型：intcreatebinTree(binTreevoidpreorder(binTreevoidlnorder(binTreevoidpostorder(binTreevoidlnordern(binTreeintleaf(binTreeintpostTreeDepth(binTree2、編寫(xiě)算法實(shí)現(xiàn)二叉樹(shù)的非遞歸中序遍歷和求二叉樹(shù)高度。1)問(wèn)題描述：實(shí)現(xiàn)二叉樹(shù)的非遞歸中序遍歷和求二叉樹(shù)高度2)實(shí)驗(yàn)要求：以二叉鏈表作為存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)過(guò)程：1、實(shí)現(xiàn)非遞歸中序遍歷代碼：voidcbiTree::lnordern(binTreeinttop=0;p=T;do{while(p!=nuLL){stack[top]=p;;top=top+1;p=p->lchild;};if(top>0){top=top-1;p=stack[top];printf("%3c",p->data);p=p->rchild;}}while(p!=nuLL||top!=0);}2、求二叉樹(shù)高度：intcbiTree::postTreeDepth(binTreeif(T!=nuLL){l=postTreeDepth(T->lchild);r=postTreeDepth(T->rchild);max=l>r?l:r;return(max+1);}elsereturn(O);}實(shí)驗(yàn)步驟：1)新建一個(gè)基于consoleApplication的工程，工程名稱(chēng)biTreeTest；2)新建一個(gè)類(lèi)cbiTree二叉樹(shù)類(lèi)。3)在類(lèi)cbiTree的頭文件上方定義二叉鏈表存儲(chǔ)數(shù)據(jù)類(lèi)型結(jié)構(gòu)體biTnode。4)在類(lèi)cbiTree中定義函數(shù)createbinTree()；preorder()；Inorder()；postorder();postTreeDepth();lnordern()；實(shí)現(xiàn)函數(shù)createbinTree();preorder();lnorder()；postorder();postTreeDepth();Inordern()；在主函數(shù)中定義對(duì)象，通過(guò)對(duì)象調(diào)用函數(shù)，實(shí)現(xiàn)各個(gè)函數(shù)的操作。運(yùn)行結(jié)果:篇二：數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告-二叉樹(shù)的實(shí)現(xiàn)與遍歷《數(shù)據(jù)結(jié)構(gòu)》第六次實(shí)驗(yàn)報(bào)告學(xué)生姓名學(xué)生班級(jí)學(xué)生學(xué)號(hào)指導(dǎo)老師重慶郵電大學(xué)計(jì)算機(jī)學(xué)院一、實(shí)驗(yàn)內(nèi)容1）采用二叉樹(shù)鏈表作為存儲(chǔ)結(jié)構(gòu)，完成二叉樹(shù)的建立，先序、中序和后序以及按層次遍歷的操作，求所有葉子及結(jié)點(diǎn)總數(shù)的操作。2）輸出樹(shù)的深度，最大元，最小元。二、需求分析遍歷二叉樹(shù)首先有三種方法，即先序遍歷，中序遍歷和后序遍歷。遞歸方法比較簡(jiǎn)單，首先獲得結(jié)點(diǎn)指針如果指針不為空，且有左子，從左子遞歸到下一層，如果沒(méi)有左子，從右子遞歸到下一層，如果指針為空，則結(jié)束一層遞歸調(diào)用。直到遞歸全部結(jié)束。下面重點(diǎn)來(lái)講述非遞歸方法：首先介紹先序遍歷：先序遍歷的順序是根左右，也就是說(shuō)先訪問(wèn)根結(jié)點(diǎn)然后訪問(wèn)其左子再然后訪問(wèn)其右子。具體算法實(shí)現(xiàn)如下：如果結(jié)點(diǎn)的指針不為空，結(jié)點(diǎn)指針入棧，輸出相應(yīng)結(jié)點(diǎn)的數(shù)據(jù)，同時(shí)指針指向其左子，如果結(jié)點(diǎn)的指針為空，表示左子樹(shù)訪問(wèn)結(jié)束，棧頂結(jié)點(diǎn)指針出棧，指針指向其右子，對(duì)其右子樹(shù)進(jìn)行訪問(wèn)，如此循環(huán)，直至結(jié)點(diǎn)指針和棧均為空時(shí)，遍歷結(jié)束。再次介紹中序遍歷：中序遍歷的順序是左根右，中序遍歷和先序遍歷思想差不多，只是打印順序稍有變化。具體實(shí)現(xiàn)算法如下：如果結(jié)點(diǎn)指針不為空，結(jié)點(diǎn)入棧，指針指向其左子，如果指針為空，表示左子樹(shù)訪問(wèn)完成，則棧頂結(jié)點(diǎn)指針出棧，并輸出相應(yīng)結(jié)點(diǎn)的數(shù)據(jù)，同時(shí)指針指向其右子，對(duì)其右子樹(shù)進(jìn)行訪問(wèn)。如此循環(huán)直至結(jié)點(diǎn)指針和棧均為空，遍歷結(jié)束。最后介紹后序遍歷：后序遍歷的順序是左右根，后序遍歷是比較難的一種，首先需要建立兩個(gè)棧，一個(gè)用來(lái)存放結(jié)點(diǎn)的指針，另一個(gè)存放標(biāo)志位，也是首先訪問(wèn)根結(jié)點(diǎn)，如果結(jié)點(diǎn)的指針不為空，根結(jié)點(diǎn)入棧，與之對(duì)應(yīng)的標(biāo)志位也隨之入標(biāo)志位棧，并賦值0，表示該結(jié)點(diǎn)的右子還沒(méi)有訪問(wèn)，指針指向該結(jié)點(diǎn)的左子，如果結(jié)點(diǎn)指針為空，表示左子訪問(wèn)完成，父結(jié)點(diǎn)出棧，與之對(duì)應(yīng)的標(biāo)志位也隨之出棧，如果相應(yīng)的標(biāo)志位值為0，表示右子樹(shù)還沒(méi)有訪問(wèn)，指針指向其右子，父結(jié)點(diǎn)再次入棧，與之對(duì)應(yīng)的標(biāo)志位也入棧，但要給標(biāo)志位賦值為1，表示右子訪問(wèn)過(guò)。如果相應(yīng)的標(biāo)志位值為1,表示右子樹(shù)已經(jīng)訪問(wèn)完成，此時(shí)要輸出相應(yīng)結(jié)點(diǎn)的數(shù)據(jù)，同時(shí)將結(jié)點(diǎn)指針賦值為空，如此循環(huán)直至結(jié)點(diǎn)指針和棧均為空，遍歷結(jié)束。三、詳細(xì)設(shè)計(jì)源代碼：#include#definemAx100〃表示棧的最大容量#defineFuLL99〃表示棧滿(mǎn)#defineempTY-1〃表示棧空typedefstructTnode//定義結(jié)點(diǎn){定義chardata;//存儲(chǔ)結(jié)點(diǎn)數(shù)據(jù)structTnode*left;〃結(jié)點(diǎn)左子指針structTnode*right;〃定義右子指針定義}Tnode,*pnode;〃聲明Tnode類(lèi)型的變量和指針typedefstructstack//定義棧{pnodepnode[mAx];〃存放數(shù)據(jù)intp;//棧頂指針}stack,*pstack;〃定義stack類(lèi)型的變量和指針voidpush(pstackpstack,pnodepnode)〃入棧{}pnodepop(pstackpstack)//出棧{}pnodeTop(pstackpstack)//看棧頂元素{}intlsempty(pstackpstack)//棧判空{(diào)}intlsfull(pstackpstack)//棧滿(mǎn){}voidlnitstack(pstackpstack)//初始化棧if(pstack->p==FuLL)elsereturnO;return1;if(pstack->p==empTY)elsereturnO;;return1;returnpstack->pnode[pstack->p];returnpstack->pnode[pstack->p--];pstack->p++;pstack->pnode[pstack->p]=pnode