資源描述：
《二叉樹(shù)的建立和遍歷實(shí)驗(yàn)報(bào)告》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫(kù)。
1、實(shí)驗(yàn)四二叉樹(shù)的建立和遍歷學(xué)院專業(yè)班學(xué)號(hào)姓名一．實(shí)習(xí)目的1.掌握二叉鏈表的存儲(chǔ)結(jié)構(gòu)；2.掌握二叉鏈表的建立；3.掌握二叉樹(shù)的先序遍歷、中序遍歷、后序遍歷的遞歸算法；4.掌握二叉樹(shù)遍歷算法的應(yīng)用；二．實(shí)習(xí)內(nèi)容1.按先序序列建立二叉樹(shù)的二叉鏈表（算法6.4）（空樹(shù)用#表示）2.對(duì)生成的二叉樹(shù)分別進(jìn)行先序遍歷、中序遍歷、后序遍歷，輸出結(jié)果。3．統(tǒng)計(jì)二叉樹(shù)中結(jié)點(diǎn)個(gè)數(shù)；4.求二叉樹(shù)的高度；三．實(shí)驗(yàn)步驟1.定義二叉鏈表的存儲(chǔ)結(jié)構(gòu)#include"stdio.h"#include"stdlib.h"typedefcha
2、rTElemType;typedefstructBiTNode{TElemTypedata;structBiTNode*lchild,*rchild;//左右孩子指針}BiTNode,*BiTree;2.編寫(xiě)函數(shù)CreateBiTree，按先序序列建立二叉樹(shù)的二叉鏈表;測(cè)試的字符序列為abdg###e##c#f##;程序代碼為：voidCreateBiTree(BiTree&T){//算法6.4：按先序次序輸入二叉樹(shù)中結(jié)點(diǎn)的值(可為字符型或整型，在主程中定義)，構(gòu)造二叉鏈表表示的二叉樹(shù)T。以#表示空樹(shù)T
3、ElemTypech;scanf("%c",&ch);if(ch=='#')//空T=NULL;else{T=(BiTree)malloc(sizeof(BiTNode));//生成根結(jié)點(diǎn)if(!T)4exit(-1);T->data=ch;CreateBiTree(T->lchild);//遞歸構(gòu)造左子樹(shù)CreateBiTree(T->rchild);//構(gòu)造右子樹(shù)}}2.編寫(xiě)二叉樹(shù)的先序遍歷、中序遍歷、后序遍歷的遞歸算法intpreOrderTraverse(BiTreeT){//初始條件：二叉樹(shù)T
4、存在，先序遞歸遍歷T；if(T==NULL)return1;if(T!=NULL)//T不空{(diào)printf("%5c",T->data);//訪問(wèn)根結(jié)點(diǎn)preOrderTraverse(T->lchild);//先序遍歷左子樹(shù)preOrderTraverse(T->rchild);//先序遍歷右子樹(shù)}}intinOrderTraverse(BiTreeT){//初始條件：二叉樹(shù)T存在，中序遞歸遍歷T；if(T==NULL)return1;if(T!=NULL)//T不空{(diào)inOrderTraverse(
5、T->lchild);//中序遍歷左子樹(shù)printf("%5c",T->data);//訪問(wèn)根結(jié)點(diǎn)inOrderTraverse(T->rchild);//中序遍歷右子樹(shù)}}intpostOrderTraverse(BiTreeT){//初始條件：二叉樹(shù)T存在，//操作結(jié)果：后序遞歸遍歷T；if(T==NULL)return1;if(T!=NULL)//T不空{(diào)postOrderTraverse(T->lchild);//后序遍歷左子樹(shù)postOrderTraverse(T->rchild);//后序遍
6、歷右子樹(shù)printf("%5c",T->data);//訪問(wèn)根結(jié)點(diǎn)4}}3.編寫(xiě)函數(shù)統(tǒng)計(jì)二叉樹(shù)中結(jié)點(diǎn)個(gè)數(shù)；（遍歷算法）intcountND(BiTreeT){intn=0,k=0,m=0;if(T==NULL)return0;else{if(T->lchild!=NULL)k=countND(T->lchild);//后序遍歷左子樹(shù),得到左子樹(shù)結(jié)點(diǎn)個(gè)數(shù)if(T->rchild!=NULL)m=countND(T->rchild);//再后序遍歷右子樹(shù)n=m+k+1;}returnn;}4.編寫(xiě)函數(shù)求二叉
7、樹(shù)的高度；intBitheight(BiTreeT){intlh,rh,th;if(T==NULL)return0;lh=Bitheight(T->lchild);//遞歸求T的左子樹(shù)的高度lhrh=Bitheight(T->rchild);//遞歸求T的右子樹(shù)的高度rhif(lh>rh)th=lh+1;elseth=rh+1;returnth;}4.編寫(xiě)main函數(shù)，調(diào)用函數(shù)，輸出結(jié)構(gòu)voidmain(){inti,k,h;BiTreeT;printf("請(qǐng)按先序輸入二叉樹(shù)(如:ab###表示a為根結(jié)
8、點(diǎn),b為左子樹(shù)的二叉樹(shù))");CreateBiTree(T);printf("先序遍歷的結(jié)果為：");i=preOrderTraverse(T);printf("");printf("中序遍歷的結(jié)果為：");i=inOrderTraverse(T);printf("");printf("后序遍歷的結(jié)果為：");i=postOrderTraverse(T);printf("");k=countND(T);4prin
