實(shí)驗(yàn)四 樹和二叉樹的操作.doc

實(shí)驗(yàn)四 樹和二叉樹的操作一、實(shí)驗(yàn)題目：用菜單驅(qū)動(dòng)的手法，編寫一個(gè)完整的程序，生成一棵二叉樹，求二叉樹的高度，求二叉樹的葉子結(jié)點(diǎn)數(shù)，輸出二叉樹的所有結(jié)點(diǎn)。二、實(shí)驗(yàn)算法描述：二叉樹的生成是指如何在內(nèi)存中建立二叉樹的存儲(chǔ)結(jié)構(gòu)。建立順序存儲(chǔ)結(jié)構(gòu)的問題較簡(jiǎn)單，這里僅討論如何建立二叉鏈表。要建立二叉鏈表，就需要按照某種方式輸人二叉樹的結(jié)點(diǎn)及其邏輯信息。注意到對(duì)二叉樹遍歷時(shí)，不僅得到了結(jié)點(diǎn)信息，而且由序列中結(jié)點(diǎn)的先后關(guān)系還可獲得一定的邏輯信息，如果這些信息足夠，就可根據(jù)遍歷序列生成相應(yīng)的二叉樹二叉樹的生成方法就是基于遍歷序列的，相當(dāng)于遍歷問題的逆問題，即由遍歷序列反求二叉樹，這需要分析和利用二叉樹遍歷序列的特點(diǎn)。在下列兩種方法中任選一種。*以下的（一）（二）要編寫在一個(gè)完整的程序中。如果你不能編在一個(gè)程序中，則可以用兩個(gè)完整的程序來實(shí)現(xiàn)。（一）用先根序列建立二叉樹二叉樹的結(jié)點(diǎn)就按相應(yīng)的遍歷過程逐個(gè)生成。類似層次遍歷，如果不對(duì)遍歷序列作些補(bǔ)充，是不能完整反映結(jié)點(diǎn)間的邏輯關(guān)系的，也就不能得到正確的結(jié)果。補(bǔ)充的方法也是增加虛結(jié)點(diǎn)，但這里只需對(duì)空指針對(duì)應(yīng)的位置進(jìn)行補(bǔ)充，而不必補(bǔ)充到完全二叉樹的形式。以先根遍歷上圖為例，二叉樹的先根輸入序列為：ABDGCEFH其中表示虛結(jié)點(diǎn)，這里不需要結(jié)束符。算法過程為，先生成根結(jié)點(diǎn)，再生成左子樹，然后是右子樹，左右子樹的生成采用遞歸。在具體作本實(shí)驗(yàn)時(shí),還需編寫一個(gè)主函數(shù)調(diào)用這個(gè)函數(shù)來生成二叉樹,最后輸出二叉樹的結(jié)點(diǎn)序列。（二）按完全二叉樹的層次順序，依次輸入結(jié)點(diǎn)信息來建立二叉鏈表這是因?yàn)橥耆鏄涞膶哟伪闅v序列中，結(jié)點(diǎn)間的序號(hào)關(guān)系可反映父子關(guān)系即邏輯關(guān)系。對(duì)一般的二又樹，要補(bǔ)充若干個(gè)虛結(jié)點(diǎn)使其成為完全二叉樹后，冉按其層次順序輸入。例如，僅含3個(gè)結(jié)點(diǎn)A、B、C的右單支樹（見下圖 2），按完全二叉樹的形式輸入的結(jié)點(diǎn)序列為：ABC，其中表示虛結(jié)點(diǎn)，表示輸入結(jié)束。算法的基本思想是：依次輸入結(jié)點(diǎn)信息，若輸入的結(jié)點(diǎn)不是虛結(jié)點(diǎn)，則建立一個(gè)新結(jié)點(diǎn)：若新結(jié)點(diǎn)是第1個(gè)結(jié)點(diǎn)，則令其為根結(jié)點(diǎn)；否則將新結(jié)點(diǎn)作為孩子鏈接到它的雙親結(jié)點(diǎn)上。如此重復(fù)下去，直至輸入字符“”為止。 這里的關(guān)鍵是新結(jié)點(diǎn)與其雙親的鏈接。由于是按層次自左至右輸入結(jié)點(diǎn)的，所以先輸入的結(jié)點(diǎn)，其孩子也必定較先輸入。即結(jié)點(diǎn)與其孩子具有先進(jìn)先出的特點(diǎn)，于是可設(shè)置一個(gè)隊(duì)列，保存已輸人結(jié)點(diǎn)的地址。這樣，隊(duì)尾是當(dāng)前正輸入的結(jié)點(diǎn)，隊(duì)頭是其雙親結(jié)點(diǎn)。當(dāng)隊(duì)頭結(jié)點(diǎn)的兩個(gè)孩子都輸入完畢后，出隊(duì)，新的隊(duì)頭是下一個(gè)要輸入孩子的雙親結(jié)點(diǎn)。如此下去，直到輸入結(jié)束符為止。雙親與孩子的鏈接方法是：若當(dāng)前輸入的結(jié)點(diǎn)編號(hào)是偶數(shù)，則該結(jié)點(diǎn)作為左孩子與其雙親鏈接；否則作為右孩子與其雙親鏈。若雙親結(jié)點(diǎn)或孩子結(jié)點(diǎn)為虛結(jié)點(diǎn)，則無需鏈接。實(shí)驗(yàn)程序如下：#include#include#include#includeint cmp(const void *a,const void *b)return *(int *)a-*(int *)b;typedef char datatype;typedef struct treenodedatatype data; struct treenode *leftchild,*rightchild;treenode,*bitree;treenode *t;int count=0;/建立二叉樹方法1treenode *creattree_1() treenode *t,*p,*v100;int i,j;datatype e;t=NULL; printf(n請(qǐng)輸入初始二叉樹各結(jié)點(diǎn)的編號(hào)和對(duì)應(yīng)的值（如1,a）:); scanf(%d,%c,&i,&e); while(i!=0&e!=#) p=(treenode *)malloc(sizeof(treenode); p-data=e;p-leftchild=NULL;p-rightchild=NULL; vi=p; if(i=1) t=p; else j=i/2; if(i%2=0) vj-leftchild=p; else vj-rightchild=p; printf(n請(qǐng)繼續(xù)輸入（以0，#結(jié)束）:); scanf(%d,%c,&i,&e); return (t);/建立二叉樹方法2treenode *creattree_2() treenode *t;datatype e; scanf(%c,&e); if(e=#) t=NULL; else t=(treenode *)malloc(sizeof(treenode); t-data=e; t-leftchild=creattree_2(); t-rightchild=creattree_2(); return (t);/先序遍歷輸出二叉樹void preorder(treenode *p) if(p) printf(%-4c,p-data); preorder(p-leftchild); preorder(p-rightchild); /中序遍歷輸出二叉樹void inorder(treenode *p) if(p) inorder(p-leftchild); printf(%-4c,p-data); inorder(p-rightchild); /后序遍歷輸出二叉樹void postorder(treenode *p)if(p) postorder(p-leftchild); postorder(p-rightchild); printf(%-4c,p-data); /計(jì)算二叉樹高度int treedepth(bitree bt) int lefthight,righthight,max; if(bt!=NULL) lefthight=treedepth(bt-leftchild); righthight=treedepth(bt-rightchild); max=(lefthightrighthight)?lefthight:righthight; return(max+1); else return (0); /逆時(shí)針旋轉(zhuǎn)90度輸出二叉樹void printtree(bitree bt,int level) int j; if(bt) printtree(bt-rightchild,level+1); for(j=0;jdata); printtree(bt-leftchild,level+1); /交換二叉樹左右子樹void exchange(bitree bt) bitree p; if(bt) p=bt-leftchild;bt-leftchild=bt-rightchild;bt-rightchild=p; exchange(bt-leftchild); exchange(bt-rightchild); /計(jì)算葉結(jié)點(diǎn)數(shù)int leafcount(bitree bt) if(bt!=NULL) leafcount(bt-leftchild); leafcount(bt-rightchild); if(bt-leftchild=NULL)&(bt-rightchild=NULL) count+; return (count);/輸出葉結(jié)點(diǎn)void paintleaf(bitree bt) if(bt!=NULL)if(bt-leftchild=NULL&bt-rightchild=NULL) printf(%-4c,bt-data);paintleaf(bt-leftchild); paintleaf(bt-rightchild);/哈夫曼樹int haffman()int a100,b100;int i,j=0,k,n;memset(a,0,100);memset(b,0,100);printf(請(qǐng)輸入構(gòu)造哈夫曼樹的元素個(gè)數(shù)（正整數(shù)）：);scanf(%d,&n);printf(n);printf(請(qǐng)依次輸入各元素權(quán)值（以空格間隔，按ENTER鍵結(jié)束）：n); for(i=0;in;i+) scanf(%d,&ai);printf(n);getchar();printf(構(gòu)造哈夫曼樹過程：nn); for(i=0;in;i+) qsort(a,n,sizeof(a0),cmp); printf(步驟（%d）,i+1); for(k=i;kn;k+) printf(%d ,ak); printf(nn); bj+=ai; bj+=ai+1; ai+1=ai+ai+1; printf(當(dāng)前哈夫曼樹的所有結(jié)點(diǎn)權(quán)值為：n); for(i=0;ij-1;i+) printf(%-5d,bi); printf(nn);int main()int command;char order; doprintf(=簡(jiǎn)單二叉樹操作菜單=n) ; printf(* 1.建立二叉樹（按照完全二叉樹） *n); printf(* 2.建立二叉樹（模仿先序遞歸遍歷） *n); printf(* 3.先序遞歸遍歷二叉樹 *n); printf(* 4.中序遞歸遍歷二叉樹 *n); printf(* 5.后序遞歸遍歷二叉樹 *n); printf(* 6.輸出二叉樹的高度 *n); printf(* 7.輸出二叉樹的葉結(jié)點(diǎn) *n); printf(* 8.交換二叉樹的左右子樹 *n); printf(* 9.打印二叉樹 *n); printf(* 10.哈夫曼樹（最優(yōu)二叉樹） *n); printf(* 0.退出 *n); printf(=nn); printf(請(qǐng)輸入指令（0,1,2,3,4,5,6,7,8,9,10）:);scanf(%d,&command);if(command10)getchar(); system(cls);printf(n指令輸入錯(cuò)誤！請(qǐng)重新輸入！n); switch(command) case 1: getchar(); system(cls); printf(若已構(gòu)建二叉樹，此操作將會(huì)清除當(dāng)前二叉樹，繼續(xù)/退出Y/N:); scanf(%c,&order) ; if(order=Y|order=y) t=creattree_1(); if(t) printf(n當(dāng)前二叉樹為（逆時(shí)針旋轉(zhuǎn)90度）：n); printtree(t,0); printf(n); else printf(n當(dāng)前二叉樹為空！請(qǐng)先建立二叉樹！n); getchar(); break; elsebreak; case 2: getchar(); system(cls); printf(若已構(gòu)建二叉樹，此操作將會(huì)清除當(dāng)前二叉樹，繼續(xù)/退出Y/N:); scanf(%c,&order) ; if(order=Y|order=y) printf(n請(qǐng)輸入二叉樹按先序遞歸遍歷各結(jié)點(diǎn)的值（虛結(jié)點(diǎn)以#代替）:n); fflush(stdin); t=creattree_2(); if(t) printf(n當(dāng)前二叉樹為（逆時(shí)針旋轉(zhuǎn)90度）：n); printtree(t,0); printf(n); else printf(n當(dāng)前二叉樹為空！請(qǐng)先建立二叉樹！n); getchar(); break; elsebreak; case 3: getchar(); system(cls);if(t) printf(n當(dāng)前二叉樹為（逆時(shí)針旋轉(zhuǎn)90度）：n);printtree(t,0); printf(n); printf(n先序遞歸遍歷序列為:n); preorder(t); printf(n); else printf(n二叉樹為空！請(qǐng)先建立二叉樹！n); break; case 4: getchar(); system(cls);if(t) printf(n當(dāng)前二叉樹為（逆時(shí)針旋轉(zhuǎn)90度）：n);printtree(t,0); printf(n); printf(n中序遞歸遍歷序列為:n); inorder(t); printf(n); else printf(n二叉樹為空！請(qǐng)先建立二叉樹！n); break; case 5: getchar(); system(cls);if(t) printf(n當(dāng)前二叉樹為（逆時(shí)針旋轉(zhuǎn)90度）：n);printtree(t,0); printf(n); printf(n后序遞歸遍歷序列為:n);postorder(t);printf(n);else printf(n二叉樹為空！請(qǐng)先建立二叉樹！n);break;case 6:getchar(); system(cls);if(t)printf(n當(dāng)前二叉樹為（逆時(shí)針旋轉(zhuǎn)90度）：n);printtree(t,0); printf(n); printf(當(dāng)前二叉樹的高度為:%dn,treedepth(t); elseprintf(n二叉樹為空！請(qǐng)先建立二叉樹！n);break;case 7:getchar(); system(cls);if(t)printf(n當(dāng)前二叉樹為（逆時(shí)針旋轉(zhuǎn)90度）：n);printtree(t,0); printf(n); printf(當(dāng)前二叉樹的葉子結(jié)點(diǎn)數(shù)為:%dnn,leafcount