二叉树基本操作--实验报告
实验三
二叉树的基本操作
学院:物理与电子学院
班级:电信1105班
姓名:刘岩
学号:1404110729
一、实验目的
1、熟悉二叉树的基本操作，掌握二叉树的实现以及实际应用。
3、加深对于二叉树的理解，逐步培养解决实际问题的编程能力。
二、实验环境
1台WINDOWS环境的PC机，装有Visual C++ 6.0。
三、实验内容
1、问题描述
现需要编写一套二叉树的操作函数，以便用户能够方便的利用这些函数来实现自己的应用。其中操作函数包括：
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)
2、基本要求
实现以上9个函数。
主函数中实现以下功能：
创建下图中的树b
输出二叉树b
找到’H’节点，输出其左右孩子值
输出b的高度
输出b的节点个数
输出b的四种遍历顺序
3、程序编写
上图转化为二叉树括号表示法为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");
}
四、实验心得与小结
通过本次实验，我熟悉二叉树的基本知识内容，对课本的知识有了更加深刻的理解与掌握掌握。通过查阅资料以及百度一些前人的程序设计，我学到了很多原来在课堂上掌握不到的东西，这次是我的第一次完成了二叉树的实现以及实际应用。加深了对二叉树的理解，。本次实验还运用到了递归的使用，是非常新的体验，原来都是停留在概念上的运用递归处理，这次运用到了实际的实验编程中，受益匪浅。这次实验，让我明白了一个道理，实践出真知，只有通过自己的双手实践，才能更好的理解知识与运用。
第二篇：二叉树的基本操作实现及其应用
实验 三 二叉树的基本操作实现及其应用
一、 实验目的
1．熟悉二叉树结点的结构和对二叉树的基本操作。
2．掌握对二叉树每一种操作的具体实现。
3．学会利用递归方法编写对二叉树这种递归数据结构进行处理的算法。
4.会用二叉树解决简单的实际问题。
二、实验内容
设计程序实现二叉树结点的类型定义和对二叉树的基本操作。该程序包括二 叉树结构类型以及每一种操作的具体的函数定义和主函数。
1、 按先序次序建立一个二叉树 ，
2、按（A:先序 B:中序 C:后序 ）遍历输出二叉树的所有结点
3、求二叉树中所有结点数
4、求二叉树的深度
三、实验步骤
㈠、数据结构与核心算法的设计描述
1、先序输入二叉树元素：
void BinTreeCreate(BitTree &BT) /*按先序次序输入二叉树结点值，空格表示空树*/
{ if(ch==’$’)BT=NULL;else{
if(!(BT=(BitTree)malloc(sizeof(BitNode))))exit(OVERFLOW);//
BT->data=ch; BinTreeCreate(BT->lchild); /*构造左孩子*/ BinTreeCreate(BT->rchild); /*构造右孩子*/}}
2、层次遍历二叉树结点
void BinTraverse(BitTree BT) /*按层次遍历输出二叉树的所有的结点*/
{ BitTree p=BT; BitTree Queue[300];if(p)
{ Queue[rear]=p ;rear=(rear+1)%300; /* 队尾指针加一对25取余，实现循环队列*/
while(front!=rear) /*隊不空*/{
p=Queue[front]; /*出队,将值赋给BT*/ cout<<p->data;front=(front+1)%300;
if(p->lchild) { Queue[rear]=p->lchild;rear=(rear+1)%300;}
if(p->rchild){
Queue[rear]=p->rchild;rear=(rear+1)%300;
}}}
3、递归中序遍历二叉树
char minTraverse(BitTree BT) /*中序遍历小树*/ {if(BT){
minTraverse(BT->lchild);return BT->data;minTraverse(BT->rchild);} }
4、求二叉树深度
int BinTreelen(BitTree BT){
if(!BT)return 0; else{
i=BinTreelen(BT->lchild);j=BinTreelen(BT->rchild);if(i>j)len=i;else len=j;
return len+1;}}
5、求结点数
int BinTreenode(BitTree BT)
{if(BT==0)return 0;else
return BinTreenode(BT->lchild)+BinTreenode(BT->rchild)+1;
}
㈡、函数调用及主函数设计
㈢ 程序调试及运行结果分析
1、 输入结点后选择所需要的操作：
选择1，将进行中序遍历操作：
选择2，将进行层次遍历操作：
选择3，可求深度
选择4，求得结点数
㈣ 实验总结
这次实验，让我了解到了递归的妙用，虽然有些方法推想起来比较麻烦，但在电脑上运行却很简单。做东西不要怕麻烦，慢慢查资料，验证，问题总会解决。
四、主要程序清单
#include <iostream.h>
#include <stdlib.h>
typedef char Data; /* 定義DataType為char類型*/
#define OVERFLOW -100
#define OK 1
#define ERROR 0
typedef struct BitNode /*二叉樹的結點類型*/
{
Data data;
struct BitNode *lchild,*rchild;
}*BitTree;
void BinTreeInit(BitTree &BT) /*初始化二叉树，即把二叉树置空*/
{
BT=new BitNode;
(BT)->lchild=NULL;
(BT)->rchild=NULL;
}
void BinTreeCreate(BitTree &BT) /*按先序次序输入二叉树结点值，空格表示空树*/
{
Data ch;
cout<<"按先序次序输入结点值"<<endl;
cin>>ch;
if(ch=='$')BT=NULL;
else {
if(!(BT=(BitTree)malloc(sizeof(BitNode))))exit(OVERFLOW);
BT->data=ch;
BinTreeCreate(BT->lchild); /*构造左孩子*/
BinTreeCreate(BT->rchild); /*构造右孩子*/
}}
int BinTreeEmpty(BitTree BT) /*检查二叉树是否为空*/
{
if(BT->data!=' ')return 1;else return 0;
}
void BinTraverse(BitTree BT) /*按层次遍历输出二叉树的所有的结点*/
{
BitTree p=BT;BitTree Queue[300];
int front=0,rear=0; /*隊列为空*/ if(p){
Queue[rear]=p ;rear=(rear+1)%300; /* 队尾指针加一对25取余，实现循环队列*/
while(front!=rear) /*隊不空*/{
p=Queue[front]; /*出队,将值赋给BT*/
cout<<p->data;
front=(front+1)%300;
if(p->lchild) {
Queue[rear]=p->lchild;rear=(rear+1)%300;
}
if(p->rchild) {
Queue[rear]=p->rchild;rear=(rear+1)%300;}}}}
void minTraverse(BitTree BT) /*中序遍历小树*/{
if(BT){ minTraverse(BT->lchild);
cout<<BT->data;
minTraverse(BT->rchild);}}
int BinTreelen(BitTree BT){
int i,j,len;
if(!BT)return 0;else{
i=BinTreelen(BT->lchild);
j=BinTreelen(BT->rchild);
if(i>j)len=i;else len=j;
return len+1;}
}
int BinTreenode(BitTree BT)
{
int n=0;if(BT==0)return 0;else
return BinTreenode(BT->lchild)+BinTreenode(BT->rchild)+1;
}
void main()
{BitTree BT;
BinTreeCreate(BT);
int x;
menu: cout<<"选择你要的操作：1,中序遍历；2，层次遍历；3，求深度；4，求结点数;0,退出。"<<endl;
cin>>x;switch(x){
case 1:
minTraverse(BT);cout<<endl;
goto menu;
case 2:
BinTraverse(BT);cout<<endl;
goto menu;
case 3:
cout<<"小树的深度为："<<endl;
cout<<BinTreelen(BT)<<endl;
goto menu;
case 4:
cout<<"小树的结点数为："<<endl;
cout<<BinTreenode(BT)<<endl;
goto menu;
case 0:
break;}}
-
化学实验基本操作的练习
化学实验基本操作唐荣德1某学生采用以下方法清洗实验仪器用稀HNO3清洗做过银镜实验的试管用NaOH溶液清洗盛过苯酚的试管用盐酸清洗…
- 化学实验基本操作实验报告单
-
化学实验报告 实验__化学实验基本操作
实验报告姓名：班级：同组人：自评成绩：项目：化学实验基本操作课程：学号：一、实验目的1.熟悉实验室规则，安全守则及意外事故处理。2…
-
化学实验基本操作实验报告单
实验一化学实验基本操作姓名年级日期任课教师实验目的1认识化学实验常用仪器2掌握药品的取用加热等基本操作实验仪器及药品试管镊子试管夹…
-
生物化学实验基本操作-实验报告
生物化学实验基本操作一实验目的1熟悉化学类实验室的基本常识规则安全及防护知识2掌握基本实验操作及常用仪器的使用方法3通过实际操作进…
-
二叉树实验报告
算法与数据结构实验报告——二叉树课程名称：算法与数据结构实验项目名称：满二叉树的建立与遍历实验时间：20xx年x月x日班级：电科1…
-
二叉树实验报告
实验六树和二叉树的操作一实验目的1进一步掌握树的结构及非线性特点递归特点和动态性2进一步巩固对指针的使用和二叉树的三种遍历方法建立…
-
实验六 二叉树实验报告(1)
实验四二叉树的操作班级：计算机1002班姓名：**学号：**完成日期：20XX.6.14题目：对于给定的一二叉树，实现各种约定的遍…
-
二叉树基本操作--实验报告
宁波工程学院电信学院计算机教研室实验报告一实验目的1熟悉二叉树树的基本操作2掌握二叉树的实现以及实际应用3加深二叉树的理解逐步培养…
-
二叉树实验报告
数据结构实验报告专业班级计算机科学与技术姓名学号一实验目的和要求上机学习二叉树二实验内容实现二叉树的各项算法并掌握其用法如二叉树的…
-
树和二叉树实验报告
树和二叉树一实验目的1掌握二叉树的结构特征以及各种存储结构的特点及适用范围2掌握用指针类型描述访问和处理二叉树的运算二实验要求1认…