實(shí)驗(yàn)2二叉樹的基本操作及哈夫曼編碼

1、二 叉 樹 的基本操作及哈夫曼編碼實(shí)現(xiàn)實(shí)驗(yàn)?zāi)康? 掌握二叉樹的結(jié)構(gòu)特征，以及各種存儲(chǔ)結(jié)構(gòu)的特點(diǎn)及適用范圍。2 掌握用指針類型描述、訪問和處理二叉樹的運(yùn)算。3 掌握哈夫曼編碼實(shí)驗(yàn)要求認(rèn)真閱讀和掌握本實(shí)驗(yàn)的程序上機(jī)運(yùn)行程序。保存和打印出程序的運(yùn)行結(jié)果，并結(jié)合程序進(jìn)行分析。按照二叉樹的操作需要，重新改寫主程序并運(yùn)行，打印出文件清單和運(yùn)行結(jié)果。實(shí)驗(yàn)內(nèi)容1 輸入字符序列，建立二叉鏈表。2 按先序、中序和后序遍歷二叉樹（遞歸算法）。3 按某種形式輸出整棵二叉樹。4 求二叉樹的高度。5 求二叉樹的葉節(jié)點(diǎn)個(gè)數(shù)。6 交換二叉樹的左右子樹。7 借助隊(duì)列實(shí)現(xiàn)二叉樹的層次遍歷。8 哈夫曼編碼的實(shí)現(xiàn)9 在主函數(shù)中設(shè)計(jì)一

2、個(gè)簡(jiǎn)單的菜單，分別調(diào)試上述算法。 運(yùn)行結(jié)果：=主菜單= 1.建立二叉樹方法1 2.建立二叉樹方法2 3.先序遞歸遍歷二叉樹 4.中序遞歸遍歷二叉樹 5.后序遞歸遍歷二叉樹 6.層次遍歷二叉樹 7.計(jì)算二叉樹的高度 8.計(jì)算二叉樹中葉結(jié)點(diǎn)個(gè)數(shù) 9.交換二叉樹的左右子樹 10.打印二叉樹 0.結(jié)束程序運(yùn)行= 請(qǐng)輸入您的選擇(0,1,2,3,4,5,6,7,8,9,10) 1請(qǐng)輸入二叉樹各結(jié)點(diǎn)的編號(hào)和對(duì)應(yīng)的值（如1，a）：1，a請(qǐng)繼續(xù)輸入二叉樹各結(jié)點(diǎn)的編號(hào)和對(duì)應(yīng)的值：2，b請(qǐng)繼續(xù)輸入二叉樹各結(jié)點(diǎn)的編號(hào)和對(duì)應(yīng)的值：3，c請(qǐng)繼續(xù)輸入二叉樹各結(jié)點(diǎn)的編號(hào)和對(duì)應(yīng)的值：4，d請(qǐng)繼續(xù)輸入二叉樹各結(jié)點(diǎn)的編號(hào)和對(duì)應(yīng)的

3、值：6，e請(qǐng)繼續(xù)輸入二叉樹各結(jié)點(diǎn)的編號(hào)和對(duì)應(yīng)的值：7，f請(qǐng)繼續(xù)輸入二叉樹各結(jié)點(diǎn)的編號(hào)和對(duì)應(yīng)的值：9，g請(qǐng)繼續(xù)輸入二叉樹各結(jié)點(diǎn)的編號(hào)和對(duì)應(yīng)的值：13，h請(qǐng)繼續(xù)輸入二叉樹各結(jié)點(diǎn)的編號(hào)和對(duì)應(yīng)的值：0，#=主菜單=); 1.建立二叉樹方法1 2.建立二叉樹方法2 3.先序遞歸遍歷二叉樹 4.中序遞歸遍歷二叉樹 5.后序遞歸遍歷二叉樹 6.層次遍歷二叉樹 7.計(jì)算二叉樹的高度 8.計(jì)算二叉樹中葉結(jié)點(diǎn)個(gè)數(shù) 9.交換二叉樹的左右子樹 10.打印二叉樹 0.結(jié)束程序運(yùn)行= 請(qǐng)輸入您的選擇(0,1,2,3,4,5,6,7,8,9,10) 4中序遍歷二叉樹：d g b a e h c f =主菜單=); 1.建立

