实验报告
一、实验目的
1、熟悉二叉树树的基本操作。
2、掌握二叉树的实现以及实际应用。
3、加深二叉树的理解，逐步培养解决实际问题的编程能力。
二、实验环境
1台WINDOWS环境的PC机，装有Visual C++ 6.0。
三、实验内容
【问题描述】
现需要编写一套二叉树的操作函数，以便用户能够方便的利用这些函数来实现自己的应用。其中操作函数包括：
1> 创建二叉树CreateBTNode(*b,*str)：根据二叉树括号表示法的字符串*str生成对应的链式存储结构。
2> 输出二叉树DispBTNode(*b)：以括号表示法输出一棵二叉树。
3> 查找结点FindNode(*b,x)：在二叉树b中寻找data域值为x的结点,并返回指向该结点的指针。
4> 求高度BTNodeDepth(*b)：求二叉树b的高度。若二叉树为空,则其高度为0；否则,其高度等于左子树与右子树中的最大高度加l。
5> 求二叉树的结点个数NodesCount(BTNode *b)
6> 先序遍历的递归算法：void PreOrder(BTNode *b)
7> 中序遍历的递归算法：void InOrder(BTNode *b)
8> 后序遍历递归算法：void PostOrder(BTNode *b)
9> 层次遍历算法void LevelOrder(BTNode *b)
【基本要求】
实现以上9个函数。
主函数中实现以下功能：
创建下图中的树b
输出二叉树b
找到’H’节点，输出其左右孩子值
输出b的高度
输出b的节点个数
输出b的四种遍历顺序
上图转化为二叉树括号表示法为A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))
程序:
#include <stdio.h>
#include <malloc.h>
#define MaxSize 100
typedef char ElemType;
typedef struct node
{
ElemType data; /*数据元素*/
struct node *lchild; /*指向左孩子*/
struct node *rchild; /*指向右孩子*/
} BTNode;
void CreateBTNode(BTNode *&b,char *str);//创建
BTNode *FindNode(BTNode *b,ElemType x);//查找节点
int BTNodeHeight(BTNode *b);//求高度
void DispBTNode(BTNode *b);//输出
int NodesCount(BTNode *b);//二叉树的结点个数
void PreOrder(BTNode *b);//先序遍历递归
void InOrder(BTNode *b);//中序遍历递归
void PostOrder(BTNode *b);//后序遍历递归
void LevelOrder(BTNode *b);//层次遍历
//创建
void CreateBTNode(BTNode *&b,char *str){
BTNode *St[MaxSize],*p=NULL;
int top=-1,k,j=0;
char ch;
b=NULL;
ch=str[j];
while(ch!='\0'){
switch(ch){
case '(':top++;St[top]=p;k=1;break;
case ')':top--;break;
case ',':k=2;break;
default:p=(BTNode *)malloc(sizeof(BTNode));
p->data=ch;p->lchild=p->rchild=NULL;
if(b==NULL)
b=p;
else{
switch(k){
case 1:St[top]->lchild=p;break;
case 2:St[top]->rchild=p;break;
}
}
}
j++;
ch=str[j];
}
}
//输出
void DispBTNode(BTNode *b){
if(b!=NULL){
printf("%c",b->data);
if(b->lchild!=NULL||b->rchild!=NULL){
printf("(");
DispBTNode(b->lchild);
if(b->rchild!=NULL)
printf(",");
DispBTNode(b->rchild);
printf(")");
}
}
}
//查找节点
BTNode *FindNode(BTNode *b,ElemType x){
BTNode *p;
if(b==NULL)
return b;
else if(b->data==x)
return b;
else{
p=FindNode(b->lchild,x);
if(p!=NULL)
return p;
else
return FindNode(b->rchild,x);
}
}
//求高度
int BTNodeHeight(BTNode *b){
int lchildh,rchildh;
if(b==NULL)
return (0);
else{
lchildh=BTNodeHeight(b->lchild);
rchildh=BTNodeHeight(b->rchild);
return(lchildh>rchildh)?(lchildh+1):(rchildh+1);
}
}
//二叉树的结点个数
int NodesCount(BTNode *b){
if(b==NULL)
return 0;
else
return NodesCount(b->lchild)+NodesCount(b->rchild)+1;
}
//先序遍历递归
void PreOrder(BTNode *b){
if(b!=NULL){
printf("%c",b->data);
PreOrder(b->lchild);
PreOrder(b->rchild);
}
}
//中序遍历递归
void InOrder(BTNode *b){
if(b!=NULL){
InOrder(b->lchild);
printf("%c",b->data);
InOrder(b->rchild);
}
}
//后序遍历递归
void PostOrder(BTNode *b){
if(b!=NULL){
PostOrder(b->lchild);
PostOrder(b->rchild);
printf("%c",b->data);
}
}
//层次遍历
void LevelOrder(BTNode *b){
BTNode *p;
BTNode *qu[MaxSize];
int front,rear;
front=rear=-1;
rear++;
qu[rear]=b;
while(front!=rear){
front=(front+1)%MaxSize;
p=qu[front];
printf("%c",p->data);
if(p->lchild!=NULL){
rear=(rear+1)%MaxSize;
qu[rear]=p->lchild;
}
if(p->rchild!=NULL){
rear=(rear+1)%MaxSize;
qu[rear]=p->rchild;
}
}
}
void main()
{
BTNode *b,*p,*lp,*rp;
char str[]="A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))";//根据树形图改写成的
//二叉树括号表示法的字符串*str
//char str[100];scanf("%s",&str);//自行输入括号表示的二叉树
CreateBTNode(b,str); //创建树b
printf("\n");
printf("输出二叉树:");//输出二叉树b
DispBTNode(b);
printf("\n");
printf("'H'结点:");//找到'H'节点，输出其左右孩子值
p=FindNode(b,'H');
printf("\n");
if (p!=NULL){
printf("左孩子节点的值");
printf("%c",p->lchild->data);printf("\n");
printf("右孩子节点的值");
printf("%c",p->rchild->data);printf("\n");
//此处输出p的左右孩子节点的值
}
printf("\n");
printf("二叉树b的深度:%d\n",BTNodeHeight(b));//输出b的高度
printf("二叉树b的结点个数:%d\n",NodesCount(b));//输出b的节点个数
printf("\n");
printf(" 先序遍历序列:\n");//输出b的四种遍历顺序
printf(" 算法:");PreOrder(b);printf("\n");
printf(" 中序遍历序列:\n");
printf(" 算法:");InOrder(b);printf("\n");
printf(" 后序遍历序列:\n");
printf(" 算法:");PostOrder(b);printf("\n");
printf(" 层次遍历序列:\n");
printf(" 算法:");LevelOrder(b); printf("\n");
}
四、实验心得与小结
通过实验，我熟悉二叉树树的基本操作，掌握二叉树的实现以及实际应用。加深了对二叉树的理解，逐步培养解决实际问题的编程能力以及进一步了解了二叉树图转化为括号表示法。递归的使用，要注意，初始时的状态以及如何使用递归，注意普遍性，思考时从普通的开始。通过这次上机操作，让我明白书本上的程序一定要自己去调试，这样才能将书本程序与老师讲的内容融会贯通，达到温故而知新。
五、指导教师评议
成绩评定： 指导教师签名：
第二篇：二叉树基本操作+数据结构+实验报告
中南大学
数据结构实验报告
题 目 二叉树基本操作
学生姓名
联系电话
指导老师
专业班级
完成时间 20##年11月25 日
目 录
一、 系统功能介绍…………………………………2
二、 需求分析………………………………………2
三、 概要设计………………………………………2
四、 详细设计………………………………………5
五、 调试分析………………………………………8
六、 使用说明………………………………………8
七、 测试结果………………………………………9
八、 心得体会………………………………………10
九、 附录（程序代码）……………………………11
一、系统功能介绍
该程序是用C-Free编写的，主要功能是实现二叉树的定义和基本操作，包括定义二叉树的结构类型以及各个操作的具体函数的定义和主函数的定义。
各操作主要包括：初始化二叉树、按先序次序建立二叉树、检查二叉树是否为空、前序、中序、后序遍历树的方式、求树的深度、求树的结点数目、清空二叉树等九个对树的操作。
二、需求分析
本程序由C-free工具编写完成了初始化，建立二叉树，检查树空与否，用前序、中序、后序遍历二叉树，求树的深度，求树的结点数目，清空二叉树等功能。
1）输出的形式和输出值的范围：在选择操作中，都以整型（数字）选择操作，插入和输出的数值都是char类型的字符；
2）输出的形式：在每次操作后，都会提示操作是否成功或者操作的结果；
3）程序达到的功能：完成初始化、检查是否为空、请空、遍历、求树的深度、求树的结点数目等功能；
4)测试数据设计：
A,按先序次序建立二叉树。依次输入a,b,c,d,e,f,g.建立二叉树。
B,分别按先序，中序和后序遍历输出二叉树中的结点元素。
C,求树的高度和结点数。
三、概要分析
为了实现上述功能，定义二叉树的抽象数据类型。
ADT BinTree{
数据对象D:D是具有相同特性的数据元素的集合。
数据关系R:
若D=￠，称BinTree为空二叉树
若D≠￠,则R={H},H是如下的二元关系；
（1） 在D中存在唯一的称为根的数据元素root,它在关系H下无前驱；
（2） 若D-{root}≠￠，则存在D-{root}={D1,Dr},且D1∩Dr=￠；
（3） 若D≠￠，则中存在唯一的元素x1,<root,x1>∈H,，且存在D1上的关系H1H;若则中存在唯一的元素且存在上的饿关系
（4） 是一棵符合本定义的二叉树，称为根的左子树，是一棵符合本定义的二叉树，称为根的右子树。
基本操作 P：
BinTree BinTreeInit()
{
操作结果：构造空的二叉树
初始条件：给出二叉树的定义
}
BinTree BinTreeCreat(BinTree &BT)
{
操作结果：用先序序列创建一个二叉树
初始条件：构造了空的二叉树
}
int BinTreeEmpty()
{
操作结果：返回0或1，即树的空与否
初始条件：二叉树存在
}
void PreBinTraverse(BinTree BT)
{
操作结果：按先序序列遍历输出二叉树
初始条件：二叉树存在
}
void InBinTraverse(BinTree BT)
{
操作结果：按中序序列遍历输出二叉树
初始条件：二叉树存在
}
void PastBinTraverse(BinTree BT)
{
操作结果：按后序序列遍历输出二叉树
初始条件：二叉树存在
}
int BinTreeDepth(BinTree BT)
{
操作结果：返回二叉树的深度
初始条件：二叉树存在
}
int BinTreeCount(BinTree BT)
{
操作结果：返回二叉树的结点个数
初始条件：二叉树存在
}
void BinTreeClear(BinTree &BT)
{
操作结果：清空释放二叉树的结点
初始条件：二叉树存在
}
}
四、详细设计
流程图
实现概要设计中定义的所有的数据类型，对每个操作给出伪码算法。对主程序和其他模块也都需要写出伪码算法。
typedef int DataType;
树节点类型定义
typedef struct BitNode{
int data;
struct BitNode *lchild,*rchild;
}BitNode,*BitTree;1. 初始化二叉树，即把树根指针置空
1. Status BinTreeInit()
{ BitTree BT;
BT=(BinTree)malloc(sizeof(BinNode));
BT=NULL;
return OK;
}
2. 按先序次序建立一个二叉树
Status BinTreeCreat(BitTree &BT)
{
scanf("%d",&e);
if(e=='0) BT=NULL;
else
{ BT=(BinNode*)malloc(sizeof(BinNode));
BT->data=e; /*生成根结点*/
BinTreeCreat(BT->lchild); /*构造左子树*/
BinTreeCreat(BT->rchild); /*构造右子树*/
}
return OK;
}
3. 检查二叉树是否为空
Status BinTreeEmpty(BitTree BT)
{ if(BT==NULL) return ERROR;
else return OK;
}
4. 前序遍历
Status PreBinTraverse(BitTree BT)
{ if(BT!=NULL)
{printf("%d ",BT->data);/*DATA[i+1]=s->data;*/
PreBinTraverse(BT->lchild);
PreBinTraverse(BT->rchild);
}
Return OK;
}
5. 中序遍历
Status InBinTraverse(BitTree BT)
{ if(BT!=NULL)
{InBinTraverse(BT->lchild);
printf("%d ",BT->data);
InBinTraverse(BT->rchild);
}
Return OK;
}
6. 后序遍历
Status PastBinTraverse(BitTree BT)
{ if(BT!=NULL)
{PastBinTraverse(BT->lchild);
PastBinTraverse(BT->rchild);
printf("%d ",BT->data);
}
Return OK;
}
7. 求二叉树的深度
Int BinTreeDepth(BitTree BT){
int i=1,j=1;
if(BT==NULL)
return ERROR;
else
{
i=BinTreeDepth(BT->lchild);
j=BinTreeDepth(BT->rchild);
if(i>j)
return(i+1);
else
return (j+1);
}
}
8. 求二叉树中所有结点数
BitTree BinTreeCount(BitTree BT)
{ if(BT==NULL) return 0;
else
return (BinTreeCount(BT->lchild)+BinTreeCount(BT->rchild)+1);
}
9. 清除二叉树，使之变为空树
Status BinTreeClear(BitTree &BT){
if(BT){
if(BT->lchild)
BinTreeClear(BT->lchild);
if(BT->rchild)
BinTreeClear(BT->rchild);
free(BT);
BT=NULL;
Return OK;
}
}
五．调试分析
调试第一步：找出一些因为粗心而导致的错误如：少大括号，少逗号，字母打错，没有分清大小写，等等。
调试第二步：在这一步的调试中主要想谈谈函数BinTreeDepth(BitTree BT)，BinTreeClear(BitTree &BT)这2个函数的调试。
在BinTreeDepth(BitTree BT)函数中因为没有把最后的i和j加1所以最后的结果都少了一层，后来把i和j分别加上了1就可以了。在BinTreeClear(BitTree &BT函数中因为没有BT=NULL;而出现了错误后来改正了以后就好了。
六．结果测试
操作界面为
。
选择1后：
。
选择2：
，分别输入1，2，3，0，0，4，5，0，0，0，0，建立一棵树。
选择3：
选择4：
选择5：
选择6：
选择7：
选择8：
选择9：
选择0：
七．心的体会
这个实验是所有的实验中难度最大的一个了，因为以前对树这种结构没有什么接触所以感觉比较陌生，在树的建立过程中虽然用的是递归算法但还是出现了错误，就是没有正确的领悟到结束的条件，在一个节点的结束时没有把它的左右孩子都置为空，后来经过仔细的思考才明白，只有把结点的左右孩子都置空才算把这个结点结束。
在遍历时因为用的是递归所以没有出现什么错误，一开始对遍历的递归不是很相信，不太相信那样 就可以把一棵树遍历出来，经过这个实验以后就没有怀疑了。
在后面的求结点和深度和销毁树中都用的是递归算法，所以经过这个实验后对递归这个工具有了很深的理解，从开始的懵懂慢慢变的清晰和理解了。
通过这个实验以后加深了对树这种新的结构的了解和理解。
八．源代码
# include<stdio.h>
# include<malloc.h>
# include<stdlib.h>
typedef struct BitNode{
int data;
struct BitNode *lchild,*rchild;
}BitNode,*BitTree;
BitTree BitTreeInit(){
BitTree BT;
BT=(BitNode*)malloc(sizeof(BitNode));
BT=NULL;
return BT;
}
BitTree BitTreeCreat(BitTree &BT){
int ch;
printf("请输入节点的内容,输入0时结束建立！\n");
scanf("%d",&ch);
if(ch==0)
BT=NULL;
else{
BT=(BitTree)malloc(sizeof(BitNode));
BT->data=ch;
BitTreeCreat(BT->lchild);
BitTreeCreat(BT->rchild);
}
return BT;
}
void BitTreeEmpty(BitTree BT){
if(BT==NULL)
printf("树为空！\n");
else
printf("树非空！\n");
}
void PreOrderTraverse(BitTree BT){
if(BT!=NULL){
printf("树结点的内容为:%d\n",BT->data);
PreOrderTraverse(BT->lchild);
PreOrderTraverse(BT->rchild);
}
}
void InOrderTraverse(BitTree BT){
if(BT!=NULL){
InOrderTraverse(BT->lchild);
printf("树结点的内容为:%d\n",BT->data);
InOrderTraverse(BT->rchild);
}
}
void PostOrderTraverse(BitTree BT){
if(BT!=NULL){
PostOrderTraverse(BT->lchild);
PostOrderTraverse(BT->lchild);
printf("树结点的内容为:%d\n",BT->data);
}
}
int count(BitTree BT){
if(BT==NULL)
return 0;
else
return(count(BT->lchild)+count(BT->rchild)+1);
}
int BinTreeDepth(BitTree BT){
int i=1,j=1;
if(BT==NULL)
return 0;
else
{
i=BinTreeDepth(BT->lchild);
j=BinTreeDepth(BT->rchild);
if(i>j)
return(i+1);
else
return (j+1);
}
}
void BinTreeClear(BitTree &BT){
if(BT){
if(BT->lchild)
BinTreeClear(BT->lchild);
if(BT->rchild)
BinTreeClear(BT->rchild);
free(BT);
BT=NULL;
}
}
main(){
int i=1,j,l;
BitTree BT;
while(i!=0){
printf("-----------------欢迎使用-------------------\n");
printf("请选择要进行的操作\n");
printf("1.初始化一棵树 2.建立一棵树 3.判断树是否为空\n");
printf("4.按前序遍历树 5.按中序遍历树 6.按后序遍历树\n");
printf("7.求树的深度 8.求树的结点数 9.把树清空\n");
printf("0.退出操作界面\n");
printf("-----------------谢谢使用-------------------\n");
scanf("%d",&j);
switch(j){
case 1:BT=BitTreeInit();printf("树已经初始化！\n");break;
case 2:BitTreeCreat(BT);break;
case 3:BitTreeEmpty(BT);break;
case 4:PreOrderTraverse(BT);break;
case 5:InOrderTraverse(BT);break;
case 6:PostOrderTraverse(BT);break;
case 7:l=BinTreeDepth(BT);printf("树的深度为：%d\n",l);break;
case 8:l=count(BT);printf("树的结点数为：%d\n",l);break;
case 9:BinTreeClear(BT);printf("树已经清空！\n");break;
case 0:exit(0);
}
}
}