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

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

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

5、,*rch; BiTNode,*BiTree; BiTree queM; int front=0,rear=0;/函數原型聲明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;/主函數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.計算二叉樹中葉結點個數); printf(nn 9.交換二叉樹的左右子樹); printf(nn 10.打印二叉樹); printf(nn 0.結束程序運行); 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; /調用性質5建立二叉樹算法 case 2:printf(n請輸入二叉樹各結點值:);fflush(stdin); t=creat_bt2();break; /調用遞歸建立二叉

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(二叉樹的葉子結點數為：%dn,leafcount(t); printf(二叉樹的葉結點為：);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(逆時針旋轉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的結點是根 else j=i/2; if(i%2=0)vj-lch=p; /序號為偶數，作為左孩子 else vj-rch

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