北 京 林 业 大 学
12学年—13学年第1学期数据结构实验报告书
专 业：自动化班 级：11－1
姓 名：宁友菊学 号：111044120
实验地点：B2机房任课教师：孟伟
实验题目：二叉树的基本操作
实验环境：Visual C++
实验目的：
1．掌握二叉树的定义；
2．掌握二叉树的基本操作，如建立、前序遍历、中序遍历和后序遍历、结点个数的统计等；
实验内容：
用递归的方法实现以下算法：
1．以二叉链表表示二叉树，建立一棵二叉树；
2．输出二叉树的前序遍历结果；
3．输出二叉树的中序遍历结果；
4．输出二叉树的后序遍历结果；
5．统计二叉树的叶结点个数；
6．统计二叉树的结点个数；
7．计算二叉树的深度。
8．交换二叉树每个结点的左孩子和右孩子；
实现方法、实验结果及结论分析等：
（一）实现方法
1. 所用数据结构的定义及其相关说明（相关结构体或类的定义及其含义）
?实验采用二叉树的数据结构，以二叉链表存储，主程序中采用switch函数调用各个子程序以实现各个功能。0结束程序，输入错误时返回主函数重新输入。
2. 自定义函数的名称及其功能说明
（1）void CreateBiTree 以二叉链表表示二叉树，建立一棵二叉树；
（2）void PreOrderTraverse 输出二叉树的前序遍历结果；
（3）void InOrderTraverse 输出二叉树的中序遍历结果；
（4）void PostOrderTraverse 输出二叉树的后序遍历结果；
（5）int LeafNodeCount 统计二叉树的叶结点个数；
（6）int Node Count 统计二叉树的结点个数；
（7）int Depth 计算二叉树的深度。
（8）int Swap 交换二叉树每个结点的左孩子和右孩子；
3. 主要功能算法void PreOrderTraverse的时间复杂度
O（n）=O（n1)×O(n2)×O(n3)×O(n4)×O(n5)×O(n6)×O(n7)xO(n8)
O（n1)——void CreateBiTree函数算法时间复杂度O(n)
O(n2)——void PreOrderTraverse函数算法时间复杂度O(n)
O(n3)——void InOrderTraverse函数算法时间复杂度O(n)
O(n4)——void PostOrderTraverse 函数算法时间复杂度O(n)
O(n5)——int LeafNodeCount函数算法时间复杂度O(n)
O(n6)——int NodeCount函数算法时间复杂度O(n)
O(n7)——int Depth函数算法时间复杂度O(n)
O(n8)——int Swap 函数算法时间复杂度O(n)
4. 实验流程图
（二）实验结果
1、选择操作一：
2、创建二叉树
3、前序遍历结果
4、中序遍历结果
5、后序遍历结果
6、总结点数
7、叶节点数
8、二叉树深度
9、对换左右孩子
10、退出
11、输入错误检测
（三）结论分析
1. 问题与解决方法
在编写程序时，遇到了一个程序保存后编译正确却运行不了，之后请教了我们班的同学，才知道是第一个函数出了问题，改了之后就好了。
2. 收获和体会
做程序编写时，必须要细心，有时候问题出现了，可能会一直查不出来。自己也不容易发现。在编写这个程序时，我就出现了这个问题，之后一定要尽量避免此类问题出现。
3. 尚存在的问题
这几个子函数的名称都是边看着书边写的，还没有完全脱离书本，真正变成自己建的东西。还要加强记忆。
第二篇：数据结构二叉树操作实验报告
数据结构实验报告
指导教师XX实验时间：2010年11月1日
学院计算机学院专业信息安全
班级XXXXXX学号XXXXX姓名XX实验室S331
实验题目：二叉树操作
实验要求：
采用二叉树链表作为存储结构，完成二叉树的建立，先序、中序和后序以及按层次遍历的操作，求所有叶子及结点总数的操作。
示例程序：
#include"stdio.h"
#include"string.h"
#define Max 20 //结点的最大个数
typedef struct node{
char data;
struct node *lchild,*rchild;
}BinTNode; //自定义二叉树的结点类型
typedef BinTNode *BinTree; //定义二叉树的指针
int NodeNum,leaf; //NodeNum为结点数，leaf为叶子数
//==========基于先序遍历算法创建二叉树==============
//=====要求输入先序序列，其中加入虚结点“#”以示空指针的位置==========
BinTree CreatBinTree(void)
{
BinTree T;
char ch;
if((ch=getchar())=='#')
return(NULL); //读入#，返回空指针
else{
T=(BinTNode *)malloc(sizeof(BinTNode)); 生成结点
T->data=ch;
T->lchild=CreatBinTree(); //构造左子树
T->rchild=CreatBinTree(); //构造右子树
return(T);
}
}
//========NLR 先序遍历=============
void Preorder(BinTree T)
{
if(T) {
printf("%c",T->data); //访问结点
Preorder(T->lchild); //先序遍历左子树
Preorder(T->rchild); //先序遍历右子树
}
}
//========LNR 中序遍历===============
//==========LRN 后序遍历============
//=====采用后序遍历求二叉树的深度、结点数及叶子数的递归算法========
int TreeDepth(BinTree T)
{
int hl,hr,max;
if(T){
hl=TreeDepth(T->lchild); //求左深度
hr=TreeDepth(T->rchild); //求右深度
max=hl>hr? hl:hr; //取左右深度的最大值
NodeNum=NodeNum+1; //求结点数
if(hl==0&&hr==0) leaf=leaf+1; //若左右深度为0，即为叶子。
return(max+1);
}
else return(0);
}
//====利用“先进先出”（FIFO）队列，按层次遍历二叉树==========
void Levelorder(BinTree T)
{
int front=0,rear=1;
BinTNode *cq[Max],*p; //定义结点的指针数组cq
cq[1]=T; //根入队
while(front!=rear)
{
front=(front+1)%NodeNum;
p=cq[front]; //出队
printf("%c",p->data); //出队，输出结点的值
if(p->lchild!=NULL){
rear=(rear+1)%NodeNum;
cq[rear]=p->lchild; //左子树入队
}
if(p->rchild!=NULL){
rear=(rear+1)%NodeNum;
cq[rear]=p->rchild; //右子树入队
}
}
}
//==========主函数=================
void main()
{
BinTree root;
int i,depth;
printf("\n");
printf("Creat Bin_Tree； Input preorder:"); //输入完全二叉树的先序序列，
// 用#代表虚结点，如ABD###CE##F##
root=CreatBinTree(); //创建二叉树，返回根结点
do { //从菜单中选择遍历方式，输入序号。
printf("\t********** select ************\n");
printf("\t1: Preorder Traversal\n");
printf("\t2: Iorder Traversal\n");
printf("\t3: Postorder traversal\n");
printf("\t4: PostTreeDepth,Node number,Leaf number\n");
printf("\t5: Level Depth\n"); //按层次遍历之前，先选择4，求出该树的结点数。
printf("\t0: Exit\n");
printf("\t*******************************\n");
scanf("%d",&i); //输入菜单序号（0-5）
switch (i){
case 1: printf("Print Bin_tree Preorder: ");
Preorder(root); //先序遍历
break;
case 2: printf("Print Bin_Tree Inorder: ");
Inorder(root); //中序遍历
break;
case 3: printf("Print Bin_Tree Postorder: ");
Postorder(root); //后序遍历
break;
case 4: depth=TreeDepth(root); //求树的深度及叶子数
printf("BinTree Depth=%d BinTree Node number=%d",depth,NodeNum);
printf(" BinTree Leaf number=%d",leaf);
break;
case 5: printf("LevePrint Bin_Tree: ");
Levelorder(root); //按层次遍历
break;
default: exit(1);
}
printf("\n");
} while(i!=0);
}
实验内容及步骤：
1、分析、理解程序。
2、添加中序和后序遍历算法.
3、调试程序，设计一棵二叉树，输入完全二叉树的先序序列，用#代表虚结点（空指针），如ABD###CE##F##，建立二叉树，求出先序、中序和后序以及按层次遍历序列，求所有叶子及结点总数。
4、画出所设计的二叉树，以后序遍历算法为例，画出执行踪迹示意图。给出实验结果。
5、给出实验结果。
改正后的完整程序：
#include"stdio.h"
#include"string.h"
#include
#include
#define Max 20 //结点的最大个数
typedef struct node{
char data;
struct node *lchild,*rchild;
}BinTNode; //自定义二叉树的结点类型
typedef BinTNode *BinTree; //定义二叉树的指针
int NodeNum,leaf; //NodeNum为结点数，leaf为叶子数
//==========基于先序遍历算法创建二叉树==============
//=====要求输入先序序列，其中加入虚结点"#"以示空指针的位置==========
BinTree CreatBinTree(void)
{
BinTree T;
char ch;
if((ch=getchar())=='#')
return(NULL); //读入#，返回空指针
else{
T=(BinTNode *)malloc(sizeof(BinTNode)); // 生成结点
T->data=ch;
T->lchild=CreatBinTree(); //构造左子树
T->rchild=CreatBinTree(); //构造右子树
return(T);
}
}
//========NLR 先序遍历=============
void Preorder(BinTree T)
{
if(T) {
printf("%c",T->data); //访问结点
Preorder(T->lchild); //先序遍历左子树
Preorder(T->rchild); //先序遍历右子树
}
}
//========LNR 中序遍历===============
void Inorder(BinTree T)
{
if(T) {
Inorder(T->lchild); //先序遍历左子树
printf("%c",T->data); //访问结点
Inorder(T->rchild); //先序遍历右子树
}
}
/*void Inorder(BinTree T)
while(p||!StackEmpty(BinTree T)){
if(T) {Push (BinTree T,T);T=T->lchild;}//根指针进栈，遍历左子树
else{ //根指针退栈，访问根节点，遍历右子树
Pop(BinTree T,t);
if(!Visit(T->data))
return ERROR;
T=T-rchild;
}//else
}//while
return OK;
}
*/
//==========LRN 后序遍历============
void Postorder(BinTree T)
{
if(T) {
Postorder(T->lchild); //先序遍历左子树
Postorder(T->rchild); //先序遍历右子树
printf("%c",T->data); //访问结点
}
}
//=====采用后序遍历求二叉树的深度、结点数及叶子数的递归算法========
int TreeDepth(BinTree T)
{
int hl,hr,max;
if(T){
hl=TreeDepth(T->lchild); //求左深度
hr=TreeDepth(T->rchild); //求右深度
max=hl>hr? hl:hr; //取左右深度的最大值
NodeNum=NodeNum+1; //求结点数
if(hl==0&&hr==0) leaf=leaf+1; //若左右深度为0，即为叶子。
return(max+1);
}
else return(0);
}
//====利用"先进先出"（FIFO）队列，按层次遍历二叉树==========
void Levelorder(BinTree T)
{
int front=0,rear=1;
BinTNode *cq[Max],*p; //定义结点的指针数组cq
cq[1]=T; //根入队
while(front!=rear)
{
front=(front+1)%NodeNum;
p=cq[front]; //出队
printf("%c",p->data); //出队，输出结点的值
if(p->lchild!=NULL){
rear=(rear+1)%NodeNum;
cq[rear]=p->lchild; //左子树入队
}
if(p->rchild!=NULL){
rear=(rear+1)%NodeNum;
cq[rear]=p->rchild; //右子树入队
}
}
}
//==========主函数=================
void main()
{
BinTree root;
int i,depth;
printf("\n");
printf("Creat Bin_Tree； Input preorder:"); //输入完全二叉树的先序序列，
// 用#代表虚结点，如ABD###CE##F##
root=CreatBinTree(); //创建二叉树，返回根结点
do { //从菜单中选择遍历方式，输入序号。
printf("\t********** select ************\n");
printf("\t1: Preorder Traversal\n");
printf("\t2: Iorder Traversal\n");
printf("\t3: Postorder traversal\n");
printf("\t4: PostTreeDepth,Node number,Leaf number\n");
printf("\t5: Level Depth\n"); //按层次遍历之前，先选择4，求出该树的结点数。
printf("\t0: Exit\n");
printf("\t*******************************\n");
scanf("%d",&i); //输入菜单序号（0-5）
switch (i){
case 1: printf("Print Bin_tree Preorder: ");
Preorder(root); //先序遍历
break;
case 2: printf("Print Bin_Tree Inorder: ");
Inorder(root); //中序遍历
break;
case 3: printf("Print Bin_Tree Postorder: ");
Postorder(root); //后序遍历
break;
case 4: depth=TreeDepth(root); //求树的深度及叶子数
printf("BinTree Depth=%d BinTree Node number=%d",depth,NodeNum);
printf(" BinTree Leaf number=%d",leaf);
break;
case 5: printf("LevePrint Bin_Tree: ");
Levelorder(root); //按层次遍历
break;
default: exit(1);
}
printf("\n");
} while(i!=0);
}
程序结果：
二叉树及后序遍历（虚线路径）
心得体会：
通过本次实验，我熟练了二叉树先序、中序和后序三种遍历，不仅是程序的编写，还有二叉树的绘制。