实验报告：
二叉树
题目：
建立一棵二叉树，数据以字符串形式从键盘输入，在此二叉树上完成：
（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);
}