




版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
实验6:二叉树的基本操作
一、实验目的
1.掌握二叉树的非线性和递归性特点
2.理解二叉树的存储结构
3.掌握二叉树遍历操作
二、实验内容
1.使用二叉链表,创建一个如图(a)的二叉树。可以用先序、中序和后序方式遍历二叉树并将
结点输出,.统计出一个二叉树叶子节点及树的深度。
#include<iostream>
#include<cstdio>
usingnamespacestd;
typedefcharDatatype;
intent;
structTNode
(
Datatypedata;
TNode*rchild;
TNode*Ichild;
voidCreatTree(TNode*&root)
(
charndata;
cin»ndata;
if(ndata==^#^)root=NULL;
else
(
root=newTNode;root->data=ndata;
CreatTree(root->lchild);
CreatTree(root->rchild);
}
)
voidpreOrderTraver(TNode*&root)//先
(
if(root!=NULL)
cout«root->data«nn;
preOrderTraver(root->lchild);
preOrderTraver(root->rchild);
)
)
voidInOrderTraver(TNode*&root)〃中
(
if(root!=NULL)
(
InOrderTraver(root->lchild);
cout«root->data«"
InOrderTraver(root->rchild);
)
)
voidposOrderTraver(TNode*&root)〃后
(
if(root!=NULL)
(
posOrderTraver(root->lchild);
posOrderTraver(root->rchild);
cout«root->data«"
)
)
intBTHeight(TNode*t)/〃二叉树的深度
(
intans=0;
if(t==NULL)return0;
elseif(t!=NULL)
ans+=max(ans,max(BTHeight(t->lchild),BTHeight(t->rchild))+1);
returnans;
)
intBTLeafNode(TNode*t)/〃二叉树的叶子节点数
(
if(t!=NULL)
(
if(t->lchild==NULL&&t->rchild==NULL)
(
printf("%c",t->data);
cnt++;
)
else
(
BTLeafNode(t->lchild);
BTLeafNode(t->rchild);
returnent;
}
intmain()
{
TNode*root=NULL;
coutvv”请输入该二叉树的先序遍历结果:\n";
CreatTree(root);
coutvv”先序遍历结果"vvendl;
preOrderTraver(root);cout«endl;
cout<v”中序遍历结果:"<<endl;
InOrderTraver(root);cout«endl;
cout<<”后序遍历结果:n«endl;
posOrderTraver(root);cout«endl;
printf(”\n输出二叉树的深度:");
intsum=BTHeight(root);
cout«sum«endl;
printff输出二叉树的叶子结点:”);
intans=BTLeafNode(root);
printf(”\n输出二叉树的叶子结点的个数:”);
cout«ans«endl;
return0;
)
运行结果:
存在问题:无
2.对于给定的w={2,3,4,7,8,9}权值,试构造一棵哈夫曼树,并给出各个节点的huffman编码及huffman数
组的值。
#defineN50〃叶子结点数
#defineM2*N-1〃树中结点总数
typedefstruct
(
chardata[5];〃结点值
intweight;〃权重
intparent;〃双亲结点
intIchild;〃左孩子结点
intrchild;〃右孩子结点
}HTNode;
typedefstruct
charcd[N];〃存放哈夫曼码
intstart;
}HCode;
voidCreateHT(HTNodeht[],intn)
{
inti,k,Inode,mode;
doubleminl,min2;
for(i=0;i<2*n-l;i++)〃所有结点的相关域置初值-1
htfi].parent=ht[i].lchild=ht[i].rchild=-l;
for(i=n;i<2*n-l;i++)〃构造哈夫曼树
(
minl=min2=32767;//Inode和mode为最小权重的两个结点位置
lnode=rnode-1;
for(k=0;k<=i-l;k++)
if(ht[k].parent==-l)〃只在尚未构造二叉树的结点中查找
(
if(ht[k].weighKmin1)
(
min2=minl;rnode=lnode;
mini=ht[k].weight;lnode=k;
)
else
(
if(ht[k].weight<min2)
(
min2=ht[k].weight;
rnode=k;
ht[i].weight=ht[lnode].weight+ht[rnode].weight;
ht[il.lchild=lnode;ht[i].rchild=rnode;
ht[lnode].parent=i;ht[rnode].parent=i;
)
)
voidCreateHCode(HTNodeht[l,HCodehcd[],intn)
(
inti,f,c;
HCodehe;
for(i=0;i<n;i++)〃根据哈夫曼树求哈夫曼编码
(
f=ht[i],parent;
while(f!=-l)〃循序直到树根结点
(
if(htff].lchild==c)〃处理左孩子结点
else〃处理右孩子结点
c=f;f=ht[f].parent;
)
指向哈夫曼编码最开始字符
hcd[i]=hc;
)
)
voidDispHCode(HTNodeht[],HCodehcd[],intn)
(
inti,k;
intsum=0,m=0;
intj;
printf("输出哈夫曼数组的值及编码:\n");〃输出哈夫曼编码
for(i=0;i<n;i++)
(
j=0;
printf("%s:\t",ht[i].data);
for(k=hcdfi].start;k<=n;k++)
printf(0%cn,hcd[i].cd[k]);
j++;
)
m+=htfi].weight;
sum+=ht[i].weight*j;
printf("\nn);
)
printf("\n带权路径长度WPL=%d\n",sum);
)
intmain()
(
intn=6,i;〃11表示初始字符串的个数
char*str[]={"2","3","4","7","8","9"};
intfnum[]={2,3,4,7,8,9};
HTNodeht[M];
HCodehcd[N];
for(i=0;i<n;i++)
(
strcpy(ht[i].data,str[i]);
ht[i].weight=fnum[i];
)
printf("\n");
CreateHT(ht,n);
CreateHCode(ht,hcd,n);
DispHCode(ht,hcd,n);
printf("\n");
)
测试数据:
运行结果:
存在问题:
二、本次实验问题分析及学习建议
备注:
1.每次实验完毕,各位学生可提交实验报告纸质(A
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 【正版授权】 ISO/IEC 14888-4:2024 EN Information security - Digital signatures with appendix - Part 4: Stateful hash-based mechanisms
- 2025年充电桩充电设备生产许可证申请与审批合同
- 2025年度新能源汽车充电桩建设与运营服务合同-@-3
- 2024 年度中国汽车行业争议解决报告
- 2025年度小时工维修养护服务合同范本
- 2025年度知识产权保险产品代理与服务合同
- 2025年心电遥测监护仪项目合作计划书
- 英语-黑龙江省大庆市实验中学2024-2025学年高一上学期阶段考试
- 2025年沥青试验仪器项目合作计划书
- 2025年度走读生户外活动安全责任承诺协议范本
- 颅内动脉瘤介入治疗课件
- 马蹄焰玻璃窑炉设计技术培训-课件
- 2023年主治医师(中级)-眼科学(中级)代码:334考试历年真题集锦附答案
- 种植林业可行性研究报告
- 测试文档-可能-歌词1
- 金和物业公司简介
- 电力安全工作规程-(电网建设部分)
- 广东省五年一贯制考试英语真题
- 项目部岗位廉洁风险情景教育案例
- 小学英语-What a dream教学设计学情分析教材分析课后反思
- 数据分析系统Hive培训课件
评论
0/150
提交评论