齐鲁工业大学实验报告
课程名称
数据结构
指导教师 专业班级
高晨悦
成绩
单健芳 ___________ 实验日期 计科(嵌入)14-1 实验地点
院(系) 信息学院 学生姓名 实验项目名称
学号 201403071007 __________ 同组人 ________ 无
二叉树的递归算法
一、 实验目的和要求
1. 实现二叉树的先序，中序与后序遍历的递归算法与非递归算法。 2. 求二叉树的结点个数，叶子结点个数，二叉树的高度，度为
二、 实验环境 微型计算机vc 6.0 三、 实验内容
2的结点个数。
1. 实现二叉树的先序，中序与后序遍历的递归算法与非递归算法。 2. 求二叉树的结点个数，叶子结点个数，二叉树的高度，度为
四、 实验步骤 一?实验内容
2的结点个数。
1. 实现二叉树的先序，中序与后序遍历的递归算法与非递归算法。 2. 求二叉树的结点个数，叶子结点个数，二叉树的高度，度为
二?程序的设计思想
2的结点个数。
1实现二叉树的先序，中序与后序遍历的递归算法与非递归算法。
先构造二叉树，根据先序遍历的思想，输入根后，再输入左子树，直至左子树为空则 输入上一层右字树。
(1) 二叉树的非递归遍历是用显示栈来存储二叉树的结点指针，先序遍历时，按二叉 树前序遍历的顺序访问结点，并将结点的指针入栈，直到栈顶指针指向结点的左指针域为 空时取出栈顶指针并删除栈顶指针，访问刚取出的指针指向的结点的右指针指向的结点并 将其指针入栈，如此反复执行则为非递归操作。
(2) 二叉树的递归遍历：若二叉树为空，则空操作 先序遍历： (a) 访问根结点； (b) 先序遍历左子树； (c) 先序遍历右子树。 中序遍历：
山东轻工业学院实验报告（附页）
（a）中序遍历左子树；
（b）访问根结点； （c ）中序遍历右子树 后序遍历：
（a） 后序遍历左子树； （b） 后序遍历右子树； （c） 访问根结点。
2.求二叉树的结点个数，叶子结点个数，二叉树的高度，度为 2的结点个数。
（1） 求二叉树的叶子结点个数：先分别求得左右子树中个叶子结点的个数，再计算 出两者之和
即为二叉树的叶子结点数。
（2） 二叉树的结点个数之和：先分别求得左子树右子树中结点之和，再计算两者之 和即为所
求。
（3） 二叉树的高度：首先判断二叉树是否为空，若为空则此二叉树高度为
就先分别求出左右子树的深度进行比较，取较大的树加一即为所求。 （4）二叉树的度为2的结点个数：计算有左右孩子的结点个数，即为度为 三?编程过程中遇到的问题及解决办法
（1） 后续遍历的非递归函数涉及到回溯的方法，开始设计的方案想的太过于简单，所以 形成了死循环，总是在最后的节点处不停地循环，后改成回溯后，该问题得到解决。
（2） 计算二叉树中度为2的结点个数中，返回循环的时候不论根结点有没有左右子树， 但个人设计时，根总是会将自己默认为有左右子树， 己的这个失误。
四?程序的闪光点（自我评价）
自行增加1.后在同学帮助下才看到自
0,。否则, 2的结点个数。
1. 程序模块化，各个函数分开描述，方便观察 2. 关键处有注释
3. 建立二叉树时，用先序提示输入，比较人性化。
五?程序源代码（以文件为单位提供）
#i nclude
#defi ne Maxsize 100 typedef struct TREE{
struct TREE *lTree;
山东轻工业学院实验报告（附页）
struct TREE *rTree; char data; }Tree;
void In itTree(Tree*);〃
初始化树
void PreOrderTraverse(Tree*);〃 void In Traverse(Tree *tree);〃 void InO rderTraverse(Tree *tree);〃
void PostTraverse(Tree *tree);〃
先序遍历非递归 中序遍历递归
中序遍历非递归 后序遍历递归
void CreatTree(Tree*);〃 创建二叉树 void PreTraverse(Tree*);〃
先序遍历递归
计算叶子结点个数 计算结点个数
计算度为二的结点个数
void LastOrderTraverse(Tree *tree);〃
后序遍历非递归
int DepthTree(Tree *tree);〃 计算树的深度
void main()
int LeafsTree(Tree *tree);〃
{
int NodesTree(Tree
int H,L; *tree);〃
Tree tree;
// Tree m;
In itTree(& tree); CreatTree(&tree); coutvv\先序遍历递归为:\
PreTraverse(&tree);〃 先序遍历递归 coutvv\先序遍历非递归:\
PreOrderTraverse(&tree);〃 先序遍历非递归
数据结构二叉树的递归算法实验报告word精品
