二叉树的基本操作及其应用
广西工学院计算机学院
《数据结构》课程实验报告书
实验六二叉树的基本操作及其应用
学生姓名：
学 号：
班级：
指导老师：
专 业：计算机学院软件学院
提交日期：20##年6月22日
1．实验目的
1） 了解二叉树的特点、掌握二叉树的主要存储结构。
2） 掌握二叉树的基本操作，能针对二叉树的具体应用选择相应的存储结构。
3） 掌握递归算法的设计方法。
2.实验内容
（1）二叉链表表示二叉树，建立一棵二叉树，实现下列基本操作,通过数据测试每个操作的正确性，包括：
1. CreateBinTree(&T)： 建立一颗二叉树：。
2. BinTreeEmpty(T): 判断一棵二叉树是否为空树。
3. PreOrderTraverse(T): 先序遍历二叉树T，并输出节点序列。
4. InOrderTraverse(T): 中序遍历二叉树T，并输出节点序列。
5. PostOrderTraverse(T):后序遍历二叉树T，并输出节点序列。
6. LevelOrderTraverse(T):层次遍历二叉树T，并输出节点序列。
7. Value(T,e):查找值为e的节点，并返回该节点的地址。
8. BinTreeDepth(T):返回二叉树的深度。
9. Parent(T,e):查找二叉树T中值为e的节点的双亲，若e为根节点，操作失败。（流程图）
10. LeftChild(T,e):查找二叉树T中值为e的节点的左孩子，若e没有左孩子，则操作失败。（流程图）
11.RightChild(T,e):查找二叉树T中值为e的节点的右孩子，若e没有右孩子，则操作失败。
12. CountNode(T):计算二叉树中节点的个数。
13. Leaf(T): 计算二叉树中叶子节点的个数。
14. OneChild(T): 计算二叉树中度为1的节点个数。
3．实验要求
（1） 上机前交实验源程序（纸质版），由学习委员统一收好交老师（附上不交同学名单）。
（2） 用一切你能想到的办法解决遇到的问题，培养解决问题的能力。
（3） 实验课上进行答辩。
（4） 实验报告当场交。报告内容包括 ：实验目的、实验内容、实验代码、实验运行结果以及实验体会供五部分。
3．主要算法
3.1 顺序存储结构
（1）结构定义：
#include<stdio.h>
#include<stdlib.h>
#include <conio.h>
#include<malloc.h>//各头文件
#define OK 1
#define ERROR 0
#define OVERFLOW -2
typedef char TElemType;//定义宏参
//二叉树链表的类型定义
typedef struct BiTNode
{
TElemType data;//二叉树元素元素类型定义
struct BiTNode *lchild,*rchild;//定义左右孩子指针
}BiTNode,*BinTree;
typedef BinTree ElemType;//队列元素类型定义
//定义链式队列类型
typedef struct QNode
{
ElemType data;//元素类型定义
struct QNode *next;//指向下个结点
}QNode,*QueuePtr;
////队列指针定义
typedef struct
{
QueuePtr front;//队列头指针
QueuePtr rear;//队列尾指针
}QUEUE;
//先序建立二叉树
void CreateBinTree(BinTree &T)
{//初始条件:二叉树不存在
//操作结果：建立一棵二叉树，二叉链表的数据域类型待定
TElemType ch;
scanf("%c",&ch);
if(ch==' ')
T=NULL;
else
{
T=(BinTree)malloc(sizeof(BiTNode));//建立头结点
if(!T)
exit(0);
T->data=ch;
CreateBinTree(T->lchild);
CreateBinTree(T->rchild);
}
return;
}
//清空二叉树
void ClearBinTree(BinTree &T)
{//初始条件:二叉树已存在
//操作结果：将链表都赋值为空
if(T)
{
T->data=' ';//赋域空值
ClearBinTree(T->lchild);
ClearBinTree(T->rchild);
}
return;
}
//判断空二叉树
int BinTreeEmpty(BinTree T)
{//初始条件:二叉树已存在
//操作结果:若空返回值1，反之返回0
if(!T)
return 1;
else
return 0;
}
//先序遍历二叉树
void PreorderTraverse(BinTree T)
{//初始条件:二叉树已存在
//操作结果：先序递归遍历T
if(T)
{
printf("%c",T->data);
PreorderTraverse(T->lchild);
PreorderTraverse(T->rchild);
}
return;
}
//中序遍历二叉树
void InorderTraverse(BinTree T)
{//初始条件:二叉树已存在
//操作结果:中序递归遍历T
if(T)
{
InorderTraverse(T->lchild);
printf("%c",T->data);
InorderTraverse(T->rchild);
}
return;
}
//后序遍历二叉树
void PostorderTraverse(BinTree T)
{//初始条件:二叉树已存在
//操作结果:后序递归遍历T
if(T)
{
PostorderTraverse(T->lchild);
PostorderTraverse(T->rchild);
printf("%c",T->data);
}
return;
}
//初始化链式队列
void InitQueue(QUEUE *q)
{//初始条件:队列不存在
//操作结果：建立一个队列
q->front=q->rear=(QueuePtr)malloc(sizeof(QNode));//建立头尾结点
if(!(q->front))//头结点指向NULL
exit(0);
q->front->next=NULL;
}
//销掉链式队列
void DestroyQueue(QUEUE *q)
{//初始条件:队列已存在
//操作结果：销掉链式队列
while(q->front)//头结点还没指向NULL
{
q->rear=q->front->next;
free(q->front);
q->front=q->rear;
}
}
//判断空队列
int QueueEmpTy(QUEUE q)
{//初始条件:队列已存在
//操作结果：若为空队列返回1，否则返回0
if(q.front==q.rear)//头指针等于尾指针
return 1;
else
return 0;
}
//入队列
void EnQueue(QUEUE *q ,ElemType e)
{//初始条件:队列已存在
//操作结果：元素e从队尾入队
QueuePtr p;
p=(QueuePtr)malloc(sizeof(QNode));//建立新结点p
if(!p)
exit(0);
p->data=e;
p->next=NULL;
q->rear->next=p;
q->rear=p;
}
//出队列
void DeQueue(QUEUE *q,ElemType *e)
{//初始条件:队列已存在
//操作结果：元素e从队头输出
QueuePtr p;
if(q->rear!=q->front)//头指针不等于尾指针
{
p=q->front->next;
*e=p->data;
q->front->next=p->next;
if(q->rear==p)
q->rear=q->front;
free(p);
}
}
//层次遍历二叉树
void LevelTraverse(BinTree T)
{ //初始条件:二叉树已存在
//操作结果:层次递归遍历T
QUEUE q;
BinTree a;
if(T)
{
InitQueue(&q);//初始化链式队列
EnQueue(&q,T);//入队列
while(!QueueEmpTy(q))
{
DeQueue(&q,&a);//出队列
printf("%c",a->data);
if(a->lchild)//有左孩子
EnQueue(&q,a->lchild );
if(a->rchild )//有右孩子
EnQueue(&q,a->rchild );
}
}
return;
}
//查找值为e的节点
BinTree value(BinTree T, TElemType e)
{//初始条件:二叉树已存在
//操作结果：返回二叉树T中指向元素值为e的结点的指针
QUEUE q;
BinTree a;
if(T)
{
InitQueue(&q);//初始化链式队列
EnQueue(&q,T);//入队列
while(!QueueEmpTy(q))
{
DeQueue(&q,&a);//出队列
if(a->data ==e)
return a;
if(a->lchild)//有左孩子
EnQueue(&q,a->lchild );
if(a->rchild )//有右孩子
EnQueue(&q,a->rchild );
}
}
return NULL;
}
//计算二叉树的深度
int BinTreeDepth(BinTree T)
{//初始条件:二叉树已存在
//操作结果:输出二叉树的深度
int i,j;
if(!T)
return 0;
i= BinTreeDepth(T->lchild);
j=BinTreeDepth(T->rchild);
return i>=j?i+1:j+1;
}
//查找值为e的节点的双亲
BinTree Parent(BinTree T,TElemType e)
{//初始条件:二叉树已存在
//操作结果:返回二叉树T中指向元素值为e的结点的双亲的指针
QUEUE q;
BinTree a;
if(T)
{
InitQueue(&q);//初始化链式队列
EnQueue(&q,T);//入队列
while(!QueueEmpTy(q))
{
DeQueue(&q,&a);//出队列
if(a->lchild&&a->lchild->data==e||a->rchild&&a->rchild->data==e)
return a;
else
{
if(a->lchild)//有左孩子
EnQueue(&q,a->lchild );
if(a->rchild )//有右孩子
EnQueue(&q,a->rchild );
}
}
}
return NULL;
}
//查找值为e的节点的左孩子
BinTree Leftchild(BinTree T,TElemType e)
{//初始条件:二叉树已存在
//操作结果：返回二叉树T中指向元素值为e的结点的左孩子的指针
BinTree p;
p=value(T,e);
if(p)
if(p->lchild)
return p->lchild;
else
return NULL;
return NULL;
}
//查找值为e的节点的右孩子
BinTree Rightchild(BinTree T,TElemType e)
{//初始条件:二叉树已存在
//操作结果：返回二叉树T中指向元素值为e的结点的右孩子的指针
BinTree p;
p=value(T,e);
if(p)
if(p->rchild)
return p->rchild;
else
return NULL;
return NULL;
}
//计算二叉树中节点的个数
int CountNode(BinTree T)
{//初始条件:二叉树已存在
//操作结果：输出二叉树中节点的个数
static int sum=0;
if(NULL!=T)
{
++sum;
CountNode(T->lchild);
CountNode(T->rchild);
}
return sum;
}
//计算二叉树中叶子节点的个数
int Leaf(BinTree T)
{//初始条件:二叉树已存在
//操作结果：输出二叉树中叶子节点的个数
if(!T)
return 0;
if(!T->lchild&&!T->rchild)
return 1;
return Leaf(T->lchild)+Leaf(T->rchild);
}
//计算二叉树中度为1的节点个数
int Onechild(BinTree T)
{//初始条件:二叉树已存在
//操作结果：输出二叉树中度为1的节点个数
if(!T)
return 0;
if(T->lchild&&!T->rchild||!T->lchild &&T->rchild)
return 1+ Onechild(T->lchild)+ Onechild(T->rchild);
return Onechild(T->lchild)+ Onechild(T->rchild);
}
//主函数
void main()
{
BinTree t,p;
char e;
int j,k;
while(1)
{
system("cls");//清屏
printf("\n\t***************************************************");
printf("\n\t* 二叉树的基本操作及其应用 *");
printf("\n\t***************************************************\n");
printf("\t * 1.建立二叉树 2.先序遍历 *\n");
printf("\t * 3.中序遍历 4.后序遍历 * \n");
printf("\t * 5.层次遍历 6.二叉树层数 * \n");
printf("\t * 7.结点个数 8.叶子结点数 * \n");
printf("\t * 9.单孩子结点数 10.查找结点左孩子 *\n");
printf("\t * 11.查找结点右孩子 12.查找结点双亲 *\n");
printf("\t * 13.清空二叉树 0.退出 *\n");
printf("\t****************************************************\n");
printf("请选择选项<0-13>: ");
scanf(" %d",&k);
if(k<0||k>13)
{
printf("输入有误，请重新输入!");
printf("\n");
printf("\n\t\t\t按任意键进行重新操作!");
getch();
continue;
}
switch(k)
{
case 1:
system("cls");//清屏
printf("按先序遍历建立一棵二叉树，输入相应的数据序号：\n");
printf("比如: AAA___A___\n");
printf("===================================================\n");
printf(" ( 1 )");
printf("\n");
printf(" / \\");
printf("\n");
printf(" ( 2 ) ( 4 )");
printf("\n");
printf(" / \\ / \\");
printf("\n");
printf(" ( 3 ) ( ) ( ) ( )");
printf("\n");
printf("====================================================\n");
printf("\n");
printf("你的输入为：");
CreateBinTree(t);
printf("\n");
printf("\n\t\t\t按任意键进行重新操作!");
getch();
break;
case 2:
printf("先序遍历二叉树的序列为：");
PreorderTraverse(t);//调用先序遍历函数
printf("\n");
printf("\n\t\t\t按任意键进行重新操作!");
getch();
break;
case 3:
printf("中序遍历二叉树的序列为：");
InorderTraverse(t);//调用中序遍历函数
printf("\n");
printf("\n\t\t\t按任意键进行重新操作!");
getch();
break;
case 4:
printf("后序遍历二叉树的序列为：");
PostorderTraverse(t);//调用后序遍历函数
printf("\n");
printf("\n\t\t\t按任意键进行重新操作!");
getch();
break;
case 5:
printf("层次遍历二叉树的序列为：");
LevelTraverse(t);//调用层次遍历函数
printf("\n");
printf("\n\t\t\t按任意键进行重新操作!");
getch();
break;
case 6:
printf("二叉树共有%d层!\n",BinTreeDepth(t));
printf("\n");
printf("\n\t\t\t按任意键进行重新操作!");
getch();
break;
case 7:
printf("二叉树的结点数为：%d\n",CountNode(t));
printf("\n\t\t\t按任意键进行重新操作!");
getch();
break;
case 8:
printf("二叉树的叶子结点数为：%d\n",Leaf(t));
printf("\n");
printf("\n\t\t\t按任意键进行重新操作!");
getch();
break;
case 9:
printf("二叉树的单孩子结点数为：%d\n",Onechild(t));
printf("\n");
printf("\n\t\t\t按任意键进行重新操作!");
getch();
break;
case 10:
printf("请输入要查找结点的值：");
e=getchar();
scanf("%c",&e);
p=Parent(t,e);
if(p)
printf("\n值为%c的结点的双亲结点的值为:%c",e,p->data);
else
printf("\n这结点无双亲!");
printf("\n");
printf("\n\t\t\t按任意键进行重新操作!");
getch();
break;
case 11:
printf("请输入要查找结点的值：");
e=getchar();
scanf("%c",&e);
p=Leftchild(t,e);
if(p)
printf("\n值为%c的结点的左孩子结点的值为:%c",e,p->data);
else
printf("\n这结点无左孩子!");
printf("\n");
printf("\n\t\t\t按任意键进行重新操作!");
getch();
break;
case 12:
printf("请输入要查找结点的值：");
e=getchar();
scanf("%c",&e);
p= Rightchild(t,e);
if(p)
printf("\n值为%c的结点的右孩子结点的值为:%c",e,p->data);
else
printf("\n这结点无右孩子!");
printf("\n");
printf("\n\t\t\t按任意键进行重新操作!");
getch();
break;
case 13:
printf("你真确定要清空二叉树 ! 1.YES 2.NO\n");
printf("请选择项<1-2>: ");
scanf("%d",&j);
if(j==1)
ClearBinTree(t);
printf("二叉树清空成功呦!\n");
if(j==2)
printf("\n");
printf("\n\t\t\t按任意键进行重新操作!");
getch();
break;
case 0:
printf("你真确定要退出! 1.YES 2.NO\n");
printf("请选择项<1-2>: ");
scanf("%d",&j);
if(j==1)
exit(OVERFLOW);
else
printf("\n");
printf("\n\t\t\t按任意键进行重新操作!");
getch();
break;
}
}
}
3.流程图
1. 查找二叉树T中值为e的节点的双亲流程图
2. 查找二叉树T中值为e的节点的左孩子流程图
4．程序运行结果
（1） 实验内容（1）
运行结果如下：
2）运行结果如下：
运行结果如下：
运行结果如下：
运行结果如下：
运行结果如下：
5.心得体会。
图的基本操作还有许多的不解之处，特别是最短距离
-
二叉树的应用
二叉树的应用一实验目的1使学生熟练掌握二叉树的逻辑结构和存储结构2熟练掌握二叉树的各种遍历算法3熟悉二叉树的应用二实验内容本次实验…
-
二叉树的遍历和应用
内蒙古科技大学本科生课程设计说明书题目数据结构课程设计二叉树的遍历和应用学生姓名学号专业班级指导教师20xx年5月29日内蒙古科技…
-
二叉树的基本操作及其应用
广西工学院计算机学院数据结构课程实验报告书实验六二叉树的基本操作及其应用学生姓名学号班级指导老师专业计算机学院软件学院提交日期20…
-
树和二叉树的应用
数据结构实验报告实验题目树和二叉树的应用实验内容重言式判别实验目的掌握树和二叉树的概念及工作原理运用其原理及概念完成上述实验题中的…
-
二叉树的应用实验报告
实验报告课程名称数据结构上机实验实验项目二叉树的应用实验仪器PC机系别专业班级学号学生姓名实验日期成绩指导教师实验三二叉树的应用1…
-
数据结构_实验9_二叉树遍历的应用
实验报告实验课程数据结构实验项目实验九二叉树遍历的应用实验地点指导教师班级学生姓名金轶洲学号09020xx03教师评分日期浙江传媒…
-
二叉树的应用实验报告
实验报告课程名称数据结构上机实验实验项目二叉树的应用实验仪器PC机系别专业班级学号学生姓名实验日期成绩指导教师实验三二叉树的应用1…
-
二叉树的基本操作与应用,完整版
includequotstdiohquotincludequotstdlibhquotincludequotstringhquotincludequo…
-
二叉树的遍历和应用
内蒙古科技大学本科生课程设计说明书题目数据结构课程设计二叉树的遍历和应用学生姓名学号专业班级指导教师20xx年5月29日内蒙古科技…
-
二叉树的应用
二叉树的应用一实验目的1使学生熟练掌握二叉树的逻辑结构和存储结构2熟练掌握二叉树的各种遍历算法3熟悉二叉树的应用二实验内容本次实验…