《二叉树的基本操作的实验报告》由会员分享，可在线阅读，更多相关《二叉树的基本操作的实验报告（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. 在建表达式树时，栈元素应该定义为何种数据类型？ 答：字符型。 指导老师 姚 兰 评分情况
