数据结构二叉树的递归算法实验报告

齐鲁工业大学实验报告 成绩

课程名称 数据结构 指导教师 单健芳 实验日期

院（系） 信息学院 专业班级 计科（嵌入）14-1 实验地点

学生姓名 高晨悦 学号 201403071007 同组人 无

实验项目名称 二叉树的递归算法

一、实验目的和要求

1.实现二叉树的先序，中序与后序遍历的递归算法与非递归算法。

2.求二叉树的结点个数，叶子结点个数，二叉树的高度，度为2的结点个数。 二、实验环境 微型计算机vc 6.0 三、实验内容

1.实现二叉树的先序，中序与后序遍历的递归算法与非递归算法。

2.求二叉树的结点个数，叶子结点个数，二叉树的高度，度为2的结点个数。 四、实验步骤 一．实验内容

1.实现二叉树的先序，中序与后序遍历的递归算法与非递归算法。

2.求二叉树的结点个数，叶子结点个数，二叉树的高度，度为2的结点个数。 二．程序的设计思想

1实现二叉树的先序，中序与后序遍历的递归算法与非递归算法。

先构造二叉树，根据先序遍历的思想，输入根后，再输入左子树，直至左子树为空则输入上一层右字树。

（1）二叉树的非递归遍历是用显示栈来存储二叉树的结点指针，先序遍历时，按二叉树前序遍历的顺序访问结点，并将结点的指针入栈，直到栈顶指针指向结点的左指针域为空时取出栈顶指针并删除栈顶指针，访问刚取出的指针指向的结点的右指针指向的结点并将其指针入栈，如此反复执行则为非递归操作。 （2）二叉树的递归遍历：若二叉树为空，则空操作

先序遍历： （a）访问根结点； （b）先序遍历左子树；

（c）先序遍历右子树。

山东轻工业学院实验报告（附页）

中序遍历 ： （a）中序遍历左子树； （b）访问根结点；

（c）中序遍历右子树 后序遍历：

（a）后序遍历左子树； （b）后序遍历右子树； （c）访问根结点。

2.求二叉树的结点个数，叶子结点个数，二叉树的高度，度为2的结点个数。 （1）求二叉树的叶子结点个数：先分别求得左右子树中个叶子结点的个数，再计算出两者之和即为二叉树的叶子结点数。

（2）二叉树的结点个数之和：先分别求得左子树右子树中结点之和，再计算两者之和即为所求。

（3）二叉树的高度：首先判断二叉树是否为空，若为空则此二叉树高度为0,。否则，就先分别求出左右子树的深度进行比较，取较大的树加一即为所求。

（4）二叉树的度为2的结点个数：计算有左右孩子的结点个数，即为度为2的结点个数。 三．编程过程中遇到的问题及解决办法

（1）后续遍历的非递归函数涉及到回溯的方法，开始设计的方案想的太过于简单，所以形成了死循环，总是在最后的节点处不停地循环，后改成回溯后，该问题得到解决。 （2）计算二叉树中度为2的结点个数中，返回循环的时候不论根结点有没有左右子树，但个人设计时，根总是会将自己默认为有左右子树，自行增加1.后在同学帮助下才看到自己的这个失误。

四．程序的闪光点(自我评价)

1.程序模块化，各个函数分开描述，方便观察 2.关键处有注释

3.建立二叉树时，用先序提示输入，比较人性化。 五．程序源代码(以文件为单位提供) #include #include

#define Maxsize 100 typedef struct TREE{

struct TREE *lTree;

山东轻工业学院实验报告（附页）

struct TREE *rTree; char data;

}Tree;

void InitTree(Tree*);//初始化树 void CreatTree(Tree*);//创建二叉树 void PreTraverse(Tree*);//先序遍历递归 void PreOrderTraverse(Tree*);//先序遍历非递归 void InTraverse(Tree *tree);//中序遍历递归 void InOrderTraverse(Tree *tree);//中序遍历非递归 void PostTraverse(Tree *tree);//后序遍历递归 void LastOrderTraverse(Tree *tree);//后序遍历非递归 int DepthTree(Tree *tree);//计算树的深度 int LeafsTree(Tree *tree);//计算叶子结点个数 int NodesTree(Tree *tree);//计算结点个数 int Twochild(Tree*tree);//计算度为二的结点个数

void main() {

int H,L; Tree tree;

// Tree m;

InitTree(&tree); CreatTree(&tree); cout<<\先序遍历递归为:\

PreTraverse(&tree);//先序遍历递归 cout<<\先序遍历非递归:\

PreOrderTraverse(&tree);//先序遍历非递归 cout<

cout<<\中序遍历递归为:\

InTraverse(&tree);//中序遍历递归

山东轻工业学院实验报告（附页）

cout<<\中序遍历非递归:\

InOrderTraverse(&tree);//中序遍历非递归 cout<

cout<<\后序遍历递归为:\

PostTraverse(&tree);//后序遍历递归 cout<<\后序遍历非递归:\

LastOrderTraverse(&tree);//后序遍历非递归 cout<

cout<<\树的深度为:\ H=DepthTree(&tree);

cout<

cout<<\叶子结点个数:\L=LeafsTree(&tree);

cout<

void InitTree(Tree *tree)//初始化树 { }

void CreatTree(Tree *tree)//创建树 {

int n=0,m=0,i=0; tree->lTree=NULL; tree->rTree=NULL; tree->data='0'; cout<<\结点个数：\

cout<

山东轻工业学院实验报告（附页）

if(tree->data=='0') { }

cout<<\节点\是否有左子树（0：没有 1：有）：\cout<<\请输入该节点的数据：\cin>>tree->data;

cin>>n; if(n==1) { Tree *lTree=(Tree*)malloc(sizeof(Tree)); tree->lTree=lTree; lTree->lTree=NULL; lTree->rTree=NULL; lTree->data='0'; CreatTree(tree->lTree);

cout<<\节点\是否有右子树（0：没有 cin>>i; if(i==0); else if(i==1) { Tree *rTree=(Tree*)malloc(sizeof(Tree)); tree->rTree=rTree; rTree->lTree=NULL; rTree->rTree=NULL; rTree->data='0'; CreatTree(tree->rTree);

}

}

else if(n==0)

：有）：\

1