二叉树的基本操作的实验报告.pdf

实 验 报 告 课程名称 数据结构 实验名称 二叉树 实验时间 12 月 2 日星期二下午 实验地点 数学院楼 504 班 级 信息 1 班 学 号 姓 名 一、实验目的与要求 一.实验目的 1.熟练掌握二叉树的定义和基本操作；2.灵活运用二叉树解决实际问题。二.实验内容 1.实现二叉链表的定义和基本操作；2.试利用二叉树实现哈夫曼编码和译码。二、实验内容与步骤 一.实验内容 1.实现二叉树的的基本操作：建树，求深度，中序遍历，层次遍历 2.结合表达式求值算法，建立表达式树。3.记录实验过程并总结实验经验，完成实验报告。二.实验步骤 1.新建一个文件夹，并命名。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 sqstack.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.在建表达式树时，栈元素应该定义为何种数据类型？答：字符型。指导老师 姚 兰 评分情况