版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、实验六 二叉树构造和遍历一. 实验目的 掌握二叉树的逻辑结构; 掌握二叉树的二叉链表存储结构; 掌握基于二叉链表存储的二叉树的遍历操作的实现。二. 实验环境Windows操作系统,Visual C+ 6.0编程环境。三. 实验内容和步骤1观察下面图6-1的二叉树,回答问题。图6-1(1) 写出前序、中序和后序遍历序列;前序:ABDECFG 中序:DBEAFGC 后序:DEBGFCA(2) 分别写单支结点和叶子结点;单支结点:CF 叶子结点:DEG(3) 以”#”补充所有结点的空分支;ABD#E#CF#G#(4)写出补充空分支后二叉树的前序遍历序列(扩展的前序遍历序列); ABD#E#CF#G#
2、2建立工程Bitree,编写Biree.h,Biree.cpp和测试函数Bireemain.cpp,完成下列功能。 建立一棵含有n个结点的二叉树,采用二叉链表存储; 前序(或中序、后序)遍历该二叉树。四编码 头文件Bitree.h#includeusing namespace std;template struct BiNodeT data; BiNode *lchild, *rchild;template class BiTreepublic:BiTree()root=Creat(root); /有参构造函数,初始化一棵二叉树,其前序序列由键盘输入 BiTree()Release(root)
3、; /析构函数,释放二叉链表中各结点的存储空间 void PreOrder()PreOrder(root); /前序遍历二叉树 void InOrder()InOrder(root); /中序遍历二叉树 void PostOrder()PostOrder(root); /后序遍历二叉树private: BiNode *root; /指向根结点的头指针 BiNode *Creat(BiNode *bt); /有参构造函数调用 void Release(BiNode *bt); /析构函数调用 void PreOrder(BiNode *bt); void InOrder(BiNode *bt);
4、 void PostOrder(BiNode *bt);template BiNode *BiTree:Creat(BiNode *bt)T ch; cinch; if(ch=#)bt=NULL; /建立一棵空树 else bt=new BiNode; /生成一个结点 bt-data=ch; bt-lchild=Creat(bt-lchild); /递归建立左子树 bt-rchild=Creat(bt-rchild); /递归建立右子树return bt;template void BiTree:Release(BiNode *bt)if(bt!=NULL)Release(bt-lchild)
5、;Release(bt-rchild);delete bt;template void BiTree:PreOrder(BiNode *bt) if (bt=NULL) return; /递归调用的结束条件 else coutdata; /访问根结点的数据域 PreOrder(bt-lchild); /前序递归遍历root的左子树 PreOrder(bt-rchild); /前序递归遍历root的右子树 template void BiTree:InOrder(BiNode *bt) if (bt=NULL) return; /递归调用的结束条件 else InOrder(bt-lchild)
6、;coutdata; InOrder(bt-rchild); template void BiTree:PostOrder(BiNode *bt) if (bt=NULL) return; /递归调用的结束条件 else PostOrder(bt-lchild); PostOrder(bt-rchild);coutdata; 主函数main#includeBitree.hvoid main()int c=1;while(c)cout输入前序序列:;BiTree tree;cout前序遍历:;tree.PreOrder();coutendl; cout中序遍历:;tree.InOrder();c
7、outendl;cout后序遍历:;tree.PostOrder();coutendl;cout0.结束 1.重试endl;coutc;五.调试结果(表5-1) (表5-1)二叉树验证实验调试结果六实验小结本次实验主要是通过实验过程掌握二叉树的逻辑结构,掌握二叉树的二叉链表存储结构和掌握基于二叉链表存储的二叉树的遍历操作的实现。哈夫曼编码代码#includeusing namespace std;const int Size=10,Size1=50; struct elementint weight;int lchild,rchild,parent;int getW(char T,int *w
8、,char *s)char c;int count,k=0;for(int i=0;Ti!=0;i+)count=0;if(Ti=a&T1hi4.weight) c=i3;i3=i4;i4=c;for(i;hi.weight0;i+)if(hi.parent=-1)if(hi.weighthi3.weight)i4=i3,i3=i;else if(hi.weighthi4.weight)i4=i;void HuffmanTree(element *huffTree,int w,int n)int i1,i2;for(int i=0;i2*n-1;i+)huffTreei.parent=-1;
9、huffTreei.lchild=-1; huffTreei.rchild=-1;for(i=0;in;i+)huffTreei.weight=wi;for(int k=n;k2*n-1;k+)Select(huffTree,i1,i2);huffTreei1.parent=k;huffTreei2.parent=k; huffTreek.weight=huffTreei1.weight+huffTreei2.weight; huffTreek.lchild=i1; huffTreek.rchild=i2;void bm(element h,int m)char bSize;b0=0; int
10、 sSize,cd;int top=-1,i=0,k;while(m!=-1|top!=-1)while(m!=-1)if(hm.lchild=-1 & hm.rchild=-1)/记录路径编码0,1的算法,用到parent回溯。cd=0;for(int j=hm.parent;j!=-1;j=hj.parent)cd+;bcd=0;k=m;for(j=hk.parent;j!=-1;j=hj.parent)if(hj.lchild=k) b-cd=0;else b-cd=1;k=j;couthm.weight:bendl;s+top=m;m=hm.lchild;if(top!=-1)m=stop-;m=hm.rchild;void main()char TSize1,sSiz
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 2024-2034年中国调节球阀行业竞争格局分析及投资战略咨询报告
- 2024-2034年中国衣物护洗袋行业市场深度调研分析及投资前景研究预测报告
- 2024-2034年中国蒸汽挂熨衣机行业市场深度分析及投资战略研究报告
- 2024-2034年中国脱硝产品市场深度调研分析及投资前景研究预测报告
- 2024-2034年中国聚羧酸减水剂行业市场运行态势及投资战略咨询研究报告
- 2024-2034年中国绵羊养殖行业市场发展趋势展望与投资策略分析报告
- 2024-2034年中国纪录片行业市场全景评估及发展战略规划报告
- 2024-2034年中国粗杂粮行业市场发展监测及投资战略规划研究报告
- 2024-2034年中国空心导轨行业市场深度分析及投资战略研究报告
- 2024-2034年中国福美钠行业发展前景预测及投资战略研究报告
- 中学生合理使用手机家长沟通会课件
- 越野跑策划方案
- 变革管理与变革领导力
- 免疫系统和人体防御机制
- 全国优质课一等奖初中音乐《姹紫嫣红》课件
- 销售实施管控方案
- 智慧养老服务平台建设投标方案(技术方案)
- 人教版小学道德与法治《众志成城》教学设计
- 观测墩施工方案
- 空调登高施工方案
- 化工产品包销协议书 化工产品销售合同正规范本(通用版)
评论
0/150
提交评论