樹(shù)與二叉樹(shù)實(shí)驗(yàn)

1、福州大學(xué)數(shù)計(jì)學(xué)院數(shù)據(jù)結(jié)構(gòu)上機(jī)實(shí)驗(yàn)報(bào)告專(zhuān)業(yè)：信息數(shù)學(xué)學(xué)號(hào)031201206姓名詹小青班級(jí)02班實(shí)驗(yàn)名稱(chēng)樹(shù)與二叉樹(shù)實(shí)驗(yàn)實(shí)驗(yàn)內(nèi)容樹(shù)型結(jié)構(gòu)及其應(yīng)用實(shí)驗(yàn)?zāi)康暮鸵蟆颈尘爸R(shí)】二叉樹(shù)的存儲(chǔ)、建立、遍歷及其應(yīng)用?！灸康囊蟆?掌握二叉樹(shù)的存儲(chǔ)實(shí)現(xiàn)。 2掌握二叉樹(shù)的遍歷思想。 3掌握二叉樹(shù)的常見(jiàn)算法的程序?qū)崿F(xiàn)。【實(shí)驗(yàn)主要內(nèi)容】運(yùn)用樹(shù)的結(jié)構(gòu)來(lái)實(shí)現(xiàn)建樹(shù)、遍歷等算法，并能運(yùn)用，如哈夫曼問(wèn)題的設(shè)計(jì)。問(wèn)題描述和主要步驟1、以二叉鏈表方式建立二叉樹(shù)，并任選一種遍歷方式輸出結(jié)點(diǎn)的值【實(shí)驗(yàn)?zāi)康摹浚?）了解二叉樹(shù)的結(jié)構(gòu)特點(diǎn)及有關(guān)概念，掌握二叉樹(shù)建立的基本算法； （2）了解二叉樹(shù)遍歷的概念，掌握遍歷二叉的算法。【實(shí)驗(yàn)內(nèi)容】按層次

2、序依次輸入元素值，以鏈表方式建立該二叉樹(shù)，然后可依據(jù)先序、中序、后序中的任一種遍歷方法遍歷二叉樹(shù)的方式輸出結(jié)點(diǎn)的值。2、哈夫曼編碼【實(shí)驗(yàn)?zāi)康摹苛私夂辗蚵鼧?shù)的結(jié)構(gòu)特點(diǎn)及有關(guān)概念，掌握赫夫曼樹(shù)的建立和赫夫曼編碼的設(shè)計(jì)【問(wèn)題描述】使用二叉樹(shù)進(jìn)行赫夫曼編碼的設(shè)計(jì)，要求對(duì)輸入的一串電文字符實(shí)現(xiàn)赫夫曼編碼，再對(duì)赫夫編碼生成的代碼串進(jìn)行譯碼，輸出電文字符串【實(shí)驗(yàn)功能】1、 赫夫曼樹(shù)的建立：從終端讀入字符集大小n，以及n個(gè)字符和n個(gè)權(quán)值，建立赫夫曼樹(shù)，并將它存于文件hfmtree中；2、 赫夫曼編碼的生成：利用以建好的赫夫曼樹(shù)，對(duì)報(bào)文文件ToBeTran中的正文進(jìn)行編碼，然后將結(jié)果存入文件CodeFile中；

3、3、 編碼文件的譯碼：利用已建好的赫夫曼樹(shù)將文件CodeFile中的代碼進(jìn)行譯碼，結(jié)果存入文件TextFile中。實(shí)驗(yàn)結(jié)果（截圖表示）1、以二叉鏈表方式建立二叉樹(shù)，并任選一種遍歷方式輸出結(jié)點(diǎn)的值程序：#include<iostream.h>#include<malloc.h>#define Maxsize 100typedef struct TREEstruct TREE *lTree;struct TREE *rTree;char data;Tree;void InitTree(Tree*);/初始化樹(shù)void CreatTree(Tree*);/創(chuàng)建二叉樹(shù)void

