實驗2二叉樹的基本操作及哈夫曼編碼

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

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

3、值：6，e請繼續(xù)輸入二叉樹各結(jié)點的編號和對應的值：7，f請繼續(xù)輸入二叉樹各結(jié)點的編號和對應的值：9，g請繼續(xù)輸入二叉樹各結(jié)點的編號和對應的值：13，h請繼續(xù)輸入二叉樹各結(jié)點的編號和對應的值：0，#=主菜單=); 1.建立二叉樹方法1 2.建立二叉樹方法2 3.先序遞歸遍歷二叉樹 4.中序遞歸遍歷二叉樹 5.后序遞歸遍歷二叉樹 6.層次遍歷二叉樹 7.計算二叉樹的高度 8.計算二叉樹中葉結(jié)點個數(shù) 9.交換二叉樹的左右子樹 10.打印二叉樹 0.結(jié)束程序運行= 請輸入您的選擇(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.計算二叉樹的高度 8.計算二叉樹中葉結(jié)點個數(shù) 9.交換二叉樹的左右子樹 10.打印二叉樹 0.結(jié)束程序運行 = 請輸入您的選擇(0,1,2,3,4,5,6,7,8,9,10) 7 二叉樹的高度為：4程序清單 #include #include #define M 100 typedef char Etype; /定義二叉樹結(jié)點值的類型為字符型 typedef struct BiTNode /樹結(jié)點結(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.計

7、算二叉樹的高度); printf(nn 8.計算二叉樹中葉結(jié)點個數(shù)); printf(nn 9.交換二叉樹的左右子樹); printf(nn 10.打印二叉樹); printf(nn 0.結(jié)束程序運行); printf(n=); printf(n 請輸入您的選擇(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請輸入二叉樹各結(jié)點值:);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é)點數(shù)為：%dn,leafcount(t); printf(二叉樹的葉結(jié)點為：);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(逆時針旋轉(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; /序號為1的結(jié)點是根 else j=i/2; if(i%2=0)vj-lch=p; /序號為偶數(shù)，作為左孩子 else vj-rch

11、=p; /序號為奇數(shù)，作為右孩子 printf(n請繼續(xù)輸入二叉樹各結(jié)點的編號和對應的值：); scanf(%d,%c,&i,&e);return(t);/creat_bt1;/模仿先序遞歸遍歷方法，建立二叉樹BiTNode *creat_bt2() BiTNode *t; Etype e; scanf(%c,&e); if(e=#)t=NULL; /對于#值，不分配新結(jié)點 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; /對于#值，不分配新結(jié)點 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) /計算二叉樹的高度 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) /計算葉結(jié)點數(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é)點 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