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

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

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

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

5、/樹(shù)結(jié)點(diǎn)結(jié)構(gòu) Etype data; struct BiTNode *lch,*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 tre

6、edepth(BiTree); void prtbtree(BiTree,int); void exchange(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.建立二叉樹(shù)方法1); printf(nn 2.建立二叉樹(shù)方法2); printf(nn 3.先序遞歸遍歷二叉樹(shù)); printf(nn 4.中序遞歸遍歷二叉樹(shù)); pri

7、ntf(nn 5.后序遞歸遍歷二叉樹(shù)); printf(nn 6.層次遍歷二叉樹(shù)); printf(nn 7.計(jì)算二叉樹(shù)的高度); printf(nn 8.計(jì)算二叉樹(shù)中葉結(jié)點(diǎn)個(gè)數(shù)); printf(nn 9.交換二叉樹(shù)的左右子樹(shù)); printf(nn 10.打印二叉樹(shù)); 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,switch(k) case 1:t=creat_bt1( ); /調(diào)用性質(zhì)5建立二叉樹(shù)算法 break; case 2:printf(n請(qǐng)輸入二叉樹(shù)各結(jié)點(diǎn)

8、值:);fflush(stdin); t=creat_bt2(); /調(diào)用遞歸建立二叉樹(shù)算法 break; case 3:if (t) printf(先序遍歷二叉樹(shù):); preorder(t); printf(n); else printf(二叉樹(shù)為空!n); break;,case 4:if(t) printf(中序遍歷二叉樹(shù):); inorder(t); printf(n); else printf(二叉樹(shù)為空!n); break; case 5:if(t) printf(后序遍歷二叉樹(shù):); postorder(t); printf(n); else printf(二叉樹(shù)為空!n);

9、break;,case 6:if(t) printf(層次遍歷二叉樹(shù)：); levorder(t); printf(n); else printf(二叉樹(shù)為空！n); break; case 7:if(t) printf(二叉樹(shù)的高度為：%d,treedepth(t); printf(n); else printf(二叉樹(shù)為空！n); break;,case 8:if(t) printf(二叉樹(shù)的葉子結(jié)點(diǎn)數(shù)為：%dn,leafcount(t); printf(二叉樹(shù)的葉結(jié)點(diǎn)為：);paintleaf(t); printf(n); else printf(二叉樹(shù)為空！n); break; cas

10、e 9:if(t) printf(交換二叉樹(shù)的左右子樹(shù)：n); exchange(t); prtbtree(t,0); printf(n); else printf(二叉樹(shù)為空！n); break;,case 10:if(t) printf(逆時(shí)針旋轉(zhuǎn)90度輸出的二叉樹(shù)：n); prtbtree(t,0); printf(n); else printf(二叉樹(shù)為空！n); break; case 0:exit(0); /switch while(k=1 /main,/利用二叉樹(shù)性質(zhì)6，借助一維數(shù)組V建立二叉樹(shù) BiTNode *creat_bt1() BiTNode *t,*p,*v20;in

11、t i,j;Etype e; /*輸入結(jié)點(diǎn)的序號(hào)i、結(jié)點(diǎn)的數(shù)據(jù)e*/ printf(n請(qǐng)輸入二叉樹(shù)各結(jié)點(diǎn)的編號(hào)和對(duì)應(yīng)的值（如1，a）：); scanf(%d,%c,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=p; /序號(hào)為奇數(shù)，作為右孩子 printf(n請(qǐng)繼續(xù)輸入二叉樹(shù)各結(jié)點(diǎn)的編號(hào)和對(duì)應(yīng)的值：); scanf(%d,%c,/模仿先序遞歸遍歷方法，建立二叉樹(shù) BiTNode *creat_bt2() BiTNode *t; Etype e; scanf(%c, /creat_bt

12、2,/模仿先序遞歸遍歷方法，建立二叉樹(shù) BiTNode *creat_bt2() BiTNode *t; Etype e; scanf(%c, /creat_bt2,/先序遞歸遍歷二叉樹(shù) void preorder(BiTNode *p) if(p) printf(%3c,p-data); preorder(p-lch); preorder(p-rch); /preorder,/中序遞歸遍歷二叉樹(shù) void inorder(BiTNode *p) if(p) inorder(p-lch); printf(%3c,p-data); inorder(p-rch); /inorder,/后序遞歸遍歷

13、二叉樹(shù) void postorder(BiTNode *p) if(p) postorder(p-lch); postorder(p-rch); printf(%3c,p-data); /postorder,/層次遍歷二叉樹(shù) 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); ,層次遍歷二叉樹(shù)(cont.),void levorder(B

14、iTree T) /層次遍歷二叉樹(shù) BiTree p; if(T)enqueue(T); while(front!=rear) p=delqueue( ); printf(%3d,p-data); if(p-lch!=NULL)enqueue(p-lch); if(p-rch!=NULL)enqueue(p-rch); ,int treedepth(BiTree bt) /計(jì)算二叉樹(shù)的高度 int hl,hr,max; if(bt!=NULL) hl=treedepth(bt-lch); hr=treedepth(bt-rch); max=(hlhr)?hl:hr; return (max+1

15、); else return (0); ,void exchange(BiTree bt) /交換二叉樹(shù)左右子樹(shù) BiTree p; if(bt) p=bt-lch; bt-lch=bt-rch; bt-rch=p; exchange(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) ,void paintleaf(BiTree bt) /輸出葉結(jié)點(diǎn) if(bt!=NULL) if(bt-lch=NULL ,刪除二叉樹(shù),void Delete_