4、PreTraverse(Tree*);/先序遍歷遞歸void PreOrderTraverse(Tree*);/先序遍歷非遞歸void InTraverse(Tree *tree);/中序遍歷遞歸void InOrderTraverse(Tree *tree);/中序遍歷非遞歸void PostTraverse(Tree *tree);/后序遍歷遞歸void LastOrderTraverse(Tree *tree);/后序遍歷非遞歸int DepthTree(Tree *tree);/計(jì)算樹(shù)的深度int LeafsTree(Tree *tree);/計(jì)算葉子結(jié)點(diǎn)個(gè)數(shù)int NodesTree

5、(Tree *tree);/計(jì)算結(jié)點(diǎn)個(gè)數(shù)int Twochild(Tree*tree);/計(jì)算度為二的結(jié)點(diǎn)個(gè)數(shù)void main()int H,L;Tree tree;Tree m;InitTree(&tree);CreatTree(&tree);cout<<"先序遍歷遞歸為:"PreTraverse(&tree);/先序遍歷遞歸cout<<"先序遍歷非遞歸:"PreOrderTraverse(&tree);/先序遍歷非遞歸cout<<endl;cout<<"中序遍

6、歷遞歸為:"InTraverse(&tree);/中序遍歷遞歸cout<<"中序遍歷非遞歸:"InOrderTraverse(&tree);/中序遍歷非遞歸cout<<endl;cout<<"后序遍歷遞歸為:"PostTraverse(&tree);/后序遍歷遞歸cout<<"后序遍歷非遞歸:"LastOrderTraverse(&tree);/后序遍歷非遞歸cout<<endl; cout<<"樹(shù)的深度為:&q

7、uot; H=DepthTree(&tree);cout<<H<<endl;cout<<"葉子結(jié)點(diǎn)個(gè)數(shù):"L=LeafsTree(&tree); cout<<L<<endl;cout<<"結(jié)點(diǎn)個(gè)數(shù)："cout<<NodesTree(&tree)<<endl;cout<<"度為二的結(jié)點(diǎn)個(gè)數(shù)"L=Twochild(&tree);cout<<L<<endl;void InitTr

8、ee(Tree *tree)/初始化樹(shù)tree->lTree=NULL;tree->rTree=NULL;tree->data='0'void CreatTree(Tree *tree)/創(chuàng)建樹(shù)int n=0,m=0,i=0;if(tree->data='0')cout<<"請(qǐng)輸入該節(jié)點(diǎn)的數(shù)據(jù)："cin>>tree->data;cout<<"節(jié)點(diǎn)"<<tree->data<<"是否有左子樹(shù)（0：沒(méi)有 1：有）：&quo

