数据结构之二叉树编程实验报告
实验报告：
二叉树
题目：
建立一棵二叉树，数据以字符串形式从键盘输入，在此二叉树上完成：
（1） 前序、中序、后序遍历
（2） 求出叶子数
（3） 求树高
（4） 左右子树交换，输出交换后的前序、中序遍历序列
分析：
建树：
输入的字符串序列为带有空节点的前序遍历序列（空节点用*表示）。
①：前序，中序，后序遍历：递归遍历
②：求叶子数：
当一个节点的左右孩子都是NULL时，此节点即为叶子节点。
③：求树高
当前节点的树高等于其左右孩子树高大的加1。
④：左右子树交换：
对于每个节点，将其左右孩子交换，再递归对其左右子树交换。
测试结果：
附：源码
#include <iostream>
#include <stdlib.h>
using namespace std;
struct Bintree
{
char data;
Bintree* lchild;
Bintree* rchild;
};
Bintree *head;
int sp;
/* 已知一棵二叉树的前序序列，建立这棵树 */
void CreateTree(Bintree *&p,char a[])
{
Bintree *temp;
if(a[sp]!=0)
{
if(a[sp]=='*')
{
p=NULL;
sp++;
return ;
}
p=new Bintree;
p->data=a[sp++];
CreateTree(p->lchild,a);
CreateTree(p->rchild,a);
}
else p=NULL;
}
/* 求一棵树的高度 */
int Depth(Bintree *&t)
{
int lh , rh ;
if( t == NULL )
{
return 0 ;
}
else
{
lh = Depth( t->lchild ) ;
rh = Depth( t->rchild ) ;
return ( lh > rh ? lh : rh ) + 1 ;
}
}
/* 将二叉树的左右子树互换 */
void Exchange1(Bintree *&t)
{
Bintree *temp;
if(t)
{
Exchange1(t->lchild);
Exchange1(t->rchild);
temp=t->lchild;
t->lchild=t->rchild;
t->rchild=temp;
}
}
/* 按照前序递归遍历二叉树 */
void Preorder1(Bintree *&t)
{
if(t!=NULL)
{
printf("%c",t->data);
Preorder1(t->lchild);
Preorder1(t->rchild);
}
}
/* 按照中序递归遍历二叉树 */
void Inorder1(Bintree *&t)
{
if(t!=NULL)
{
Inorder1(t->lchild);
printf("%c",t->data);
Inorder1(t->rchild);
}
}
/* 按照后序递归遍历二叉树 */
void Posorder1(Bintree *&t)
{
if(t!=NULL)
{
Posorder1(t->lchild);
Posorder1(t->rchild);
printf("%c",t->data);
}
}
/* 递归法求叶子结点个数 */
int Leaves_Num1(Bintree *&t)
{
if(t)
{
if(t->lchild==NULL&&t->rchild==NULL)
{
return 1;
}
return Leaves_Num1(t->lchild)+Leaves_Num1(t->rchild);
}
return 0;
}
/*******************************************/
int main ()
{
char a[100];
memset(a,0,sizeof(a));
cout<<"输入带有空节点的前序遍历序列（空节点用*表示）"<<endl;
cin>>a;
sp=0;
CreateTree(head,a);
cout<<"前序遍历："<<endl;
Preorder1(head);
cout<<endl;
cout<<"中序遍历："<<endl;
Inorder1(head);
cout<<endl;
cout<<"后序遍历："<<endl;
Posorder1(head);
cout<<endl;
cout<<"叶子数："<<Leaves_Num1(head)<<endl;
cout<<"树高："<<Depth(head)<<endl;
cout<<"左右子树交换后"<<endl;
Exchange1(head);
cout<<"前序遍历："<<endl;
Preorder1(head);
cout<<endl;
cout<<"中序遍历："<<endl;
Inorder1(head);
cout<<endl;
cout<<"后序遍历："<<endl;
Posorder1(head);
cout<<endl;
return 0;
}
第二篇：数据结构-二叉树实验报告
数据结构实验报告
课程 数据结构 _ 实验名称 二叉树实验
院系 电信学院 专业班级 计科10-4
姓名 学 号
一、实验构思
首先构造二叉树的存储结构，用data存储当前节点的值，分别用*lchild，*rchild表示该节点的左右孩子。然后应用BiTree Create函数，根据用户的输入构造二叉树，当输入#时表示没有孩子。采用递归的思想构造Preorder，Inorder，Postorder函数，分别实现二叉树的先序，中序，和后序的遍历。然后编写了Sumleaf，Depth函数，来求叶子节点的数目和二叉树的深度。
二、实验设计
二叉树的存储结构：typedef struct BiTNode
{
char data;
struct BiTNode *lchild；
struct BiTNode *rchild;
}BiTNode,*BiTree;
子程序模块：
BiTree Create(BiTree T) 创建二叉树
{
char ch;
ch=getchar();
if(ch=='#')
T=NULL;
else
{
if(!(T=(BiTNode *)malloc(sizeof(BiTNode))))
printf("Error!");
T->data=ch;
T->lchild=Create(T->lchild);
T->rchild=Create(T->rchild);
}
return T;
}
void Preorder(BiTree T) 先序遍历二叉树
{
if(T)
{
printf("%c",T->data);
Preorder(T->lchild);
Preorder(T->rchild);
}
}
int Sumleaf(BiTree T) 求二叉树T的叶子节点数目
{
int sum=0,m,n;
if(T)
{
if((!T->lchild)&&(!T->rchild))
sum++;
m=Sumleaf(T->lchild);
sum+=m;
n=Sumleaf(T->rchild);
sum+=n;
}
return sum;
}
void Inorder(BiTree T) 中序遍历二叉树
{
if(T)
{
Inorder(T->lchild);
printf("%c",T->data);
Inorder(T->rchild);
}
}
void Postorder(BiTree T) 后序遍历二叉树
{
if(T)
{
Postorder(T->lchild);
Postorder(T->rchild);
printf("%c",T->data);
}
}
int Depth(BiTree T) 求二叉树的深度
{
int dep=0,depl,depr;
if(!T)
dep=0;
else{
depl=Depth(T->lchild);
depr=Depth(T->rchild);
dep=1+(depl>depr?depl:depr);
}
return dep;
}
主程序模块：
int main()
{
BiTree T = 0;
int sum,dep;
printf("请输入你需要建立的二叉树\n");
printf("\n例如输入序列ABC##DE#G##F###（其中的#表示空）\n并且输入过程中不要加回车\n输入完之后可以按回车退出\n");
T=Create(T);
printf("先序遍历的结果是：\n");
Preorder(T);
printf("\n");
printf("中序遍历的结果是：\n");
Inorder(T);
printf("\n");
printf("后序遍历的结果是：\n");
Postorder(T);
printf("\n");
printf("统计的叶子数：\n");
sum=Sumleaf(T);
printf("%d",sum);
printf("\n统计树的深度：\n");
dep=Depth(T);
printf("\n%d\n",dep);
}
三、实现描述
各函数原型说明：BiTree Create(BiTree T)//构造二叉树T
void Preorder(BiTree T)//对二叉树T进行先序遍历
void Inorder(BiTree T)//对二叉树T进行中序遍历
void Postorder(BiTree T)//对二叉树T进行后序遍历
int Sumleaf(BiTree T)//求二叉树T的叶子节点数目
int Depth(BiTree T)//求二叉树T的深度
函数间的调用关系：int main()
{
调用Create函数，构造二叉树T
调用Preorder函数，对二叉树进行先序遍历
调用Inorder函数，对二叉树进行中序遍历
调用Postorder函数，对二叉树进行后序遍历
调用Sumleaf函数，统计二叉树的叶子节点数
调用Depth函数，统计二叉树的深度
}
时间复杂度分析：在对二叉树进行遍历的过程中，用到了递归的思想，对于二叉树中的每一个结点，从头到尾只访问过一次，所以，对于含有N个结点的二叉树，其遍历的时间复杂度为o(n)。
四、源程序代码
#include <stdio.h>
#include <string.h>
#include<malloc.h>
#define NULL 0
typedef struct BiTNode
{
char data;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
BiTree Create(BiTree T)
{
char ch[20];
int i=0;
for(i=0;i<20&&getchar()!='\0';i++)
ch[i]=getchar();
for(i=0;ch[i]!='\0';i++)
{
if(ch[i]=='#')
{
T=NULL;
}
else if(!(T=(BiTNode *)malloc(sizeof(BiTNode))))
printf("Error!");
else
{
T->data=ch[i];
T->lchild=Create(T->lchild);
T->rchild=Create(T->rchild);
}
}
return T;
}
void Preorder(BiTree T)
{
if(T)
{
printf("%c",T->data);
Preorder(T->lchild);
Preorder(T->rchild);
}
}
int Sumleaf(BiTree T)
{
int sum=0,m,n;
if(T)
{
if((!T->lchild)&&(!T->rchild))
sum++;
m=Sumleaf(T->lchild);
sum+=m;
n=Sumleaf(T->rchild);
sum+=n;
}
return sum;
}
void Inorder(BiTree T)
{
if(T)
{
Inorder(T->lchild);
printf("%c",T->data);
Inorder(T->rchild);
}
}
void Postorder(BiTree T)
{
if(T)
{
Postorder(T->lchild);
Postorder(T->rchild);
printf("%c",T->data);
}
}
int Depth(BiTree T)
{
int dep=0,depl,depr;
if(!T)
dep=0;
else{
depl=Depth(T->lchild);
depr=Depth(T->rchild);
dep=1+(depl>depr?depl:depr);
}
return dep;
}
int main()
{
BiTree T = 0;
int sum,dep;
printf("请输入你需要建立的二叉树\n");
printf("输入序列ABC##DE#G##F###（其中的#表示空）\n");
T=Create(T);
printf("先序遍历的结果是：\n");
Preorder(T);
printf("\n");
printf("中序遍历的结果是：\n");
Inorder(T);
printf("\n");
printf("后序遍历的结果是：\n");
Postorder(T);
printf("\n");
printf("统计的叶子数：\n");
sum=Sumleaf(T);
printf("%d",sum);
printf("\n统计树的深度：\n");
dep=Depth(T);
printf("\n%d\n",dep);
}
-
数据结构二叉树实验报告
实验三二叉树的遍历一实验目的熟悉二叉树的结点类型和二叉树的基本操作掌握二叉树的前序中序和后序遍历的算法3加深对二叉树的理解逐步培养…
-
数据结构C二叉树实验报告
北京林业大学12学年13学年第1学期数据结构实验报告书专业自动化班级111姓名宁友菊学号111044120实验地点B2机房任课教师…
- 数据结构树和二叉树实验报告
-
数据结构二叉树实验报告(附代码)
一实验构思Conceive10本部分应包括描述实验实现的基本思路包括所用到的离散数学工程数学程序设计算法等相关知识首先构造二叉树的…
-
数据结构二叉树操作实验报告
实验报告指导教师XX实验时间20xx年11月1日学院计算机学院专业信息安全班级XXXXXX学号XXXXX姓名XX实验室S331实验…
-
数据结构二叉树实验报告
实验三二叉树的遍历一实验目的熟悉二叉树的结点类型和二叉树的基本操作掌握二叉树的前序中序和后序遍历的算法3加深对二叉树的理解逐步培养…
-
数据结构_实验9_二叉树遍历的应用
实验报告实验课程数据结构实验项目实验九二叉树遍历的应用实验地点指导教师班级学生姓名金轶洲学号09020xx03教师评分日期浙江传媒…
-
中南民族大学信管二叉树_数据结构实验报告
中南民族大学管理学院学生实验报告实验项目二叉树的建立与遍历课程名称数据结构年级20xx专业信息管理与信息系统指导教师实验地点管理学…
-
数据结构实验报告 二叉树
实验报告实验目的1掌握树及二叉树的基本概念2掌握二叉树的存储结构3掌握二叉树的遍历实验内容算术表达式与二叉树之间存在着对应关系编写…
-
数据结构C二叉树实验报告
北京林业大学12学年13学年第1学期数据结构实验报告书专业自动化班级111姓名宁友菊学号111044120实验地点B2机房任课教师…