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

實(shí)驗(yàn)四 二叉樹的建立和遍歷 學(xué)院 專業(yè) 班 學(xué)號(hào) 姓名 一 實(shí)習(xí)目的1. 掌握二叉鏈表的存儲(chǔ)結(jié)構(gòu)；2. 掌握二叉鏈表的建立；3. 掌握二叉樹的先序遍歷、中序遍歷、后序遍歷的遞歸算法；4. 掌握二叉樹遍歷算法的應(yīng)用；二 實(shí)習(xí)內(nèi)容1. 按先序序列建立二叉樹的二叉鏈表（算法6.4）（空樹用#表示）2. 對(duì)生成的二叉樹分別進(jìn)行先序遍歷、中序遍歷、后序遍歷，輸出結(jié)果。3 統(tǒng)計(jì)二叉樹中結(jié)點(diǎn)個(gè)數(shù)； 4. 求二叉樹的高度；三 實(shí)驗(yàn)步驟1. 定義 二叉鏈表的存儲(chǔ)結(jié)構(gòu)#include stdio.h#include stdlib.h typedef char TElemType;typedef struct BiTNode TElemType data; struct BiTNode *lchild, *rchild; / 左右孩子指針 BiTNode,*BiTree;2. 編寫函數(shù)CreateBiTree，按先序序列建立二叉樹的二叉鏈表;測(cè)試的字符序列為abdg#e#c#f#; 程序代碼為：void CreateBiTree(BiTree &T) / 算法6.4：按先序次序輸入二叉樹中結(jié)點(diǎn)的值(可為字符型或整型，在主程中定義)， 構(gòu)造二叉鏈表表示的二叉樹T。以#表示空樹 TElemType ch; scanf(%c,&ch); if(ch=#) / 空 T=NULL; else T=(BiTree )malloc(sizeof(BiTNode); / 生成根結(jié)點(diǎn) if(!T) exit(-1); T-data=ch; CreateBiTree(T-lchild);/ 遞歸構(gòu)造左子樹 CreateBiTree(T-rchild);/ 構(gòu)造右子樹 2. 編寫二叉樹的先序遍歷、中序遍歷、后序遍歷的遞歸算法 int preOrderTraverse(BiTree T) / 初始條件：二叉樹T存在，先序遞歸遍歷T； if(T=NULL) return 1; if(T!=NULL) / T不空 printf(%5c,T-data); / 訪問(wèn)根結(jié)點(diǎn) preOrderTraverse(T-lchild);/ 先序遍歷左子樹 preOrderTraverse(T-rchild);/ 先序遍歷右子樹 int inOrderTraverse(BiTree T) / 初始條件：二叉樹T存在，中序遞歸遍歷T； if(T=NULL) return 1; if(T!=NULL) / T不空 inOrderTraverse(T-lchild);/ 中序遍歷左子樹 printf(%5c,T-data); / 訪問(wèn)根結(jié)點(diǎn) inOrderTraverse(T-rchild);/ 中序遍歷右子樹 int postOrderTraverse(BiTree T) / 初始條件：二叉樹T存在， / 操作結(jié)果：后序遞歸遍歷T； if(T=NULL) return 1; if(T!=NULL) / T不空 postOrderTraverse(T-lchild);/ 后序遍歷左子樹 postOrderTraverse(T-rchild);/ 后序遍歷右子樹 printf(%5c,T-data); / 訪問(wèn)根結(jié)點(diǎn) 3. 編寫函數(shù)統(tǒng)計(jì)二叉樹中結(jié)點(diǎn)個(gè)數(shù)； （遍歷算法）int countND(BiTree T) int n=0,k=0,m=0;if(T=NULL) return 0;else if(T-lchild!=NULL ) k=countND(T-lchild); / 后序遍歷左子樹,得到左子樹結(jié)點(diǎn)個(gè)數(shù)if(T-rchild!=NULL ) m=countND(T-rchild); / 再后序遍歷右子樹 n=m+k+1 ; return n;4. 編寫函數(shù)求二叉樹的高度；int Bitheight(BiTree T) int lh,rh,th;if(T=NULL)return 0; lh= Bitheight(T-lchild); / 遞歸求T的左子樹的高度lhrh= Bitheight(T-rchild); /遞歸求T的右子樹的高度rh if(lhrh) th=lh+1; else th=rh+1; return th;4. 編寫 main 函數(shù)，調(diào)用函數(shù)，輸出結(jié)構(gòu) void main() int i,k,h ; BiTree T; printf(請(qǐng)按先序輸入二叉樹(如:ab#表示a為根結(jié)點(diǎn),b為左子樹的二叉樹)n); CreateBiTree(T); printf(先序遍歷的結(jié)果為：n); i=preOrderTraverse(T); printf(n); printf(中序遍歷的結(jié)果為：n); i=inOrderTraverse(T);printf(n); printf(后序遍歷的結(jié)果為：n); i=postOrderTraverse(T);printf(n); k=countND(T); printf(結(jié)點(diǎn)個(gè)數(shù)為%dn,k); h= Bitheight(T