9、t;cin>>n;if(n=1)Tree *lTree=(Tree*)malloc(sizeof(Tree);tree->lTree=lTree;lTree->lTree=NULL;lTree->rTree=NULL;lTree->data='0'CreatTree(tree->lTree);cout<<"節(jié)點(diǎn)"<<tree->data<<"是否有右子樹(shù)（0：沒(méi)有 1：有）："cin>>i;if(i=0);else if(i=1)Tree *r

10、Tree=(Tree*)malloc(sizeof(Tree);tree->rTree=rTree;rTree->lTree=NULL;rTree->rTree=NULL;rTree->data='0'CreatTree(tree->rTree);else if(n=0)cout<<"節(jié)點(diǎn)"<<tree->data<<"是否有右子樹(shù)（0：沒(méi)有 1：有）："cin>>m; if(m=0);else if(m=1)Tree *rTree=(Tree*)mall

11、oc(sizeof(Tree);tree->rTree=rTree;rTree->lTree=NULL;rTree->rTree=NULL;rTree->data='0'CreatTree(tree->rTree);void PreTraverse(Tree*tree)/先序遍歷遞歸if(tree!=NULL)cout<<tree->data<<" "if(tree->lTree!=NULL)PreTraverse(tree->lTree);PreTraverse(tree->rT

12、ree);else if(tree->rTree!=NULL)PreTraverse(tree->rTree);else;void PreOrderTraverse(Tree *tree)/先序遍歷非遞歸Tree *S80=NULL;int top =0;while (tree!=NULL)|(top)if (tree!=NULL)cout<<tree->data<<" "top+;Stop = tree; tree = tree->lTree;elsetree = Stop;top-;tree = tree->rTre

13、e;void InTraverse(Tree *tree)/中序遍歷遞歸if(tree!=NULL)if(tree->lTree!=NULL)InTraverse(tree->lTree);cout<<tree->data<<" "InTraverse(tree->rTree);else if(tree->rTree!=NULL)cout<<tree->data<<" "InTraverse(tree->rTree);elsecout<<tree->

14、;data<<" "void InOrderTraverse(Tree *tree)/中序遍歷非遞歸Tree *D80=NULL;int top =0;while (tree!=NULL)|(top)if (tree!=NULL)top+;Dtop = tree; tree = tree->lTree;elsetree = Dtop;top-;cout<<tree->data<<" "tree = tree->rTree;void PostTraverse(Tree *tree)/后序遍歷遞歸if(t

15、ree!=NULL)if(tree->lTree!=NULL)PostTraverse(tree->lTree);PostTraverse(tree->rTree);cout<<tree->data<<" "else if(tree->rTree!=NULL)PostTraverse(tree->rTree);cout<<tree->data<<" "elsecout<<tree->data<<" "void Las

16、tOrderTraverse(Tree *tree)/后序遍歷非遞歸Tree *stackMaxsize=NULL,*p;p=tree;int top=0,tag=1,i=0,k=0;while(p!=NULL | top)i=1;while(p!=NULL)stack+top=p;p=p->lTree;if(top!=0)p=stacktop->rTree;if(p=NULL)cout<<stacktop->data<<" "if(stacktop!=NULL)while(i)if(stacktop!=NULL)if(stackt

17、op->rTree!=NULL)if(stacktop->rTree->data=stacktop+1->data)cout<<stacktop->data<<" "elsei=0;elsei=0;elsei=0;if(top!=0)p=stacktop->rTree;elsep=NULL;int DepthTree(Tree *tree) /深度函數(shù) int u,v; if (tree=NULL) return 0; u=DepthTree(tree->lTree); v=DepthTree(tree-&g

18、t;rTree); if (u>v) return (u+1); return (v+1); int LeafsTree(Tree *tree)/子葉個(gè)數(shù)函數(shù) int num1,num2; if(tree=NULL) return 0; else if(tree->lTree=NULL&&tree->rTree=NULL) return 1; else num1=LeafsTree(tree->lTree); num2=LeafsTree(tree->rTree); return(num1+num2); int NodesTree(Tree *tr

19、ee)/結(jié)點(diǎn)個(gè)數(shù)函數(shù) int num1,num2; if(tree=NULL) return 0; if(tree->lTree=NULL&&tree->rTree=NULL) return 1; else num1=NodesTree(tree->lTree); num2=NodesTree(tree->rTree); return(num1+num2+1); int Twochild(Tree*tree)/度為2的 int n=0; if(tree=NULL) return(0); if(tree->lTree!=NULL&&t

20、ree->rTree!=NULL) n=1; return(Twochild(tree->lTree)+Twochild(tree->rTree)+n); 實(shí)驗(yàn)結(jié)果截圖：2、哈夫曼編碼程序：#include <stdio.h>#include <stdlib.h>#include <string.h>#define MAXLEN 100typedef struct int weight; int lchild; int rchild; int parent; char key;htnode;typedef htnode hfmtMAXLEN

21、;int n;void inithfmt(hfmt t)/對(duì)結(jié)構(gòu)體進(jìn)行初始化 int i; printf("n"); printf("-n"); printf("*輸入?yún)^(qū)*n"); printf("n請(qǐng)輸入n="); scanf("%d",&n); getchar(); for(i=0;i<2*n-1;i+)/對(duì)結(jié)構(gòu)體進(jìn)行初始化 ti.weight=0; ti.lchild=-1; ti.rchild=-1; ti.parent=-1; printf("n");

22、 void inputweight(hfmt t)/輸入函數(shù) int w;/w表示權(quán)值 int i; char k;/k表示獲取的字符 for(i=0;i<n;i+) printf("請(qǐng)輸入第%d個(gè)字符:",i+1); scanf("%c",&k); getchar(); ti.key=k; printf("請(qǐng)輸入第%d個(gè)字符的權(quán)值:",i+1); scanf("%d",&w); getchar(); ti.weight=w; printf("n"); void selec

23、tmin(hfmt t,int i,int *p1,int *p2)/選中兩個(gè)權(quán)值最小的函數(shù) long min1=999999; long min2=999999; int j; for(j=0;j<=i;j+)/選擇最小權(quán)值字符的下標(biāo)返回 if(tj.parent=-1) if(min1>tj.weight) min1=tj.weight; *p1=j; for(j=0;j<=i;j+)/選擇次小權(quán)值字符的下標(biāo)還回 if(tj.parent=-1) if(min2>tj.weight && j!=(*p1)/注意 j!=(*p1) min2=tj.we

24、ight; *p2=j; void creathfmt(hfmt t)/創(chuàng)建哈夫曼樹(shù)的函數(shù) int i,p1,p2; inithfmt(t); inputweight(t); for(i=n;i<2*n-1;i+) selectmin(t,i-1,&p1,&p2); tp1.parent=i; tp2.parent=i; ti.lchild=p1; ti.rchild=p2; ti.weight=tp1.weight+tp2.weight; void printhfmt(hfmt t)/打印哈夫曼樹(shù) int i; printf("-n"); print

25、f("*哈夫曼編數(shù)結(jié)構(gòu):*n"); printf("tt權(quán)重t父母t左孩子t右孩子t字符t"); for(i=0;i<2*n-1;i+) printf("n"); printf("tt%dt%dt%dt%dt%c",ti.weight,ti.parent,ti.lchild,ti.rchild,ti.key); printf("n-n"); printf("nn"); void hfmtpath(hfmt t,int i,int j)/編碼的重要哈夫曼樹(shù)路徑遞歸算法 i

26、nt a,b; a=i; b=j=ti.parent; if(tj.parent!=-1) i=j; hfmtpath(t,i,j); if(tb.lchild=a) printf("0"); else printf("1"); void phfmnode(hfmt t)/對(duì)字符進(jìn)行初始編碼 int i,j,a; printf("n-n"); printf("*哈夫曼編碼*"); for(i=0;i<n;i+) j=0; printf("n"); printf("tt%ct&qu

27、ot;,ti.key,ti.weight); hfmtpath(t,i,j); printf("n-n"); void encoding(hfmt t)/對(duì)用戶輸入的電文進(jìn)行編碼 char r1000;/用來(lái)存儲(chǔ)輸入的字符串 int i,j; printf("nn請(qǐng)輸入需要編碼的字符:"); gets(r); printf("編碼結(jié)果為:"); for(j=0;rj!='0'j+) for(i=0;i<n;i+) if(rj=ti.key) hfmtpath(t,i,j); printf("n"

28、;); void decoding(hfmt t)/對(duì)用戶輸入的密文進(jìn)行譯碼 char r100; int i,j,len; j=2*n-2;/j初始從樹(shù)的根節(jié)點(diǎn)開(kāi)始 printf("nn請(qǐng)輸入需要譯碼的字符串:"); gets(r); len=strlen(r); printf("譯碼的結(jié)果是:"); for(i=0;i<len;i+) if(ri='0') j=tj.lchild; if(tj.lchild=-1) printf("%c",tj.key); j=2*n-2; else if(ri='1') j=tj.rchild; if(tj.rchild=-1) p