1、二叉樹(shù)實(shí)驗(yàn)報(bào)告09信管石旭琳20091004418一、實(shí)驗(yàn)?zāi)康模?、理解二叉樹(shù)的遍歷算法及應(yīng)用2、理解哈夫曼樹(shù)及其應(yīng)用。3、掌握哈夫曼編碼思想。二、實(shí)驗(yàn)內(nèi)容：1、建立二叉樹(shù)二叉鏈表2、實(shí)現(xiàn)二叉樹(shù)遞歸遍歷算法（中序、前序、后序）3、求二叉樹(shù)高度4、求二叉樹(shù)結(jié)點(diǎn)個(gè)數(shù)5、求二叉樹(shù)葉子個(gè)數(shù)6、將序號(hào)為偶數(shù)的值賦給左子樹(shù)三、主要程序：#include#includetypedefintElemType;structBiTNodeElemTypedata;structBiTNode*lch,*rch;BiTNode,*BiTree;*creat_bt1();*creat_bt2();(structBiTN

2、ode*t)(structBiTNode*t);voidpostorder(structBiTNode*t);voidnumbt(structBiTNode*t);intn,n0,n1,n2;voidmain()intk;printf(nnn);printf(nn1.建立二叉樹(shù)方法1(借助一維數(shù)組建立);printf(nn2.建立二叉樹(shù)方法2(先序遞歸遍歷建立);printf(nn3.先序遞歸遍歷二叉樹(shù));printf(nn4.中序遞歸遍歷二叉樹(shù));printf(nn5.后序遞歸遍歷二叉樹(shù));printf(nn6.計(jì)算二叉樹(shù)結(jié)點(diǎn)個(gè)數(shù));printf(nn7.結(jié)束程序運(yùn)行);printf(n=)

3、;do(printf(n請(qǐng)輸入你要執(zhí)行的操作(1,2,3,4,5,6,7);scanf(%d,&k);printf(n);switch(k)(case1:printf(你選擇的是操作1,現(xiàn)用方法1進(jìn)行建立二叉樹(shù)n);BiTree=creat_bt1();/*調(diào)用性質(zhì)5建立二叉樹(shù)算法*/structBiTNodestructBiTNodevoidpreordervoidinorderbreak;case2:printf(你 選 擇 的 是 操 作2,現(xiàn) 用 方 法2進(jìn) 行 建 立 二 叉 樹(shù)n);BiTree=creat_bt2();/*調(diào)用遞歸建立二叉樹(shù)算法*/break;case3:

4、printf(你 選 擇 的 是 操 作3,現(xiàn) 進(jìn) 行 先 序 遞 歸 遍 歷 二 叉 樹(shù)n結(jié) 果為:);preorder(BiTree);break;case4:printf(你選擇的是操作4,現(xiàn)進(jìn)行中序遞歸遍歷二叉樹(shù)n結(jié)果為:)；inorder(BiTree);break;case5:printf(你選擇的是操作5,現(xiàn)進(jìn)行后序遞歸遍歷二叉樹(shù)n結(jié)果為:)；postorder(BiTree);break;case6:n=0,n0=0,n1=0,n2=0;/*全局變量置0*/printf(你選擇的是操作6,現(xiàn)進(jìn)行計(jì)算二叉樹(shù)結(jié)點(diǎn)個(gè)數(shù)n結(jié)果為:)；numbt(BiTree);printf(n二叉樹(shù)結(jié)

5、點(diǎn)總數(shù)是：%d,n);printf(n二叉樹(shù)葉子結(jié)點(diǎn)數(shù)是：%d,n0);printf(n度為1的結(jié)點(diǎn)數(shù)是：%d,n1);printf(n度為2的結(jié)點(diǎn)數(shù)是：%d,n2);break;)case7:printf(你選擇的是操作8,將結(jié)束本程序運(yùn)行，謝謝你的使用，再見(jiàn)！n);break;)while(k=1&kdata=e;p-lch=NULL;p-rch=NULL;vi=p;if(i=1)/*序號(hào)為1的結(jié)點(diǎn)是根*/t=p;elsej=(i+1)/2;if(i%2=0)/*序號(hào)為偶數(shù)，做左孩子*/vj-lch=p;elsevj-rch=p;)printf(ni,data=);scanf(%d

6、,%d,&i,&e);)returnt;)structBiTNode*creat_bt2()structBiTNode*t;inte;printf(ndata=);scanf(%d,&e);if(e=0)t=NULL;/*對(duì)于0值，不分配新結(jié)點(diǎn)*/elset=(structBiTNode*)malloc(sizeof(structBiTNode);t-data=e;t-lch=creat_bt2();/*左孩子獲得新指針值*/t-rch=creat_bt2();.return(t);voidpreorder(structBiTNode*t)if(t)printf(%d,

7、t-data);preorder(t-lch);preorder(t-rch);voidinorder(structBiTNode*t)if(t)inorder(t-lch);printf(%d,t-data);inorder(t-rch);voidpostorder(structBiTNode*t)if(t)postorder(t-lch);postorder(t-rch);printf(%d,t-data);voidnumbt(structBiTNode*t)(if(t)(numbt(t-lch);(n+;if(t-lch=NULL&t-rch=NULL)n0+;if(t-lch=

8、NULL&t-rch!=NULL)|(t-lch!=NULL&t-rch=NULL)n1+;if(t-lch!=NULL&t-rch!=NULL)n2+;numbt(t-rch);四、測(cè)試結(jié)果：你選擇的是操作?，F(xiàn)用方法2 2進(jìn)行建立二叉樹(shù)d-at-ad-at-a=1=1HataHata=2=2d-at-ad-at-a-4.-4.d d總七縣=0=0data=5data=5(Lata=0(Lata=0dta=0dta=0datadata-3-3datA8datA8dAta=6dAta=6dAta=0dAta=0data=0data=0請(qǐng)輸入你要執(zhí)行的操作 S/，*J你選拄的是操作孔現(xiàn)進(jìn)行先序遞歸遍歷二叉樹(shù)拮果為2453&2453&請(qǐng)輸入你要執(zhí)行的操作3,23,2廣,4.4.6/6/4 4你選擇的是操作現(xiàn)進(jìn)行中序遞歸遍歷二叉樹(shù)結(jié)為：42542513136 6常輸X X你要執(zhí)行的操作523523磊5,6.7)55,6.7)5你選擇的是操作5.5.現(xiàn)進(jìn)行后序遞歸遍歷二叉樹(shù)售果為:452631:452631請(qǐng)嗡入你要執(zhí)行的揍作門評(píng).3.35,6.7)83.35,6.7)8你選展的是操作*現(xiàn)進(jìn)行計(jì)算二叉樹(shù)結(jié)