二叉樹的建立和遍歷的實驗報告

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