树与二叉树实验

1、福州大学数计学院数据结构上机实验报告专业：信息数学学号031201206姓名詹小青班级02班实验名称树与二叉树实验实验内容树型结构及其应用实验目的和要求【背景知识】二叉树的存储、建立、遍历及其应用。【目的要求】1掌握二叉树的存储实现。 2掌握二叉树的遍历思想。 3掌握二叉树的常见算法的程序实现。【实验主要内容】运用树的结构来实现建树、遍历等算法，并能运用，如哈夫曼问题的设计。问题描述和主要步骤1、以二叉链表方式建立二叉树，并任选一种遍历方式输出结点的值【实验目的】（1）了解二叉树的结构特点及有关概念，掌握二叉树建立的基本算法； （2）了解二叉树遍历的概念，掌握遍历二叉的算法。【实验内容】按层次

2、序依次输入元素值，以链表方式建立该二叉树，然后可依据先序、中序、后序中的任一种遍历方法遍历二叉树的方式输出结点的值。2、哈夫曼编码【实验目的】了解赫夫曼树的结构特点及有关概念，掌握赫夫曼树的建立和赫夫曼编码的设计【问题描述】使用二叉树进行赫夫曼编码的设计，要求对输入的一串电文字符实现赫夫曼编码，再对赫夫编码生成的代码串进行译码，输出电文字符串【实验功能】1、 赫夫曼树的建立：从终端读入字符集大小n，以及n个字符和n个权值，建立赫夫曼树，并将它存于文件hfmtree中；2、 赫夫曼编码的生成：利用以建好的赫夫曼树，对报文文件ToBeTran中的正文进行编码，然后将结果存入文件CodeFile中；

3、3、 编码文件的译码：利用已建好的赫夫曼树将文件CodeFile中的代码进行译码，结果存入文件TextFile中。实验结果（截图表示）1、以二叉链表方式建立二叉树，并任选一种遍历方式输出结点的值程序：#include<iostream.h>#include<malloc.h>#define Maxsize 100typedef struct TREEstruct TREE *lTree;struct TREE *rTree;char data;Tree;void InitTree(Tree*);/初始化树void CreatTree(Tree*);/创建二叉树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);/计算树的深度int LeafsTree(Tree *tree);/计算叶子结点个数int NodesTree

5、(Tree *tree);/计算结点个数int Twochild(Tree*tree);/计算度为二的结点个数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<<"树的深度为:&q

7、uot; H=DepthTree(&tree);cout<<H<<endl;cout<<"叶子结点个数:"L=LeafsTree(&tree); cout<<L<<endl;cout<<"结点个数："cout<<NodesTree(&tree)<<endl;cout<<"度为二的结点个数"L=Twochild(&tree);cout<<L<<endl;void InitTr

8、ee(Tree *tree)/初始化树tree->lTree=NULL;tree->rTree=NULL;tree->data='0'void CreatTree(Tree *tree)/创建树int n=0,m=0,i=0;if(tree->data='0')cout<<"请输入该节点的数据："cin>>tree->data;cout<<"节点"<<tree->data<<"是否有左子树（0：没有 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<<"节点"<<tree->data<<"是否有右子树（0：没有 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<<"节点"<<tree->data<<"是否有右子树（0：没有 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) /深度函数 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)/子叶个数函数 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)/结点个数函数 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); 实验结果截图：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)/对结构体进行初始化 int i; printf("n"); printf("-n"); printf("*输入区*n"); printf("n请输入n="); scanf("%d",&n); getchar(); for(i=0;i<2*n-1;i+)/对结构体进行初始化 ti.weight=0; ti.lchild=-1; ti.rchild=-1; ti.parent=-1; printf("n");

22、 void inputweight(hfmt t)/输入函数 int w;/w表示权值 int i; char k;/k表示获取的字符 for(i=0;i<n;i+) printf("请输入第%d个字符:",i+1); scanf("%c",&k); getchar(); ti.key=k; printf("请输入第%d个字符的权值:",i+1); scanf("%d",&w); getchar(); ti.weight=w; printf("n"); void selec

23、tmin(hfmt t,int i,int *p1,int *p2)/选中两个权值最小的函数 long min1=999999; long min2=999999; int j; for(j=0;j<=i;j+)/选择最小权值字符的下标返回 if(tj.parent=-1) if(min1>tj.weight) min1=tj.weight; *p1=j; for(j=0;j<=i;j+)/选择次小权值字符的下标还回 if(tj.parent=-1) if(min2>tj.weight && j!=(*p1)/注意 j!=(*p1) min2=tj.we

24、ight; *p2=j; void creathfmt(hfmt t)/创建哈夫曼树的函数 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)/打印哈夫曼树 int i; printf("-n"); print

25、f("*哈夫曼编数结构:*n"); printf("tt权重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)/编码的重要哈夫曼树路径递归算法 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)/对字符进行初始编码 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)/对用户输入的电文进行编码 char r1000;/用来存储输入的字符串 int i,j; printf("nn请输入需要编码的字符:"); gets(r); printf("编码结果为:"); 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)/对用户输入的密文进行译码 char r100; int i,j,len; j=2*n-2;/j初始从树的根节点开始 printf("nn请输入需要译码的字符串:"); gets(r); len=strlen(r); printf("译码的结果是:"); 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