4、二叉樹方法1 2.建立二叉樹方法2 3.先序遞歸遍歷二叉樹 4.中序遞歸遍歷二叉樹 5.后序遞歸遍歷二叉樹 6.層次遍歷二叉樹 7.計(jì)算二叉樹的高度 8.計(jì)算二叉樹中葉結(jié)點(diǎn)個(gè)數(shù) 9.交換二叉樹的左右子樹 10.打印二叉樹 0.結(jié)束程序運(yùn)行 = 請(qǐng)輸入您的選擇(0,1,2,3,4,5,6,7,8,9,10) 7 二叉樹的高度為：4程序清單 #include #include #define M 100 typedef char Etype; /定義二叉樹結(jié)點(diǎn)值的類型為字符型 typedef struct BiTNode /樹結(jié)點(diǎn)結(jié)構(gòu) Etype data; struct BiTNode *lch

5、,*rch; BiTNode,*BiTree; BiTree queM; int front=0,rear=0;/函數(shù)原型聲明BiTNode *creat_bt1();BiTNode *creat_bt2();void preorder(BiTNode *p);void inorder(BiTNode *p);void postorder(BiTNode *p);void enqueue(BiTree);BiTree delqueue( );void levorder(BiTree);int treedepth(BiTree);void prtbtree(BiTree,int);void ex

