數(shù)據(jù)結(jié)構(gòu) 二叉樹.docVIP

常熟理工學(xué)院數(shù)據(jù)結(jié)構(gòu)與算法實(shí)驗(yàn)指導(dǎo)與報(bào)告書_2017-2018_學(xué)年 第_1_ 學(xué)期專 業(yè)： 物聯(lián)網(wǎng)工程 實(shí)驗(yàn)名稱： 二叉樹 實(shí)驗(yàn)地點(diǎn)： N6-210 指導(dǎo)教師： 聶盼紅 計(jì)算機(jī)科學(xué)與工程學(xué)院2017實(shí)驗(yàn)六 二叉樹【實(shí)驗(yàn)?zāi)康摹?、掌握二叉樹的基本存儲表示。2、掌握二叉樹的遍歷操作實(shí)現(xiàn)方法（遞歸和非遞歸方法）。3、理解并實(shí)現(xiàn)二叉樹的其他基本操作。4、掌握二叉樹的重要應(yīng)用-哈夫曼編碼的實(shí)現(xiàn)?！緦?shí)驗(yàn)學(xué)時(shí)】4-6學(xué)時(shí)【實(shí)驗(yàn)預(yù)習(xí)】回答以下問題：1、二叉樹的二叉鏈表存儲表示。/*-二叉樹的二叉鏈表存儲表示-*/typedef struct BTNode char data ; /*結(jié)點(diǎn)數(shù)據(jù)*/ struct BTNode *lchild; /*左孩子指針*/ struct BTNode *rchild ; /*右孩子指針*/*BiTree;2、二叉樹的三種基本遍歷方式。/*先序遍歷二叉樹，補(bǔ)充遞歸算法*/void PreOrder(BiTree p) if(p!=NULL); printf(%c,p-data); /訪問根節(jié)點(diǎn) PreOrder(p-lchild); /先序遍歷左子數(shù) PreOrder(p-rchild); /先序遍歷右子數(shù) /*PreOrder*/*中序遍歷二叉樹，補(bǔ)充遞歸算法*/void InOrder(BiTree p) if(p!=NULL); InOrder(p-lchild); /中序遍歷左子數(shù) printf(%c,p-data); /訪問根節(jié)點(diǎn) InOrder(p-rchild); /中序遍歷右子數(shù) /*InOrder*/*后序遍歷二叉樹，補(bǔ)充遞歸算法*/void PostOrder(BiTree p) if(p!=NULL); PostOrder(p-lchild); /后序遍歷左子數(shù) PostOrder(p-rchild); /后序遍歷右子數(shù) printf(%c,p-data); /訪問根節(jié)點(diǎn) /*PostOrder*/3、解釋哈夫曼樹和帶權(quán)路徑長度WPL。哈夫曼樹，是指權(quán)值為W1、W2、.Wn的n個(gè)葉節(jié)點(diǎn)所構(gòu)成的二叉樹中帶權(quán)路徑長度最小的二叉樹。從樹根結(jié)點(diǎn)到到該結(jié)點(diǎn)之間的路徑長度與該結(jié)點(diǎn)上權(quán)的乘積稱為結(jié)點(diǎn)的帶權(quán)路徑長度，通常記作：WPL=（n，i=1）WiLi【實(shí)驗(yàn)內(nèi)容和要求】1、 編寫程序exp6_1.c，實(shí)現(xiàn)二叉樹的鏈?zhǔn)酱鎯盎静僮?。以下圖所示的二叉樹實(shí)現(xiàn)二叉樹的二叉鏈表存儲及基本操作，回答下列問題，補(bǔ)充完整程序，并調(diào)試運(yùn)行驗(yàn)證結(jié)果。（1）按照先序序列建立該二叉樹。讀入的字符序列應(yīng)為：A，B，C，*，*，D，E，*，G，*，*，F(xiàn)，*，*，* (*表示空指針)。（2）該二叉樹的三種遍歷序列：先序序列：A,B,C,D,E,G,F;中序序列：C,B,E,G,D,F,A;后序序列：C,G,E,F,D,B,A;（3）按層次遍歷該二叉樹，得到的序列為：A,B,C,D,E,F,G（4）該二叉樹的深度為 5 。（5）該二叉樹的葉子結(jié)點(diǎn)數(shù)為：_3_。A（6）交換該二叉樹所有結(jié)點(diǎn)的左右次序得到的新二叉樹為：（畫出新二叉樹的圖）BCDEFG（7）新二叉樹的三種遍歷序列分別為：先序序列：A,B,D,C,F,G,E;中序序列：D,B,F,G,C,E,A;后序序列：D,G,F,E,C,B,A;exp6_1.c參考程序如下：#include#include#define MAX 20/*-二叉樹的二叉鏈表存儲表示-*/typedef struct BTNode char data; /*結(jié)點(diǎn)數(shù)據(jù)*/ struct BTNode *lchild; /*左孩子指針*/ struct BTNode *rchild ; /*右孩子指針*/ * BiTree;/*-非遞歸遍歷輔助隊(duì)列-*/typedef struct SqQueue BiTree dataMAX; int front,rear; SqQueue;void createBiTree(BiTree *t); /*先序遍歷創(chuàng)建二叉樹*/void PreOrder(BiTree p); /*先序遍歷二叉樹*/void InOrder(BiTree p); /*中序遍歷二叉樹*/void PostOrder(BiTree p);/*后序遍歷二叉樹*/void RPreorder(BiTree p); /*先序遍歷的非遞歸算法*/void RInorder(BiTree p); /*中序遍歷的非遞歸算法*/void RPostorder(BiTree p); /*后序遍歷的非遞歸算法*/int depth(BiTree t); /*求二叉樹的深度算法*/BiTree gettreenode(char x,BiTree lptr,BiTree rptr);/*后序復(fù)制二叉樹-建立結(jié)點(diǎn)*/BiTree copytree(BiTree t);/*以后序遍歷的方式復(fù)制二叉樹*/BiTree swap(BiTree b); /*交換二叉樹的結(jié)點(diǎn)的左右孩子*/void ccOrder(BiTree t); /*利用循環(huán)隊(duì)列實(shí)現(xiàn)層次遍歷*/int Leaves(BiTree t); /*統(tǒng)計(jì)二叉樹葉子結(jié)點(diǎn)（遞歸）*/void release(BiTree t); /*釋放二叉樹*/*先序遍歷創(chuàng)建二叉樹*/void createBiTree(BiTree * t) char s; BiTree q; printf(nplease input data:); s=getchar(); getchar(); /*扔掉存在鍵盤緩沖區(qū)的輸入結(jié)束回車符*/ if(s=#) /*子樹為空則返回*/ * t =NULL; return; else q=(BiTree)malloc(sizeof(struct BTNode); if(q=NULL) printf(Memory alloc failure!); exit(0); q-data=s; *t=q; createBiTree(&q-lchild);/*遞歸建立左子樹*/ createBiTree(&q-rchild);/*遞歸建立右子樹*/ /*createBiTree*/*先序遍歷二叉樹，補(bǔ)充遞歸算法*/void PreOrder(BiTree p) if(p!=NULL) printf(%c,p-data); /訪問根節(jié)點(diǎn) PreOrder(p-lchild); /先序遍歷左子數(shù) PreOrder(p-rchild); /先序遍歷右子數(shù) /*PreOrder*/*中序遍歷二叉樹，補(bǔ)充遞歸算法*/void InOrder(BiTree p) if(p!=NULL) InOrder(p-lchild); /中序遍歷左子數(shù) printf(%c,p-data); /訪問根節(jié)點(diǎn) InOrder(p-rchild); /中序遍歷右子數(shù) /*InOrder*/*后序遍歷二叉樹，補(bǔ)充遞歸算法*/void PostOrder(BiTree p) if(p!=NULL) PostOrder(p-lchild); /后序遍歷左子數(shù) PostOrder(p-rchild); /后序遍歷右子數(shù) printf(%c,p-data); /訪問根節(jié)點(diǎn) /*PostOrder*/*先序遍歷的非遞歸算法*/void RPreorder(BiTree p) BiTree stackMAX,q; int top=0,i; for(i=0; idata); if(q-rchild!=NULL) stacktop+=q-rchild; /*右指針進(jìn)棧*/ if(q-lchild!=NULL) q=q-lchild;/*順著左指針繼續(xù)向下*/ else if(top0) q=stack-top; /*左子樹訪問完，出棧繼續(xù)訪問右子樹結(jié)點(diǎn)*/ else q=NULL; /*RPreorder*/*中序遍歷的非遞歸算法*/void RInorder(BiTree p) BiTree stackMAX,q; /定義節(jié)點(diǎn)棧和搜索指針 int top=0; q=p; do while(q)/左鏈所有節(jié)點(diǎn)入棧 stacktop+=q; q=q-lchild; if(top0) q=stack-top; printf(%c,q-data); /訪問根 q=q-rchild; while(q|top!=0);/*RInorder*/*后序遍歷的非遞歸算法*/void RPostorder(BiTree p) BiTree stackMAX,q; int i,top=0,flagMAX; for(i=0; ilchild; else while(top) if(flagtop-1=0) /*遍歷結(jié)點(diǎn)的右子樹*/ q=stacktop-1; q=q-rchild; flagtop-1=1; break; else q=stack-top; printf(%c,q-data); /*遍歷結(jié)點(diǎn)*/ if(top=0) break; /*RPostorder*/*求二叉樹的深度算法，補(bǔ)充遞歸算法*/int depth(BiTree t) int lc,rc; if(t=NULL) return 0; /若為空樹，則返回零 else lc=depth(t-lchild); /遞歸求t的左子樹深度 rc=depth(t-rchild);/遞歸求t的右子樹深度 if(lcrc) return(lc+1); else return(rc+1); /*depth*/*建立結(jié)點(diǎn)*/BiTree gettreenode(char x,BiTree lptr,BiTree rptr) BiTree t; t=(BiTree)malloc(sizeof(struct BTNode); t- data = x; t-lchild = lptr; t-rchild = rptr; return(t);/*gettreenode*/*以后序遍歷的方式遞歸復(fù)制二叉樹*/BiTree copytree(BiTree t) BiTree newlptr,newrptr,newnode; if(t=NULL) return NULL; if(t-lchild!=NULL) newlptr = copytree(t-lchild); else newlptr = NULL; if(t-rchild!=NULL) newrptr = copytree(t-rchild); else newrptr = NULL; newnode = gettreenode(t-data, newlptr, newrptr); return(newnode);/*copytree*/*交換二叉樹的結(jié)點(diǎn)的左右孩子*/BiTree swap(BiTree b) BiTree t,t1,t2; if(b=NULL) t=NULL; else t=(BiTree)malloc(sizeof(struct BTNode); t-data=b-data; t1=swap(b-lchild);/*遞歸交換左子樹上的結(jié)點(diǎn)*/ t2=swap(b-rchild);/*遞歸交換右子樹上的結(jié)點(diǎn)*/ t-lchild=t2;/*交換根t的左右子樹*/ t-rchild=t1; return(t);/*swap*/*利用循環(huán)隊(duì)列實(shí)現(xiàn)層次遍歷*/void ccOrder(BiTree t) BiTree p; SqQueue qlist,*q; /利用循環(huán)隊(duì)列，實(shí)現(xiàn)層次遍歷 q=&qlist; q-rear=0; q-front=0; /初始化隊(duì)列 p=t; if(p!=NULL) printf(%c,p-data); /訪問根節(jié)點(diǎn) q-dataq-rear=p; /根節(jié)點(diǎn)入隊(duì) q-rear=(q-rear+1)%MAX; /修改隊(duì)尾指針 while(q-front!=q-rear) p=q-dataq-front; /出隊(duì)操作 q-front=(q-front+1)%MAX; if(p-lchild!=NULL) /訪問出隊(duì)節(jié)點(diǎn)的左孩子，并且入隊(duì) printf(%c,p-lchild-data); q-dataq-rear=p-lchild; q-rear=(q-rear+1)%MAX; if(p-rchild!=NULL) /訪問出隊(duì)節(jié)點(diǎn)的右孩子，并且入隊(duì) printf(%c,p-rchild-data); q-dataq-rear=p-rchild; q-rear=(q-rear+1)%MAX; /*ccOrder*/*統(tǒng)計(jì)二叉樹葉子結(jié)點(diǎn)，補(bǔ)充遞歸算法*/int Leaves(BiTree t) if(t=NULL) return 0; if(t-lchild=NULL&t-rchild=NULL) return 1; return (Leaves(t-lchild)+Leaves(t-rchild); /左子數(shù)葉子節(jié)點(diǎn)加上右子數(shù)葉子結(jié)點(diǎn)數(shù)/*Leaves*/*釋放二叉樹*/void release(BiTree t) if(t!=NULL) release(t-lchild); release(t-rchild); free(t); /*release*/int main() BiTree t=NULL,copyt=NULL; int select; do printf(n*MENU*n); printf( 1. 按先序序列建立二叉樹n); printf( 2. 遍歷二叉樹（三種遞歸方法）n); printf( 3. 遍歷二叉樹（三種非遞歸方法）n); printf( 4. 層次遍歷二叉樹n); printf( 5. 輸出二叉樹的深度n); printf( 6. 統(tǒng)計(jì)二叉樹的葉子結(jié)點(diǎn)數(shù)（遞歸）n); printf( 7. 后序遍歷方式復(fù)制一棵二叉樹n); printf( 8. 交換二叉樹所有結(jié)點(diǎn)的左右孩子n); printf( 0. EXIT); printf(n*MENU*n); printf(ninput choice:); scanf(%d,&select); getchar(); switch(select) case 1: printf(n1-按先序序列建立二叉樹:n); printf(請依次輸入結(jié)點(diǎn)序列：n); / BiTree gettreenode(x,&lptr,&rptr); createBiTree(&t); if(t!=NULL) printf(二叉樹創(chuàng)建成功！n); else printf(二叉樹未創(chuàng)建成功！n); break; case 2: printf(n2-遍歷二叉樹（三種遞歸方法）:n); printf(n先序遍歷序列:); PreOrder(t); printf(n中序遍歷序列:); InOrder(t); printf(n后序遍歷序列:); PostOrder(t); printf(n); break; case 3: printf(n3-遍歷二叉樹（三種非遞歸方法）:n); printf(n先序遍歷的非遞歸:); RPreorder(t); printf(n中序遍歷的非遞歸:); RInorder(t); printf(n后序遍歷的非遞歸:); RPostorder(t); printf(n); break; case 4: printf(n4-層次遍歷二叉樹:n); printf(n按層次遍歷:); ccOrder(t); printf(n); break; case 5: printf(n5-輸出二叉樹的深度:n); printf(n二叉樹的深度:%d,depth(t); printf(n); break; case 6: printf(n6-統(tǒng)計(jì)二叉樹的葉子結(jié)點(diǎn)數(shù)（遞歸）:n); printf(n葉子結(jié)點(diǎn)數(shù)為：%d,Leaves(t); printf(n); break; case 7: printf(n7-后序遍歷方式復(fù)制一棵二叉樹:n); copyt=copytree(t); if(copyt!=NULL) printf(n先序遞歸遍歷復(fù)制的二叉樹:); PreOrder(copyt); else printf(n復(fù)制失敗！); printf(n); break; case 8: printf(n8-交換二叉樹所有結(jié)點(diǎn)的左右孩子:n); printf(n先序遞歸遍歷交換后的二叉樹:); PreOrder(swap(t); /*如需輸出中序和后序遍歷的結(jié)果，增加調(diào)用*/ printf(n); break; case 0: release(t); /*釋放二叉樹*/ break; default: break; while(select); return 0;exp6_1.c實(shí)驗(yàn)結(jié)果：(1) 按照先序序列建立二叉樹：（2）該二叉樹的三種遞歸遍歷序列為：（3）遍歷二叉樹（三種非遞歸方法）：（4）層次遍歷二叉樹：（5）輸出二叉樹的深度（6）統(tǒng)計(jì)二叉樹的葉子結(jié)點(diǎn)數(shù)（遞歸）（7）后序遍歷方式復(fù)制一棵二叉樹（8）交換二叉樹所有結(jié)點(diǎn)的左右孩子2、 編寫程序exp6_2.c，實(shí)現(xiàn)哈夫曼樹的建立和哈夫曼編碼。若有一組字符序列a,c,e,i,s,t,w，對應(yīng)的出現(xiàn)頻率為10,1,15,12,3,4,13。以此序列創(chuàng)建哈夫曼樹和哈夫曼編碼?；卮鹣铝袉栴}，補(bǔ)充完整程序，并調(diào)試運(yùn)行驗(yàn)證結(jié)果。（1） 構(gòu)造該序列的哈夫曼樹，畫出哈夫曼樹的形態(tài)。（以結(jié)點(diǎn)值左小右大的原則）eT658t28T425i12T533e15T318w13s 3c1 t4T14a 10（2） 寫出對應(yīng)的哈夫曼編碼。a的編碼為111， c的編碼為11000，e的編碼為10，i的編碼為00，s的編碼為11001，t的編碼為1101，w的編碼為01（3） 計(jì)算編碼的WPL。WPL=3*10+5*1+2*15+2*12+5*3+4*4+2*13=146exp6_2.c程序代碼參考如下：#include#define MAXVALUE 10000 /*定義最大權(quán)值*/#define MAXLEAF 30 /*定義哈夫曼樹中葉子結(jié)點(diǎn)個(gè)數(shù)*/#define MAXNODE MAXLEAF*2-1#define MAXBIT 10 /*定義哈夫曼編碼的最大長度*/typedef struct /*哈夫曼編碼結(jié)構(gòu)*/ int bitMAXBIT; int start;HCodeType;typedef struct /*哈夫曼樹結(jié)點(diǎn)結(jié)構(gòu)*/ char data; int weight; int parent; int lchild; int rchild;HNodeType;void HuffmanTree(HNodeType HuffNode,int *hn);void HuffmanCode(HNodeType HuffNode,HCodeType HuffCode,int n);void HuffmanTree(HNodeType HuffNode,int *hn)/*哈夫曼樹的構(gòu)造算法*/ int i,j,m1,m2,x1,x2,n; printf(n:); scanf(%d,&n); getchar(); /*輸入葉子結(jié)點(diǎn)個(gè)數(shù)*/ for (i=0; i2*n-1; i+) /*數(shù)組HuffNode 初始化*/ HuffNodei.parent=-1; HuffNodei.lchild=-1; HuffNodei.rchild=-1; printf(HuffNode:n); for (i=0; in; i+) scanf(%c,%d,&HuffNodei.data,&HuffNodei.weight); /*輸入n個(gè)葉子結(jié)點(diǎn)的權(quán)值*/ getchar(); for (i=0; in-1; i+) /*構(gòu)造哈夫曼樹*/ m1=m2=MAXVALUE; x1=x2=0; for (j=0; jn+i; j+) if (HuffNodej.weightm1 & HuffNodej.parent=-1) m2=m1; x2=x1; m1=HuffNodej.weight; x1=j; else if (HuffNodej.weightm2 & HuffNodej.parent=-1) m2=HuffNodej.weight; x2=j; /*將找出的兩棵子樹合并為一棵子樹*/ HuffNodex1.parent=n+i; HuffNodex2.parent=n+i; HuffNoden+i.weight=HuffNodex1.weight+HuffNodex2.weight; HuffNoden+i.lchild=x1;