《数据结构》实验报告五:二叉树
一、实验目的
1、掌握二叉树的基本特性
2、掌握二叉树的先序、中序、后序的递归遍历算法
3、理解二叉树的先序、中序、后序的非递归遍历算法
4、通过求二叉树的深度、叶子结点数和层序遍历等算法,理解二叉树的基本特性
二、实验预习
说明以下概念
1、二叉树:
二叉树是n个结点(n>=0)的有限集合。该集合或为空集(n=0);或由一个根节点和两棵互不相交的、分别称为该根节点的左子树的右子树的二叉树构成。(递归定义)
2、递归遍历:
二叉树的递归遍历常见有三种:前序、中序、后序遍历。(这里的前、中、后指的是根结点的访问次序)
前序遍历按照“根结点->左孩子->右孩子”的顺序访问结点;
中序遍历按照“左孩子->根结点->右孩子”的顺序访问结点;
后序遍历按照“左孩子->右孩子->根结点”的顺序访问结点。
其中在访问左孩子和右孩子的时候依然使用对应的前序、中序或后序遍历。
3、非递归遍历:
利用栈实现的非递归遍历,也分为三种:前序、中序、后序遍历。
以中序遍历为例,按照“左孩子->根结点->右孩子”的顺序进行访问。
从一棵二叉树的根节点开始,依次访问该根结点的左孩子、左孩子的左孩子……,并保存一路走过的根节点(依次入栈),直至左子树为空。
左子树为空说明该左孩子遍历完成,接着根节点出栈,并访问出栈的根节点(该根节点为最后经过的根节点),然后借助出栈的根节点进入该根节点的右子树继续进行访问。利用栈后入先出的特点,实现了二叉树的非递归遍历。
4、层序遍历:
从一棵树的根结点开始,按照从上到下、从左到右的顺序依次访问树中的每一个结点。
三、实验内容和要求
1、阅读并运行下面程序,根据输入写出运行结果,并画出二叉树的形态。
#include<stdio.h>
#include<malloc.h>
#define MAX 20
typedef struct BTNode{ /*二叉树结点结构声明*/
char data ; /*节点数据*/
struct BTNode *lchild;
struct BTNode *rchild ; /*孩子指针*/
}*BiTree;
void createBiTree(BiTree *t){ /*先序遍历创建二叉树*/
char s;
BiTree q;
printf("\nplease input data:(exit for #)");
s=getche(); //getche:输入后立即从控制台取字符,不以回车为结束(带回显)
//输入#,说明该树为空
if('#' == s)
{
*t = NULL;
return;
}
//输入非'#':为根结点分配空间
q = (BiTree)malloc(sizeof(struct BTNode));
/*分配失败*/
if( !q )
{
printf("Memory alloc failure!");
exit(0);
}
/*分配成功*/
q->data = s;
*t = q;
createBiTree(&q->lchild); /*递归建立左子树*/
createBiTree(&q->rchild); /*递归建立右子树*/
}
void PreOrder(BiTree p){ /*先序遍历二叉树*/
if( p!= NULL )
{
printf("%c",p->data);
PreOrder(p->lchild);
PreOrder(p->rchild);
}
}
void InOrder(BiTree p){ /*中序遍历二叉树*/
if( p!= NULL )
{
InOrder(p->lchild);
printf("%c",p->data);
InOrder(p->rchild);
}
}
void PostOrder(BiTree p){ /*后序遍历二叉树*/
if( p!= NULL )
{
PostOrder(p->lchild);
PostOrder(p->rchild);
printf("%c",p->data);
}
}
void Preorder_n(BiTree p){ /*先序遍历的非递归算法*/
BiTree stack[MAX]; //准备一个顺序栈存储结点
BiTree q;
int top = 0; //top=0:栈空
int i;
for(i=0;i<MAX;i++) /*初始化栈*/
stack[i] = NULL;
q = p; //设置q指向待遍历的二叉树
while( q != NULL )
{
printf("%c",q->data); //先访问根节点
if(q->rchild != NULL)
stack[top++] = q->rchild;
if(q->lchild != NULL)
q = q->lchild;
//结点的左孩子为空,说明该结点的左子树访问结束,进入下一二叉树(出栈)
else
{
if(top > 0)
q = stack[--top];
else
q = NULL;
}
}
}
void release(BiTree t){ /*释放二叉树空间*/
if(t!=NULL)
{
release(t->lchild);
release(t->rchild);
free(t);
}
}
int main(){
BiTree t = NULL;
createBiTree(&t);
printf("\n\nPreOrder the tree is:");
PreOrder(t);
printf("\n\nInOrder the tree is:");
InOrder(t);
printf("\n\nPostOrder the tree is:");
PostOrder(t);
printf("\n\n先序遍历序列(非递归):");
Preorder_n(t);
release(t);
return 0;
}
- 运行程序:
输入:ABC##DE#G##F###
- 运行结果:
- 二叉树形态:
2、在上题中补充求二叉树中结点总数算法(提示:可在某种遍历过程中统计遍历的结点数),并在主函数中补充相应的调用验证正确性。
算法代码(递归算法):
int Num_of_Nodes(BiTree t){ /*求二叉树t的结点总数,函数返回值即结点总数*/
BiTree q;
q = t;
//二叉树为空,直接返回0
if( !q )
return 0;
//二叉树非空,总结点数 = 1 + 左子树的总结点数 + 左子树的总结点数
int num_l = Num_of_Nodes(q->lchild);
int num_r = Num_of_Nodes(q->rchild);
return (1 + num_l + num_r);
}
主函数补充代码:
int main(){
BiTree t = NULL;
createBiTree(&t);
printf("\n\nPreOrder the tree is:");
PreOrder(t);
printf("\n\nInOrder the tree is:");
InOrder(t);
printf("\n\nPostOrder the tree is:");
PostOrder(t);
printf("\n\n先序遍历序列(非递归):");
Preorder_n(t);
//主函数添加代码
printf("\n\n此二叉树结点总数为:%d",Num_of_Nodes(t));
release(t);
return 0;
}
运行结果:
3、在上题中补充求二叉树中叶子结点总数算法(提示:可在某种遍历过程中统计遍历的叶子结点数),并在主函数中补充相应的调用验证正确性。
算法代码(递归算法):
int Num_of_LeafNodes(BiTree t){ /*求二叉树t的叶子结点总数,函数返回值即叶子结点总数*/
BiTree q;
q = t;
//二叉树为空,直接返回0
if( !q )
return 0;
//结点的左右子树均为空,则该结点为叶子结点
if( !(q->lchild) && !(q->rchild) )
return 1;
//二叉树非空,叶子结点总数 = 左子树的叶子结点总数 + 右子树的叶子结点总数
int num_l = Num_of_LeafNodes(q->lchild);
int num_r = Num_of_LeafNodes(q->rchild);
return (num_l + num_r);
}
主函数补充代码:
int main(){
BiTree t = NULL;
createBiTree(&t);
printf("\n\nPreOrder the tree is:");
PreOrder(t);
printf("\n\nInOrder the tree is:");
InOrder(t);
printf("\n\nPostOrder the tree is:");
PostOrder(t);
printf("\n\n先序遍历序列(非递归):");
Preorder_n(t);
//主函数添加代码
printf("\n\n此二叉树结点总数为:%d",Num_of_Nodes(t));
printf("\n\n此二叉树叶子结点总数为:%d",Num_of_LeafNodes(t));
release(t);
return 0;
}
运行结果:
4、在上题中补充求二叉树深度算法,并在主函数中补充相应的调用验证正确性。
算法代码(递归算法):
int Depth_of_BiTree(BiTree t){ /*求二叉树t的深度,函数返回值即二叉树深度*/
BiTree q;
q = t;
//二叉树为空,直接返回0
if( !q )
return 0;
//二叉树非空,深度 = 1 + Max(左子树深度,右子树深度)
int dep_l = Depth_of_BiTree(q->lchild);
int dep_r = Depth_of_BiTree(q->rchild);
int dep = 1 + ( (dep_l > dep_r)?dep_l:dep_r );
return dep;
}
主函数补充代码:
int main(){
BiTree t = NULL;
createBiTree(&t);
printf("\n\nPreOrder the tree is:");
PreOrder(t);
printf("\n\nInOrder the tree is:");
InOrder(t);
printf("\n\nPostOrder the tree is:");
PostOrder(t);
printf("\n\n先序遍历序列(非递归):");
Preorder_n(t);
//主函数添加代码
printf("\n\n此二叉树结点总数为:%d",Num_of_Nodes(t));
printf("\n\n此二叉树叶子结点总数为:%d",Num_of_LeafNodes(t));
printf("\n\n此二叉树深度为:%d",Depth_of_BiTree(t));
release(t);
return 0;
}
运行结果:
5、补充二叉树中序非递归遍历算法,并给出运行结果。
算法代码:
void Inorder_n(BiTree p){ /*中序遍历的非递归算法*/
BiTree stack[MAX]; //准备一个顺序栈存储结点
BiTree q;
int top = 0; //top = 0:栈空
int i;
for(i=0;i<MAX;i++) /*初始化栈*/
stack[i] = NULL;
q = p; //q指向遍历的二叉树
while( q || top > 0 )
{
//结点非空
if( q )
{
stack[top++] = q; //根节点入栈
q = q->lchild; //进入左子树
}
//结点为空,栈非空
else
{
q = stack[--top]; //根结点出栈
printf("%c",q->data); //访问根节点
q = q->rchild; //进入右子树
}
}
}
主函数补充代码:
int main(){
BiTree t = NULL;
createBiTree(&t);
printf("\n\nPreOrder the tree is:");
PreOrder(t);
printf("\n\nInOrder the tree is:");
InOrder(t);
printf("\n\nPostOrder the tree is:");
PostOrder(t);
printf("\n\n先序遍历序列(非递归):");
Preorder_n(t);
//主函数添加代码
printf("\n\n此二叉树结点总数为:%d",Num_of_Nodes(t));
printf("\n\n此二叉树叶子结点总数为:%d",Num_of_LeafNodes(t));
printf("\n\n此二叉树深度为:%d",Depth_of_BiTree(t));
printf("\n\n中序遍历序列(非递归):");
Inorder_n(t);
release(t);
return 0;
}
运行结果:
更多推荐
所有评论(0)