《二叉树的基本操作的实验报告》由会员分享,可在线阅读,更多相关《二叉树的基本操作的实验报告(3页珍藏版)》请在金锄头文库上搜索。
1、 实 验 报 告 课程名称 数据结构 实验名称 二叉树 实验时间 12 月 2 日星期二下午 实验地点 数学院楼 504 班 级 信息 1 班 学 号 姓 名 一、实验目的与要求 一.实验目的 1.熟练掌握二叉树的定义和基本操作; 2.灵活运用二叉树解决实际问题。 二.实验内容 1.实现二叉链表的定义和基本操作; 2.试利用二叉树实现哈夫曼编码和译码。 二、实验内容与步骤 一.实验内容 1.实现二叉树的的基本操作:建树,求深度,中序遍历,层次遍历 2.结合表达式求值算法,建立表达式树。 3.记录实验过程并总结实验经验,完成实验报告。 二.实验步骤 1.新建一个文件夹,并命名。 2.将实验材料(
2、附件)中的 c1.h 和 SqStack.cpp、LinkQueue.cpp、BiTree.cpp 文件复制到新文件夹中。 其中,c1.h 中包含程序中常用的头文件及宏定义,以后每次都要记得将该文件包括到你的源程序中。 sqstack.cpp 中包含线性表顺序存储结构的定义和部分基本操作的实现。 LinkQueue.cpp 中包含顺序栈的定义。 BiTree.cpp 中包含链式队列的定义。 3.新建一个 Main4.cpp 源文件(主文件)中, 在其中输入以下三个命令(语句)及一个空的 main 函数 typedef char SElemType; include c1.h include s
3、qstack.cpp main() 4. 在 BiTree.cpp 中 补 充 下 列 函 数 的 定 义 : CreateBiTree , BiTreeDepth ,InOrderTraverse1(递归) , InOrderTraverse2(非递归,要利用栈) ,LevelOrderTraverse(要利用队列) 。 请注意:写完一个函数后,应回到进行调用及编译,检查错误。测试正确后,再开始写其它函数。 5.在 main 函数中编写一个数字菜单,供用户选择:建树,求深度,中序遍历,层次遍历等功能,并显示结果。 编译运行,检查结果是否正确。 6.新建一工程,结合表达式求值的过程,实现创建表达式树的功能。 三、实验结果与问题 实验运行结果截图: 问题: 1. CreateBiTree 函数在建树时对输入序列有何要求? 答:输入序列为先序序列,叶子节点之后要输入两个空格表示没有左右孩子 2. 中序遍历递归算法中,递归基本项(终止条件)是什么? 答:终止的条件为左右孩子结点为空 3. 中序遍历非递归算法中,如何找到中序遍历序列中的第一个结点? 答:while(GetTop(S,p)&p) Push(S,p-lchild);向左走到尽头,即为中序遍历序列中的第一个结点 4. 在建表达式树时,栈元素应该定义为何种数据类型? 答:字符型。 指导老师 姚 兰 评分情况