- 1、本文档共10页,可阅读全部内容。
- 2、原创力文档(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
实 验 报 告
课程名称 数据结构
实验项目 实验三--创建一个二叉树并输出三种遍历结果
系 别___ _计算机学院 _ ______
专 业___ ___
班级/学号___________
学生姓名 _________
实验日期 _
成 绩 _______________________
指导教师
实验题目:实验三------创建一个二叉树并输出三种遍历结果
实验目的
掌握二叉树存储结构;
掌握并实现二叉树遍历的递归算法和非递归算法;
理解树及森林对二叉树的转换;
理解二叉树的应用—哈夫曼编码及WPL计算。
实验内容
以广义表或遍历序列形式创建一个二叉树,存储结构自选;
输出先序、中序、后序遍历序列;
二选一应用题:1)树和森林向二叉树转换;2)哈夫曼编码的应用问题。(应用型题目可替换上述前两项实验内容)
设计与编码
程序结构基本设计框架
(提示:请根据所选定题目,描述程序的基本框架,可以用流程图、界面描述图、框图等来表示)
本实验用到的理论知识
遍历二叉树,递归和非递归的方法
(提示:总结本实验用到的理论知识,实现理论与实践相结合。总结尽量简明扼要,并与本次实验密切相关,要求结合自己的题目并阐述自己的理解和想法)
具体算法设计
首先,定义二叉树的存储结构为二叉链表存储,每个元素的数据类型Elemtype,定义一棵二叉树,只需定义其根指针。
然后以递归的先序遍历方法创建二叉树,函数为CreateTree(),在输入字符时要注意,当节点的左孩子或者右孩子为空的时候,应当输入一个特殊的字符(本算法为“#”),表示左孩子或者右孩子为空。
下一步,创建利用递归方法先序遍历二叉树的函数,函数为PreOrderTree(),创建非递归方法中序遍历二叉树的函数,函数为InOrderTree(),中序遍历过程是:从二叉树的根节点开始,沿左子树向下搜索,在搜索过程将所遇到的节点进栈;左子树遍历完毕后,从栈顶退出栈中的节点并访问;然后再用上述过程遍历右子树,依次类推,指导整棵二叉树全部访问完毕。创建递归方法后序遍历二叉树的函数,函数为LaOrderTree()。
(提示:该部分主要是利用C、C++等完成数据结构定义、设计算法实现各种操作,可以用列表分步形式的自然语言描述,也可以利用流程图等描述)
编码
#includestdio.h
#includemalloc.h
#includestdlib.h
typedef char DataType;
#define MaxSize 100
typedef struct Node
{
DataType data;
struct Node *lchild;
struct Node *rchild;
}
*BiTree,BitNode;
void InitBitTree(BiTree *T); /*树的初始化*/
void CreateBitTree(BiTree *T); /*按照先序输入字符序列递归创建二叉树*/
void PreOrderTraverse(BiTree T); /*二叉树的先序遍历的递归函数声明*/
void InOrderTraverse(BiTree T); /*二叉树的中序遍历的递归函数声明*/
void PostOrderTraverse(BiTree T); /*二叉树的后序遍历的递归函数声明*/
void PreOrderTraverse2(BiTree T); /*二叉树的先序遍历的非递归函数声明*/
void InOrderTraverse2(BiTree T); /*二叉树的中序遍历的非递归函数声明*/
void PostOrderTraverse2(BiTree T); /*二叉树的后序遍历的非递归函数声明*/
void main()
{
BiTree T,root;
InitBitTree(T);
printf(根据输入二叉树的先序序列创建二叉树(#表示结束):\n);
CreateBitTree(T);
printf(二叉树的先序序列:\n);
printf(递归:\t);
PreOrderTraverse(T);
printf(\n);
printf(非递归:);
PreOrderTraverse2(T);
printf(\n);
printf(二叉树的中序序列:\n);
printf(递归:\t);
InOrderTrave
您可能关注的文档
- 刚体41(免费阅读).ppt
- 刚体6.ppt
- 四年级品德与社会《交通问题带来的思考》.ppt
- 刘金山电子音乐门铃的制作.ppt
- 刘湘知识树说课.ppt
- 刚体力学 PowerPoint 演示文稿.ppt
- 刚体力学-7-刚体动力学--举例.ppt
- 刚体01W08.ppt
- 刚体习题课-sx205.ppt
- 四年级语文上册《飞夺泸定桥》(修改后).ppt
- 专题1.1 锐角的三角函数【十大题型】(举一反三)(北师大版)(解析版).pdf
- 专题1.1 绝对值贯穿有理数经典题型(七大题型)(解析版).pdf
- 模块三 IP地址规划实践.pptx
- 第10章 虚拟现实《射柳》原型开发实例.pptx
- 专题1.1 丰富的图形世界(压轴题综合测试卷)(北师大版)(原卷版).pdf
- 专题1.1 认识立体图形、展开与折叠【八大题型】(举一反三)(北师大版)(原卷版).pdf
- 专题1.1 数轴上的动点问题(压轴题专项讲练)(人教版)(解析版).pdf
- 小学生必知的科学小知识大全.pdf
- 小学数学四 走进动物园——简易方程教学设计学情分析教材分析课后反思.pdf
- 小学数学教学反思范文10篇.pdf
最近下载
- QB_T 4563-2013金砂糖.pdf
- 大坝安全监测系统运检导则(试行) QGDW 46 10022.24-2020.docx VIP
- 第五单元 一方水土养一方人 达标训练(含答案) 浙江省人教版七年级人文地理下册.docx
- 奋进新征程建功新时代PPT模板.ppt VIP
- 规范《GB712-88-船体用结构钢》.pdf
- 二年级上册语文教学设计21《狐假虎威》一等奖 刘芳 部编版.docx VIP
- Q_GDW 46 10022.25-2020 通风空调系统运检导则.docx
- 12如何帮助学生学会正确地与异性同学交往?.docx VIP
- 专题1.2 数轴与动点经典题型(四大题型)(原卷版).docx VIP
- 拉森钢板桩专项施工方案.doc
文档评论(0)