6、change(BiTree);int leafcount(BiTree);void paintleaf(BiTree);BiTNode *t;int count=0;/主函數(shù)void main() char ch; int k; do printf(nnn); printf(n=主菜單=); printf(nn 1.建立二叉樹方法1); printf(nn 2.建立二叉樹方法2); printf(nn 3.先序遞歸遍歷二叉樹); printf(nn 4.中序遞歸遍歷二叉樹); printf(nn 5.后序遞歸遍歷二叉樹); printf(nn 6.層次遍歷二叉樹); printf(nn 7.計(jì)

7、算二叉樹的高度); printf(nn 8.計(jì)算二叉樹中葉結(jié)點(diǎn)個(gè)數(shù)); printf(nn 9.交換二叉樹的左右子樹); printf(nn 10.打印二叉樹); printf(nn 0.結(jié)束程序運(yùn)行); printf(n=); printf(n 請(qǐng)輸入您的選擇(0,1,2,3,4,5,6,7,8,9,10); scanf(%d,&k);switch(k) case 1:t=creat_bt1( );break; /調(diào)用性質(zhì)5建立二叉樹算法 case 2:printf(n請(qǐng)輸入二叉樹各結(jié)點(diǎn)值:);fflush(stdin); t=creat_bt2();break; /調(diào)用遞歸建立二叉

8、樹算法 case 3:if(t) printf(先序遍歷二叉樹:); preorder(t); printf(n); else printf(二叉樹為空!n); break; case 4:if(t) printf(中序遍歷二叉樹:); inorder(t); printf(n); else printf(二叉樹為空!n); break; case 5:if(t) printf(后序遍歷二叉樹:); postorder(t); printf(n); else printf(二叉樹為空!n); break; case 6:if(t) printf(層次遍歷二叉樹：); levorder(t);

9、printf(n); else printf(二叉樹為空！n); break; case 7:if(t) printf(二叉樹的高度為：%d,treedepth(t); printf(n); else printf(二叉樹為空！n); break; case 8:if(t) printf(二叉樹的葉子結(jié)點(diǎn)數(shù)為：%dn,leafcount(t); printf(二叉樹的葉結(jié)點(diǎn)為：);paintleaf(t); printf(n); else printf(二叉樹為空！n); break; case 9:if(t) printf(交換二叉樹的左右子樹：n); exchange(t); prtbtr

10、ee(t,0); printf(n); else printf(二叉樹為空！n); break; case 10:if(t) printf(逆時(shí)針旋轉(zhuǎn)90度輸出的二叉樹：n); prtbtree(t,0); printf(n); else printf(二叉樹為空！n); break; case 0:exit(0); /switch while(k=1&kdata=e; p-lch=NULL; p-rch=NULL; vi=p; if(i=1) t=p; /序號(hào)為1的結(jié)點(diǎn)是根 else j=i/2; if(i%2=0)vj-lch=p; /序號(hào)為偶數(shù)，作為左孩子 else vj-rch

11、=p; /序號(hào)為奇數(shù)，作為右孩子 printf(n請(qǐng)繼續(xù)輸入二叉樹各結(jié)點(diǎn)的編號(hào)和對(duì)應(yīng)的值：); scanf(%d,%c,&i,&e);return(t);/creat_bt1;/模仿先序遞歸遍歷方法，建立二叉樹BiTNode *creat_bt2() BiTNode *t; Etype e; scanf(%c,&e); if(e=#)t=NULL; /對(duì)于#值，不分配新結(jié)點(diǎn) else t=(BiTNode *)malloc(sizeof(BiTNode); t-data=e; t-lch=creat_bt2(); /左孩子獲得新指針值 t-rch=creat_bt2()

12、; /右孩子獲得新指針值 return(t); /creat_bt2/模仿先序遞歸遍歷方法，建立二叉樹BiTNode *creat_bt2() BiTNode *t; Etype e; scanf(%c,&e); if(e=#)t=NULL; /對(duì)于#值，不分配新結(jié)點(diǎn) else t=(BiTNode *)malloc(sizeof(BiTNode); t-data=e; t-lch=creat_bt2(); /左孩子獲得新指針值 t-rch=creat_bt2(); /右孩子獲得新指針值 return(t); /creat_bt2 /先序遞歸遍歷二叉樹 void preorder(Bi

13、TNode *p) if(p) printf(%3c,p-data); preorder(p-lch); preorder(p-rch); /preorder /中序遞歸遍歷二叉樹 void inorder(BiTNode *p) if(p) inorder(p-lch); printf(%3c,p-data); inorder(p-rch); /inorder /后序遞歸遍歷二叉樹 void postorder(BiTNode *p) if(p) postorder(p-lch); postorder(p-rch); printf(%3c,p-data); /postorder /層次遍歷二

14、叉樹 void enqueue(BiTree T) if(front!=(rear+1)%M) rear=(rear+1)%M; querear=T; BiTree delqueue( ) if(front=rear)return NULL; front=(front+1)%M; return(quefront); 層次遍歷二叉樹(cont.) void levorder(BiTree T) /層次遍歷二叉樹 BiTree p; if(T)enqueue(T); while(front!=rear) p=delqueue( ); printf(%3d,p-data); if(p-lch!=NU

15、LL)enqueue(p-lch); if(p-rch!=NULL)enqueue(p-rch); int treedepth(BiTree bt) /計(jì)算二叉樹的高度 int hl,hr,max; if(bt!=NULL) hl=treedepth(bt-lch); hr=treedepth(bt-rch); max=(hlhr)?hl:hr; return (max+1); else return (0); void exchange(BiTree bt) /交換二叉樹左右子樹 BiTree p; if(bt) p=bt-lch; bt-lch=bt-rch; bt-rch=p; exch

16、ange(bt-lch); exchange(bt-rch); int leafcount(BiTree bt) /計(jì)算葉結(jié)點(diǎn)數(shù) if(bt!=NULL) leafcount(bt-lch); leafcount(bt-rch); if(bt-lch=NULL)&(bt-rch=NULL) count+; return(count); void paintleaf(BiTree bt) /輸出葉結(jié)點(diǎn) if(bt!=NULL) if(bt-lch=NULL&bt-rch=NULL) printf(%3c,bt-data); paintleaf(bt-lch); paintleaf(bt-rch); 刪除二叉樹 void Delete_Tree(BTnode * p) if (!(p-lChild) & !(p-rChild) free(p); else if (p-lChild) Delete_Tree(p-lChil