树二叉树的创建及输出哈夫曼编码的输出.docx
- 文档编号:1264286
- 上传时间:2023-04-30
- 格式:DOCX
- 页数:21
- 大小:852.23KB
树二叉树的创建及输出哈夫曼编码的输出.docx
《树二叉树的创建及输出哈夫曼编码的输出.docx》由会员分享,可在线阅读,更多相关《树二叉树的创建及输出哈夫曼编码的输出.docx(21页珍藏版)》请在冰点文库上搜索。
树二叉树的创建及输出哈夫曼编码的输出
一、实验目的:
1.学会实现二叉树结点结构和对二叉树的基本操作。
2.掌握对二叉树每种操作的具体实现,学会利用递归方法编写对二叉树这种递归数据结构进行处理的算法。
3.掌握树的创建即对它的遍历,输出树,以及叶子结点,根结点。
4.哈夫曼树的建立与编码的输出。
二、实验环境:
装有VisualC++6.0的windons.7系统的计算机一台
3、实验内容与步骤:
1..二叉树的创建及输出。
m.h文件:
#include"stdafx.h"
#include
#include
#defineMaxSize100
typedefcharElemType;
typedefstructnode
{
ElemTypedata;/*数据元素*/
structnode*lchild;/*指向左孩子结点*/
structnode*rchild;/*指向右孩子结点*/
}BTNode;
BTNode*CreateBT1(char*pre,char*in,intn);
BTNode*CreateBT2(char*post,char*in,intn);
voidCreateBTNode(BTNode*&b,char*str);
voidDispBTNode(BTNode*b);
BTNode*FindNode(BTNode*b,ElemTypex);
BTNode*LchildNode(BTNode*p);
BTNode*RchildNode(BTNode*p);
intBTNodeHeight(BTNode*b);
pBTNode(BTNode*b);
m.cpp
#include"stdafx.h"
#include
#include"m.h"
BTNode*CreateBT1(char*pre,char*in,intn)
/*pre存放先序序列,in存放中序序列,n为二叉树结点个数,
本算法执行后返回构造的二叉链的根结点指针*/
{
BTNode*s;
char*p;
intk;
if(n<=0)returnNULL;
s=(BTNode*)malloc(sizeof(BTNode));/*创建二叉树结点*s*/
s->data=*pre;
for(p=in;p if(*p==*pre)/*pre指向根结点*/ break;/*在in中找到后退出循环*/ k=p-in;/*确定根结点在in中的位置*/ s->lchild=CreateBT1(pre+1,in,k);/*递归构造左子树*/ s->rchild=CreateBT1(pre+k+1,p+1,n-k-1);/*递归构造右子树*/ returns; } BTNode*CreateBT2(char*post,char*in,intn) /*post存放后序序列,in存放中序序列,n为二叉树结点个数, 本算法执行后返回构造的二叉链的根结点指针*/ { BTNode*s; charr,*p; intk; if(n<=0)returnNULL; r=*(post+n-1);/*根结点值*/ s=(BTNode*)malloc(sizeof(BTNode));/*创建二叉树结点*s*/ s->data=r; for(p=in;p if(*p==r) break; k=p-in;/*k为根结点在in中的下标*/ s->lchild=CreateBT2(post,in,k);/*递归构造左子树*/ s->rchild=CreateBT2(post+k,p+1,n-k-1);/*递归构造右子树*/ returns; } voidCreateBTNode(BTNode*&b,char*str) { BTNode*St[MaxSize],*p=NULL; inttop=-1,k,j=0; charch; b=NULL;/*建立的二叉树初始时为空*/ ch=str[j]; while(ch! ='\0')/*str未扫描完时循环*/ { switch(ch) { case'(': top++;St[top]=p;k=1;break;/*为左孩子结点*/ case')': top--;break; case',': k=2;break;/*为孩子结点右结点*/ default: p=(BTNode*)malloc(sizeof(BTNode)); p->data=ch;p->lchild=p->rchild=NULL; if(b==NULL)/**p为二叉树的根结点*/b=p; else/*已建立二叉树根结点*/ { switch(k) { case1: St[top]->lchild=p;break; case2: St[top]->rchild=p;break; } } } j++; ch=str[j]; } } voidDispBTNode(BTNode*b) { if(b! =NULL) {printf("%c",b->data); if(b->lchild! =NULL||b->rchild! =NULL) {printf("(");/*有孩子结点时才输出(*/ DispBTNode(b->lchild);/*递归处理左子树*/ if(b->rchild! =NULL)printf(",");/*有右孩子结点时才输出,*/ DispBTNode(b->rchild);/*递归处理右子树*/ printf(")");/*有孩子结点时才输出)*/ } } } BTNode*FindNode(BTNode*b,ElemTypex) { BTNode*p; if(b==NULL) returnNULL; elseif(b->data==x) returnb; else { p=FindNode(b->lchild,x); if(p! =NULL) returnp; else returnFindNode(b->rchild,x); } } BTNode*LchildNode(BTNode*p) { returnp->lchild; } BTNode*RchildNode(BTNode*p) { returnp->rchild; } intBTNodeHeight(BTNode*b) { intlchildh,rchildh; if(b==NULL)return(0);/*空树的高度为0*/ else { lchildh=BTNodeHeight(b->lchild);/*求左子树的高度为lchildh*/ rchildh=BTNodeHeight(b->rchild);/*求右子树的高度为rchildh*/ return(lchildh>rchildh)? (lchildh+1): (rchildh+1); } } 工程文件xtt.cpp //xxt.cpp: Definestheentrypointfortheconsoleapplication. // #include"stdafx.h" #include #include"m.h" intmain(intargc,char*argv[]) { ElemTypepre[]="ABDGCEF",in[]="DGBAECF",post[]="GDBEFCA"; BTNode*b1,*b2; b1=CreateBT1(pre,in,7); printf("b1: ");DispBTNode(b1);printf("\n"); b2=CreateBT2(post,in,7); printf("b2: ");DispBTNode(b2);printf("\n"); BTNode*b; CreateBTNode(b,"A(B(D,E),C(,F))"); DispBTNode(b); printf("\n"); return0; 运行结果如下 2.树的子叶 x.h X.cpp 代码为: #include #include"stdafx.h" #include #include"x.h" voidCreateBTNode(BTNode*&b,char*str) { BTNode*St[MaxSize],*p=NULL; inttop=-1,k,j=0; charch; b=NULL;/*建立的二叉树初始时为空*/ ch=str[j]; while(ch! ='\0')/*str未扫描完时循环*/ { switch(ch) { case'(': top++;St[top]=p;k=1;break;/*为左孩子结点*/ case')': top--;break; case',': k=2;break;/*为孩子结点右结点*/ default: p=(BTNode*)malloc(sizeof(BTNode)); p->data=ch;p->lchild=p->rchild=NULL; if(b==NULL)/**p为二叉树的根结点*/ b=p; else/*已建立二叉树根结点*/ { switch(k) { case1: St[top]->lchild=p;break; case2: St[top]->rchild=p;break; } } } j++; ch=str[j]; } } BTNode*FindNode(BTNode*b,ElemTypex) { BTNode*p; if(b==NULL) returnNULL; elseif(b->data==x) returnb; else { p=FindNode(b->lchild,x); if(p! =NULL) returnp; else returnFindNode(b->rchild,x); } } BTNode*LchildNode(BTNode*p) { returnp->lchild; } BTNode*RchildNode(BTNode*p) { returnp->rchild; } intBTNodeHeight(BTNode*b) { intlchildh,rchildh; if(b==NULL)return(0);/*空树的高度为0*/ else { lchildh=BTNodeHeight(b->lchild);/*求左子树的高度为lchildh*/ rchildh=BTNodeHeight(b->rchild);/*求右子树的高度为rchildh*/ return(lchildh>rchildh)? (lchildh+1): (rchildh+1); } } voidDispBTNode(BTNode*b) { if(b! =NULL) {printf("%c",b->data); if(b->lchild! =NULL||b->rchild! =NULL) {printf("(");/*有孩子结点时才输出(*/ DispBTNode(b->lchild);/*递归处理左子树*/ if(b->rchild! =NULL)printf(",");/*有右孩子结点时才输出,*/ DispBTNode(b->rchild);/*递归处理右子树*/ printf(")");/*有孩子结点时才输出)*/ } } } voidDispLeaf(BTNode*b) { if(b! =NULL) { if(b->lchild==NULL&&b->rchild==NULL) printf("%c",b->data);/*访问叶子结点*/ DispLeaf(b->lchild);/*输出左子树中的叶子结点*/ DispLeaf(b->rchild);/*输出右子树中的叶子结点*/ } } voidDispLeaf1(BTNode*b) { if(b! =NULL) { if(b->lchild==NULL&&b->rchild==NULL) printf("%c",b->data);/*访问叶子结点*/ DispLeaf1(b->rchild);/*输出右子树中的叶子结点*/ DispLeaf1(b->lchild);/*输出左子树中的叶子结点*/ } } jjj.cpp 结果是: 3.根据哈夫曼树哈夫输出曼编码: j.cpp文件 工程文件.cpp a.h文件。 运行结果如下: 4.线段树的输出。 z.cpp文件。 工程文件.cpp S.h文件。 运行结果如下: 5.二叉树的先序和中序及高度。 W.h文件: 运行结果如下: 四、实验过程分析: 1.树的遍历运算是指按某种方式访问树中的每一个结点且每一个结点只被访问一次。 先根遍历,即先访问根结点,然后按照从左到右的次序先根遍历根结点的每一棵子树。 后根遍历,即先按照从左到右的次序后根遍历根结点的每一棵子树然后访问根结点。 一个结点所在的层次为其双亲结点所在的层次加1。 树中结点的最大层次称为树的高度(或树的深度)。 2.用先序建树的时候虽然只要输入一个字符串,但是要判断空树的情况。 比较麻烦,我个人觉得用先序与中序联合建树比较简单。 因为这样只要输入先序与中序就可以建树了。 3.对于二叉树的三种遍历的过程,要是用递归写的就根据书上所给出的遍历步骤做稍微的调整就好了。 至于非递归的三种遍历,中序最为简单,用一个栈就可以完成了,思路是边进栈边收索左孩子,直到左孩子为空的时候才开始进行出栈输出再收索右孩子的操作。 而非递归的先序遍历基本可以和中序一样,建立一个队列,在进栈的时候队列也进同样的元素,但是不与栈一起出栈。 而是在最后进栈出栈结束的时候,对队列进行出队列操作即可。 在创建二叉树时CreateBTNode(*b,*str)用ch扫描采用括号表示法表示二叉树的字符串。 分以下几种情况: ①若ch='(': 则将前面刚创建的结点作为双亲结点进栈,并置k=1,表示其后创建的结点将作为这个结点的左孩子结点;②若ch=')': 表示栈中结点的左右孩子结点处理完毕,退栈;③若ch=',': 表示其后创建的结点为右孩子结点; 4.在实验过程中注意程序的编写以及注意的问题。 例如,在树的创建及遍历的过程中,注意数的有关性质。 树中的结点数等于所有结点的度数加1。 度为m的树中第i层上至多有mi-1个结点,这里应有i≥1。 具有n个结点的m次树的最小高度为logm(n(m-1)+1)。 二叉树的有关性质,非空二叉树上叶结点数等于双分支结点数加1。 非空二叉树上第i层上至多有2i-1个结点,这里应有i≥1。 高度为h的二叉树至多有2h-1个结点(h≥1)。 五.实验总结 通过实验能帮助我们更好的使理解有关二叉树和树(树是由n(n≥0)个结点组成的有限集合)的相关知识及相关的性质和算法法。 使我们对所学的知识有了进一步的了解。 二叉树对于进行表达式的前缀,中缀和后缀的表示有明显的优势,既方便,又容易理解。 其先序,中序和后序分别对应这表达式的前缀,中缀和后缀。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 二叉 创建 输出 哈夫曼 编码