实验四 树和二叉树的操作
实验四树和二叉树的操作
一、实验题目：用菜单驱动的手法，编写一个完整的程序，生成一棵二叉树，求二叉树的高度，求二叉树的叶子结点数，输出二叉树的所有结点。
二、实验算法描述：
二叉树的生成是指如何在内存中建立二叉树的存储结构。建立顺序存储结构的问题较简单，这里仅讨论如何建立二叉链表。要建立二叉链表，就需要按照某种方式输人二叉树的结点及其逻辑信息。注意到对二叉树遍历时，不仅得到了结点信息，而且由序列中结点的先后关系还可获得一定的逻辑信息，如果这些信息足够，就可根据遍历序列生成相应的二叉树
二叉树的生成方法就是基于遍历序列的，相当于遍历问题的逆问题，即由遍历序列反求二叉树，这需要分析和利用二叉树遍历序列的特点。在下列两种方法中任选一种。
**以下的（一）（二）要编写在一个完整的程序中。如果你不能编在一个程序中，则可以用两个完整的程序来实现。
（一）用先根序列建立二叉树
二叉树的结点就按相应的遍历过程逐个生成。类似层次遍历，如果不对遍历序列作些补充，是不能完整反映结点间的逻辑关系的，也就不能得到正确的结果。补充的方法也是增加虚结点，但这里只需对空指针对应的位置进行补充，而不必补充到完全二叉树的形式。以先根遍历上图为例，二叉树的先根输入序列为：ABD＠G＠＠＠CE＠＠FH＠＠＠
其中＠表示虚结点，这里不需要结束符。算法过程为，先生成根结点，再生成左子树，然后是右子树，左右子树的生成采用递归。在具体作本实验时,还需编写一个主函数调用这个函数来生成二叉树,最后输出二叉树的结点序列。
（二）按完全二叉树的层次顺序，依次输入结点信息来建立二叉链表
这是因为完全三叉树的层次遍历序列中，结点间的序号关系可反映父子关系即逻辑关系。对一般的二又树，要补充若干个虚结点使其成为完全二叉树后，冉按其层次顺序输入。例如，仅含3个结点A、B、C的右单支树（见下图2），按完全二叉树的形式输入的结点序列为：A＠B＠＠＠C＃，其中＠表示虚结点，＃表示输入结束。
算法的基本思想是：依次输入结点信息，若输入的结点不是虚结点，则建立一个新结点：若新结点是第1个结点，则令其为根结点；否则将新结点作为孩子链接到它的双亲结点上。如此重复下去，直至输入字符“＃”为止。
这里的关键是新结点与其双亲的链接。由于是按层次自左至右输入结点的，所以先输入的结点，其孩子也必定较先输入。即结点与其孩子具有先进先出的特点，于是可设置一个队列，保存已输人结点的地址。这样，队尾是当前正输入的结点，队头是其双亲结点。当队头结点的两个孩子都输入完毕后，出队，新的队头是下一个要输入孩子的双亲结点。如此下去，直到输入结束符为止。
双亲与孩子的链接方法是：若当前输入的结点编号是偶数，则该结点作为左孩子与其双亲链接；否则作为右孩子与其双亲链。若双亲结点或孩子结点为虚结点，则无需链接。
实验程序如下：
#include
#include
#include
#include
int cmp(const void *a,const void *b)
{return *(int *)a-*(int *)b;
}
typedef char datatype;
typedef struct treenode
{datatype data;
struct treenode *leftchild,*rightchild;
}treenode,*bitree;
treenode *t;
int count=0;
//建立二叉树方法1
treenode *creattree_1()
{
treenode *t,*p,*v[100];
int i,j;
datatype e;
t=NULL;
printf("\n请输入初始二叉树各结点的编号和对应的值（如1,a）:");
scanf("%d,%c",&i,&e);
while(i!=0&&e!='#')
{ p=(treenode *)malloc(sizeof(treenode));
p->data=e;
p->leftchild=NULL;
p->rightchild=NULL;
v[i]=p;
if(i==1)
{t=p;
}
else
{ j=i/2;
if(i%2==0)
{v[j]->leftchild=p;
}
else
{v[j]->rightchild=p;
}
}
printf("\n请继续输入（以0，#结束）:");
scanf("%d,%c",&i,&e);
}
return (t);
}
//建立二叉树方法2
treenode *creattree_2()
{
treenode *t;
datatype e;
scanf("%c",&e);
if(e=='#')
{t=NULL;
}
else
{ t=(treenode *)malloc(sizeof(treenode));
t->data=e;
t->leftchild=creattree_2();
t->rightchild=creattree_2();
}
return (t);
}
//先序遍历输出二叉树
void preorder(treenode *p)
{
if(p)
{ printf("%-4c",p->data);
preorder(p->leftchild);
preorder(p->rightchild);
}
}
//中序遍历输出二叉树
void inorder(treenode *p)
{ if(p)
{
inorder(p->leftchild);
printf("%-4c",p->data);
inorder(p->rightchild);
}
}
//后序遍历输出二叉树
void postorder(treenode *p)
{if(p)
{
postorder(p->leftchild);
postorder(p->rightchild);
printf("%-4c",p->data);
}
}
//计算二叉树高度
int treedepth(bitree bt)
{
int lefthight,righthight,max;
if(bt!=NULL)
{ lefthight=treedepth(bt->leftchild);
righthight=treedepth(bt->rightchild);
max=(lefthight>righthight)?lefthight:righthight;
return(max+1);
}
else
{return (0);
}
}
//逆时针旋转90度输出二叉树
void printtree(bitree bt,int level)
{ int j;
if(bt)
{
printtree(bt->rightchild,level+1);
for(j=0;j<=6*level;j++)
printf(" ");
printf("%c\n",bt->data);
printtree(bt->leftchild,level+1);
}
}
//交换二叉树左右子树
void exchange(bitree bt)
{ bitree p;
if(bt)
{
p=bt->leftchild;
bt->leftchild=bt->rightchild;
bt->rightchild=p;
exchange(bt->leftchild);
exchange(bt->rightchild);
}
}
//计算叶结点数
int leafcount(bitree bt)
{ if(bt!=NULL)
{
leafcount(bt->leftchild);
leafcount(bt->rightchild);
if((bt->leftchild==NULL)&&(bt->rightchild==NULL))
{ count++;
}
}
return (count);
}
//输出叶结点
void paintleaf(bitree bt)
{ if(bt!=NULL)
{
if(bt->leftchild==NULL&&bt->rightchild==NULL)
{
printf("%-4c",bt->data);
}
paintleaf(bt->leftchild);
paintleaf(bt->rightchild);
}
}
//哈夫曼树
int haffman()
{
int a[100],b[100];
int i,j=0,k,n;
memset(a,0,100);
memset(b,0,100);
printf("请输入构造哈夫曼树的元素个数（正整数）：");
scanf("%d",&n);
printf("\n");
printf("请依次输入各元素权值（以空格间隔，按ENTER键结束）：\n");
for(i=0;i {scanf("%d",&a[i]); } printf("\n"); getchar(); printf("构造哈夫曼树过程：\n\n"); for(i=0;i {qsort(a,n,sizeof(a[0]),cmp); printf("步骤（%d）",i+1); for(k=i;k { printf("%d ",a[k]); } printf("\n\n"); b[j++]=a[i]; b[j++]=a[i+1]; a[i+1]=a[i]+a[i+1]; } printf("当前哈夫曼树的所有结点权值为：\n"); for(i=0;i { printf("%-5d",b[i]); } printf("\n\n"); } int main() { int command; char order; do{ printf("==================简单二叉树操作菜单===================\n") ; printf("* 1.建立二叉树（按照完全二叉树）*\n"); printf("* 2.建立二叉树（模仿先序递归遍历）*\n"); printf("* 3.先序递归遍历二叉树*\n"); printf("* 4.中序递归遍历二叉树*\n"); printf("* 5.后序递归遍历二叉树*\n"); printf("* 6.输出二叉树的高度*\n"); printf("* 7.输出二叉树的叶结点*\n"); printf("* 8.交换二叉树的左右子树*\n"); printf("* 9.打印二叉树*\n"); printf("* 10.哈夫曼树（最优二叉树）*\n"); printf("* 0.退出*\n"); printf("=======================================================\n\n"); printf("请输入指令（0,1,2,3,4,5,6,7,8,9,10）:"); scanf("%d",&command); if(command<0||command>10) { getchar(); system("cls"); printf("\n指令输入错误！请重新输入！\n"); } switch(command) { case 1: getchar(); system("cls"); printf("若已构建二叉树，此操作将会清除当前二叉树，继续/退出[Y/N]:"); scanf("%c",&order) ; if(order=='Y'||order=='y') { t=creattree_1(); if(t) { printf("\n当前二叉树为（逆时针旋转90度）：\n"); printtree(t,0); printf("\n"); } else { printf("\n当前二叉树为空！请先建立二叉树！\n"); } getchar(); break; } else { break; } case 2: getchar(); system("cls"); printf("若已构建二叉树，此操作将会清除当前二叉树，继续/退出[Y/N]:"); scanf("%c",&order) ; if(order=='Y'||order=='y') { printf("\n请输入二叉树按先序递归遍历各结点的值（虚结点以#代替）:\n"); fflush(stdin); t=creattree_2(); if(t) { printf("\n当前二叉树为（逆时针旋转90度）：\n"); printtree(t,0); printf("\n"); } else { printf("\n当前二叉树为空！请先建立二叉树！\n"); } getchar(); break; } else { break; } case 3: getchar(); system("cls"); if(t) { printf("\n当前二叉树为（逆时针旋转90度）：\n"); printtree(t,0); printf("\n"); printf("\n先序递归遍历序列为:\n"); preorder(t); printf("\n"); } else { printf("\n二叉树为空！请先建立二叉树！\n"); } break; case 4: getchar(); system("cls"); if(t) { printf("\n当前二叉树为（逆时针旋转90度）：\n"); printtree(t,0); printf("\n"); printf("\n中序递归遍历序列为:\n"); inorder(t); printf("\n"); } else { printf("\n二叉树为空！请先建立二叉树！\n"); } break; case 5: getchar(); system("cls"); if(t) { printf("\n当前二叉树为（逆时针旋转90度）：\n"); printtree(t,0); printf("\n"); printf("\n后序递归遍历序列为:\n"); postorder(t); printf("\n"); } else { printf("\n二叉树为空！请先建立二叉树！\n"); } break; case 6: getchar(); system("cls"); if(t) { printf("\n当前二叉树为（逆时针旋转90度）：\n"); printtree(t,0); printf("\n"); printf("当前二叉树的高度为:%d\n",treedepth(t)); } else { printf("\n二叉树为空！请先建立二叉树！\n"); } break; case 7: getchar(); system("cls"); if(t) { printf("\n当前二叉树为（逆时针旋转90度）：\n"); printtree(t,0); printf("\n"); printf("当前二叉树的叶子结点数为:%d\n\n",leafcount(t)); printf("当前二叉树的叶子结点依次为:\n"); paintleaf(t); printf("\n"); } else { printf("\n二叉树为空！请先建立二叉树！\n"); } break; case 8: getchar(); system("cls"); if(t) { printf("\n当前二叉树为（逆时针旋转90度）：\n"); printtree(t,0); printf("\n"); exchange(t); printf("\n交换后的二叉树为:\n"); printtree(t,0); printf("\n"); } else { printf("\n二叉树不存在！请先建立二叉树！\n"); } break; case 9: getchar(); system("cls"); if(t) { printf("\n当前二叉树为（逆时针旋转90度）：\n"); printtree(t,0); printf("\n"); } else { printf("\n二叉树不存在！请先建立二叉树！\n"); } break; case 10: getchar(); system("cls"); printf("==========哈夫曼树的建立与输出==========\n\n"); haffman(); break; } if(command==0) { getchar(); system("cls"); printf("再见！\n\n"); break; } printf("\n请按ENTER键返回主菜单!\n"); getchar(); system("cls"); }while(command>=1&&command<=10); } 实验三二叉树的遍历 一、实验目的 １、熟悉二叉树的结点类型和二叉树的基本操作。 ２、掌握二叉树的前序、中序和后序遍历的算法。 3、加深对二叉树的理解，逐步培养解决实际问题的编程能力。 二、实验环境 运行Ｃ或VC++的微机。 三、实验内容 1、依次输入元素值，以链表方式建立二叉树，并输出结点的值。 2、分别以前序、中序和后序遍历二叉树的方式输出结点内容。 四、设计思路 1. 对于这道题，我的设计思路是先做好各个分部函数，然后在主函数中进行顺序排列，以此完成实验要求 2．二叉树采用动态数组 3.二叉树运用9个函数，主要有主函数、构建空二叉树函数、建立二叉树函数、访问节点函数、销毁二叉树函数、先序函数、中序函数、后序函数、范例函数，关键在于访问节点 五、程序代码 #include int data; //数据域 struct TNode *lchild,*rchild; // 指针域包括左右孩子指针 }TNode,*Tree; void CreateT(Tree *T)//创建二叉树按,依次输入二叉树中结点的值 { int a; scanf("%d",&a); if(a==00) // 结点的值为空 *T=NULL; else // 结点的值不为空 { *T=(Tree)malloc(sizeof(TNode)); if(!T) { printf("分配空间失败！！TAT"); exit(ERROR); } (*T)->data=a; CreateT(&((*T)->lchild)); // 递归调用函数，构造左子树 CreateT(&((*T)->rchild)); // 递归调用函数，构造右子树 } } void InitT(Tree *T)//构建空二叉树 { T=NULL; } void DestroyT(Tree *T)//销毁二叉树 { if(*T) // 二叉树非空 { DestroyT(&((*T)->lchild)); // 递归调用函数，销毁左子树 DestroyT(&((*T)->rchild)); // 递归调用函数，销毁右子树 free(T); T=NULL; } } void visit(int e)//访问结点 { printf("%d ",e); } 二叉树的基本操作实现及其应用 一、实验目的 1．熟悉二叉树结点的结构和对二叉树的基本操作。 2．掌握对二叉树每一种操作的具体实现。 3．学会利用递归方法编写对二叉树这种递归数据结构进行处理的算法。 4.会用二叉树解决简单的实际问题。 二、实验内容 设计程序实现二叉树结点的类型定义和对二叉树的基本操作。该程序包括二叉树结构类型以及每一种操作的具体的函数定义和主函数。 1 按先序次序建立一个二叉树， 2按（A:先序 B:中序 C:后序）遍历输出二叉树的所有结点 以上比做，以下选做 3求二叉树中所有结点数 4求二叉树的深度 三、实验步骤 ㈠、数据结构与核心算法的设计描述 /* 定义DataType为char类型 */ typedef char DataType; /* 二叉树的结点类型 */ typedef struct BitNode { DataType data; struct BitNode *lchild,*rchild; }*BitTree; 相关函数声明： 1、/* 初始化二叉树，即把树根指针置空 */ void BinTreeInit(BitTree *BT) { BT=(BitTree)malloc(sizeof(BitNode)); BT->data=NULL; cout<<"二叉树初始化成功!"< //二叉树的基本操作 #include 树和二叉树 一、实验目的 1.掌握二叉树的结构特征，以及各种存储结构的特点及适用范围。 2.掌握用指针类型描述、访问和处理二叉树的运算。 二、实验要求 1.认真阅读和掌握本实验的程序。 2.上机运行本程序。 3.保存和打印出程序的运行结果，并结合程序进行分析。 4.按照二叉树的操作需要，重新改写主程序并运行，打印出文件清单和运 行结果。 三、实验内容 1.输入字符序列，建立二叉链表。 2.按先序、中序和后序遍历二叉树（递归算法）。 3.按某种形式输出整棵二叉树。 4.求二叉树的高度。 5.求二叉树的叶节点个数。 6.交换二叉树的左右子树。 7.借助队列实现二叉树的层次遍历。 8.在主函数中设计一个简单的菜单，分别调试上述算法。 为了实现对二叉树的有关操作，首先要在计算机中建立所需的二叉树。建立二叉树有各种不同的方法。一种方法是利用二叉树的性质5来建立二叉树，输入数据时要将节点的序号（按满二叉树编号）和数据同时给出：（序号，数据元素0）。另一种方法是主教材中介绍的方法，这是一个递归方法，与先序遍历有点相似。数据的组织是先序的顺序，但是另有特点，当某结点的某孩子为空时以字符“#”来充当，也要输入。若当前数据不为“#”，则申请一个结点存入当前数据。递归调用建立函数，建立当前结点的左右子树。 四、解题思路 1、先序遍历：○1访问根结点，○2先序遍历左子树，○3先序遍历右子树 2、中序遍历：○1中序遍历左子树，○2访问根结点，○3中序遍历右子树 3、后序遍历：○1后序遍历左子树，○2后序遍历右子树，○3访问根结点 4、层次遍历算法：采用一个队列q，先将二叉树根结点入队列，然后退队列，输出该结点；若它有左子树，便将左子树根结点入队列；若它有右子树，便将右子树根结点入队列，直到队列空为止。因为队列的特点是先进后出，所以能够达到按层次遍历二叉树的目的。 五、程序清单 #include 实验三二叉树的基本运算 一、实验目的 1、使学生熟练掌握二叉树的逻辑结构和存储结构。 2、熟练掌握二叉树的各种遍历算法。 二、实验内容 [问题描述] 建立一棵二叉树，试编程实现二叉树的如下基本操作： 1. 按先序序列构造一棵二叉链表表示的二叉树T； 2. 对这棵二叉树进行遍历：先序、中序、后序以及层次遍历，分别输出结点的遍历序列； 3. 求二叉树的深度/结点数目/叶结点数目；(选做) 4. 将二叉树每个结点的左右子树交换位置。（选做） [基本要求] 从键盘接受输入（先序），以二叉链表作为存储结构，建立二叉树（以先序来建立）， [测试数据] 如输入：ABCффDEфGффFффф（其中ф表示空格字符） 则输出结果为 先序：ABCDEGF 中序：CBEGDFA 后序：CGEFDBA 层序：ABCDEFG [选作内容] 采用非递归算法实现二叉树遍历。 三、实验前的准备工作 1、掌握树的逻辑结构。 2、掌握二叉树的逻辑结构和存储结构。 3、掌握二叉树的各种遍历算法的实现。 一实验分析 本次试验是关于二叉树的常见操作，主要是二叉树的建立和遍历。二叉树的遍历有多种方法，本次试验我采用递归法，递归法比较简单。 二概要设计 功能实现 1.int CreatBiTree(BiTree &T) 用递归的方法先序建立二叉树, 并用链表储存该二叉树 2.int PreTravel(BiTree &T) 前序遍历 3. int MidTravel(BiTree &T) 中序遍历 4.int PostTravel(BiTree &T) 后序遍历 5.int Depth(BiTree &T) //计算树的深度 6.int howmuch(BiTree T,int h) 采用树节点指针数组，用于存放遍历到的元素地址，如果有左孩子，存入地址，j加一，否则没操作，通过访问数组输出层次遍历的结果。k计算叶子数，j为总节点。 7. int exchang(BiTree &T) 交换左右子树，利用递归，当有左右孩子时才交换 三详细设计 #include 二叉树的建立和遍历的实验报告 篇一：二叉树的建立及遍历实验报告 实验三：二叉树的建立及遍历 【实验目的】 （1）掌握利用先序序列建立二叉树的二叉链表的过程。 （2）掌握二叉树的先序、中序和后序遍历算法。 【实验内容】 1. 编写程序，实现二叉树的建立，并实现先序、中序和后序遍历。 如：输入先序序列abc###de###，则建立如下图所示的二叉树。 并显示其先序序列为：abcde 中序序列为：cbaed 后序序列为：cbeda 【实验步骤】 1.打开VC++。 2.建立工程：点File->New，选Project标签，在列表中选Win32 Console Application，再在右边的框里为工程起好名字，选好路径，点OK->finish。至此工程建立完毕。 3.创建源文件或头文件：点File->New，选File标签，在列表里选C++ Source File。给文件起好名字，选好路径，点OK。至此一个源文件就被添加到了你刚创建的工程之中。 4．写好代码 5．编译－＞链接－＞调试 #include #include #define OK 1 #define OVERFLOW -2 typedef int Status; typedef char TElemType; typedef struct BiTNode { TElemType data; struct BiTNode *lchild, *rchild; }BiTNode,*BiTree; Status CreateBiTree(BiTree &T) { TElemType ch; scanf("%c",&ch); if (ch=='#') T= NULL; else { if (!(T = (BiTNode *)malloc(sizeof(BiTNode)))) 数据结构二叉树基本操作 (1). // 对二叉树的基本操作的类模板封装 //------------------------------------------------------------------------------------------------------------------------ #include 重庆交通大学综合性设计性实验报告 姓名姚远学号 631106060113 班级：计信息一班 实验项目名称：二叉树 实验项目性质：设计性实验 实验所属课程：数据结构 实验室(中心)： 407机房 指导教师：鲁云平 实验完成时间： 2013 年 5 月 10 日 一、实验目的 1. 建立二叉树 2. 计算结点所在的层次 3.统计结点数量和叶结点数量 4.计算二叉树的高度 5.计算结点的度 6.找结点的双亲和子女 7.二叉树的遍历 8.二叉树的输出等等 二、实验内容及要求 1.二叉树的结点结构,二叉树的存储结构由学生自由选择和设定 2.实验完成后上交打印的实验报告,报告内容与前面所给定的实验模板相同 3.将实验报告电子版和源代码在网络教学平台提交 三、实验设备及软件 VISUAL C++软件 四、设计方案 ㈠题目（老师给定或学生自定） 二叉树的应用 ㈡设计的主要思路 在计算机科学中，二叉树是每个结点最多有两个子树的有序树。通常子树的根被称作“左子树”（left subtree）和“右子树”（right subtree）。二叉树常被用作二叉查找树和二叉堆或是二叉排序树。二叉树的每个结点至多只有二棵子树(不存在出度大于2的结点)，二叉树的子树有左右之分，次序不能颠倒。二叉树的第i层至多有2的i -1次方个结点；深度为k的二叉树至多有2^(k) -1个结点；对任何一棵二叉树T，如果其终端结点数(即叶子结点数)为n0，出度为2的结点数为n2，则n0 =n2 + 1。 ㈢主要功能 实现二叉树的各项操作。 五、主要代码 #include 郑州轻工业学院数据结构实验报告 题目 学生姓名 学号 专业班级 完成时间 2016年月日 目录 一、系统功能介绍 (2) 二、需求分析 (2) 三、概要设计 (2) 四、详细设计 (5) 五、调试分析 (8) 六、使用说明 (8) 七、测试结果 (9) 八、心得体会 (10) 九、附录（程序代码） (11) 一、系统功能介绍 该系统主要功能是实现二叉树的定义和基本操作，包括定义二叉树的结构类型以及各个操作的具体函数的定义和主函数的定义。 各操作主要包括：初始化二叉树、按先序次序建立二叉树、检查二叉树是否为空、前序、中序、后序遍历树的方式、求树的深度、求树的结点数目、清空二叉树等九个对树的操作。 二、需求分析 本系统通过函数调用实现二叉树初始化，建立二叉树，检查树空与否，用前序、中序、后序遍历二叉树，求树的深度，求树的结点数目，清空二叉树等功能。 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, 实验六：二叉树及其应用 一、实验目的 树是数据结构中应用极为广泛的非线性结构，本单元的实验达到熟悉二叉树的存储结构的特性，以及如何应用树结构解决具体问题。 二、问题描述 首先，掌握二叉树的各种存储结构和熟悉对二叉树的基本操作。其次，以二叉树表示算术表达式的基础上，设计一个十进制的四则运算的计算器。 如算术表达式：a+b*(c-d)-e/f 三、实验要求 如果利用完全二叉树的性质和二叉链表结构建立一棵二叉树，分别计算统计叶子结点的个数。求二叉树的深度。十进制的四则运算的计算器可以接收用户来自键盘的输入。由输入的表达式字符串动态生成算术表达式所对应的二叉树。自动完成求值运算和输出结果。四、实验环境 PC微机 DOS操作系统或 Windows 操作系统 Turbo C 程序集成环境或 Visual C++ 程序集成环境 五、实验步骤 1、根据二叉树的各种存储结构建立二叉树； 2、设计求叶子结点个数算法和树的深度算法； 3、根据表达式建立相应的二叉树，生成表达式树的模块； 4、根据表达式树，求出表达式值，生成求值模块； 5、程序运行效果，测试数据分析算法。 六、测试数据 1、输入数据：*（+）3 正确结果： 2、输入数据：(1+2)*3+(5+6*7); 正确输出：56 七、表达式求值 由于表达式求值算法较为复杂，所以单独列出来加以分析： 1、主要思路：由于操作数是任意的实数，所以必须将原始的中缀表达式中的操作数、操作符以及括号分解出来，并以字符串的形式保存；然后再将其转换为后缀表达式的顺序，后缀表达式可以很容易地利用堆栈计算出表达式的值。 例如有如下的中缀表达式： a+b-c 转换成后缀表达式为： ab+c- 然后分别按从左到右放入栈中，如果碰到操作符就从栈中弹出两个操作数进行运算，最后再将运算结果放入栈中，依次进行直到表达式结束。如上述的后缀表达式先将a 和b 放入栈中，然后碰到操作符“+”，则从栈中弹出a 和b 进行a+b 的运算，并将其结果d（假设为d）放入栈中，然后再将c 放入栈中，最后是操作符“-”，所以再弹出d和c 进行d-c 运算，并将其结果再次放入栈中，此时表达式结束，则栈中的元素值就是该表达式最后的运算结果。当然将原始的中缀表达式转换为后缀表达式比较关键，要同时考虑操作符的优先级以及对有括号的情况下的处理，相关内容会在算法具体实现中详细讨论。 2、求值过程 一、将原始的中缀表达式中的操作数、操作符以及括号按顺序分解出来，并以字符串的 形式保存。 二、将分解的中缀表达式转换为后缀表达式的形式，即调整各项字符串的顺序，并将括 号处理掉。 三、计算后缀表达式的值。 3、中缀表达式分解 DivideExpressionToItem()函数。分解出原始中缀表达式中的操作数、操作符以及括号，保存在队列中，以本实验中的数据为例，分解完成后队列中的保存顺序如下图所示： 《数据结构与数据库》 实验报告 实验题目 二叉树的基本操作及运算 一、需要分析 问题描述： 实现二叉树（包括二叉排序树）的建立，并实现先序、中序、后序和按层次遍历，计算叶子结点数、树的深度、树的宽度，求树的非空子孙结点个数、度为2的结点数目、度为2的结点数目，以及二叉树常用运算。 问题分析： 二叉树树型结构是一类重要的非线性数据结构，对它的熟练掌握是学习数据结构的基本要求。由于二叉树的定义本身就是一种递归定义，所以二叉树的一些基本操作也可采用递归调用的方法。处理本问题，我觉得应该： 1、建立二叉树； 2、通过递归方法来遍历（先序、中序和后序）二叉树； 3、通过队列应用来实现对二叉树的层次遍历； 4、借用递归方法对二叉树进行一些基本操作，如：求叶子数、树的深度宽度等； 5、运用广义表对二叉树进行广义表形式的打印。 算法规定： 输入形式：为了方便操作，规定二叉树的元素类型都为字符型，允许各种字符类型的输入，没有元素的结点以空格输入表示，并且本实验是以先序顺序输入的。 输出形式：通过先序、中序和后序遍历的方法对树的各字符型元素进行遍历打印，再以广义表形式进行打印。对二叉树的一些运算结果以整型输出。 程序功能：实现对二叉树的先序、中序和后序遍历，层次遍历。计算叶子结点数、树的深度、树的宽度，求树的非空子孙结点个数、度为2的结点数目、度为2的结点数目。对二叉树的某个元素进行查找，对二叉树的某个结点进行删除。 测试数据：输入一：ABC□□DE□G□□F□□□（以□表示空格）,查找5,删除E 预测结果：先序遍历ABCDEGF 中序遍历CBEGDFA 后序遍历CGEFDBA 层次遍历ABCDEFG 广义表打印A（B（C,D（E（,G）,F））） 叶子数3 深度5 宽度2 非空子孙数6 度为2的数目2 度为1的数目2 查找5，成功，查找的元素为E 删除E后，以广义表形式打印A（B（C,D（,F））） 输入二：ABD□□EH□□□CF□G□□□（以□表示空格）,查找10,删除B 预测结果：先序遍历ABDEHCFG 中序遍历DBHEAGFC 后序遍历DHEBGFCA 层次遍历ABCDEFHG 广义表打印A（B(D,E(H)),C(F(,G))） 叶子数3 深度4 宽度3 非空子孙数7 度为2的数目2 度为1的数目3 查找10，失败。 题目： 编程实现二叉查找树的建立、中序遍历、元素查找等功能，要求解释实现过程及演示实际例子的运行结果。 算法描述： 首先创建二叉树结点类，其主要包括：二叉树结点数据域，指向左、右子树的指针，构造函数，设置当前结点左、右子树、数据域以及判断当前结点是否为叶子结点等。然后进行二叉树类定义，其私有部分为定义二叉树根结点指针，公有部分主要包括：构造函数、析构函数、判断二叉树是否为空树、先，中，后序遍历的递归与非递归、二叉树删除、层序遍历以及二叉树搜索等。接下来将对一些重要函数算法进行描述： 1、isLeaf函数：若该结点的左子树和右子树都为空，则为叶子结点。 2、isEmpty函数：根结点为空则为空树。 3、Parent函数：首先判断给定结点是否有双亲，根结点和空结点一定无双亲，初始化一个临时变量，用于跟进查找双亲结点，查找到后其保存的便是双亲结点。先递归在左子树中查找，如果找到，便结束递归且返回双亲结点指针；如果没有找到，再递归在右子树中查找。如果都没有找到，说明给定结点的双亲结点不在该二叉树中。 4、LeftSibling（RightSibling）函数：首先找到当前结点的双亲，然后判断双亲结点左右子树是否为空，其中必然有一个不为空，返回另一个子树指针即可。 5、DeleteBinaryTree函数：首先判断是否为空树，若为空，则返回，然后递归删除左子树，递归删除右子树，最后删除根结点。 6、PreOrder函数：首先判断是否为空树，若为空，则返回，然后访问根结点，递归遍历左子树，递归遍历右子树，结束。 7、PreOrderWithoutRecusion函数：使用栈来模拟递归过程，首先申请栈，用于保存结点指针序列，申请指针pointer保存当前根指针，然后判断栈是否为空，若栈为空且pointer为空，跳出函数，否则若pointer不为空，访问pointer所指结点，pointer入栈，pointer指向其左子树；若pointer为空，弹出栈顶元素赋给pointer，pointer指向其右子树，结束。 8、CreateTree函数：采用先序遍历序列构造二叉树，设‘0’为空结点，输入非‘0’数，生成新结点，递归创建左子树和右子树。 9、Search函数：采用先序遍历查找给定元素是否在二叉树中，首先判断树是否是空树，若是空树，则返回空指针。然后初始化临时指针temp，查找成功后temp即为所给元素所在 本程序由SOGOF完成 该完整程序主要是递归函数的使用及模板的使用，完成了对二叉树基本的链表操作，主要有二叉树的建立，前序、中序、后序遍历，求树的高度，每层结点数（包含树的最大宽度），左右结点对换，二叉树的内存释放，求解树的叶子数。 #include 学生实验报告 学院：软通学院 课程名称：数据结构与算法 专业班级：软件142 班 姓名：邹洁蒙 学号： 0143990 学生实验报告 （二） 一、实验综述 1、实验目的及要求 目的：1）掌握树与二叉树的基本概念； 2）掌握二叉树的顺序存储，二叉链表的先序遍历中序遍历和后序遍历算法； 3）掌握树的双亲表示法。 要求：1）编程：二叉树的顺序存储实现； 2）编程：二叉链表的先序遍历中序遍历和后序遍历实现； 3）编程：树的双亲表示法实现。 2、实验仪器、设备或软件 设备：PC 软件：VC6 二、实验过程(编程，调试，运行；请写上源码，要求要有注释) 1.编程：二叉树的顺序存储实现 代码： BiTree::BiTree()//建立存储空间 { data = new int[MAXSIZE]; count = 0; } void BiTree::AddNode(int e)//加结点 { int temp = 0; data[count] = e; count++;//从编号0开始保存 } 运行截图： 2.编程：二叉链表的先序遍历中序遍历和后序遍历实现代码： void InOrderTraverse(BiTree* Head)//中序遍历 { if (Head) { InOrderTraverse(Head->LeftChild); cout << Head->data<<" "; InOrderTraverse(Head->RightChild); } } void PreOrderTraverse(BiTree* Head)//先序遍历 { if (Head) { cout << Head->data << " "; PreOrderTraverse(Head->LeftChild); PreOrderTraverse(Head->RightChild); } } void PostOrderTraverse(BiTree* Head)//后序遍历 { if (Head) { PostOrderTraverse(Head->LeftChild); PostOrderTraverse(Head->RightChild); cout << Head->data << " "; } } 运行截图： 浙江大学城市学院实验报告 课程名称数据结构基础 实验项目名称实验十二叉树的基本操作 学生姓名专业班级学号 实验成绩指导老师（签名）日期2014-12-18 一.实验目的和要求 1、掌握二叉树的链式存储结构。 2、掌握在二叉链表上的二叉树操作的实现原理与方法。 3、进一步掌握递归算法的设计方法。 二.实验内容 1、按照下面二叉树二叉链表的存储表示，编写头文件binary_tree.h，实现二叉链表的定义与基本操作实现函数；编写主函数文件test4_1.cpp，验证头文件中各个操作。 二叉树二叉链表存储表示如下： struct BTreeNode { ElemType data; // 结点值域 BTreeNode *lchild , *rchild ; // 定义左右孩子指针 } ; 基本操作如下： ①void InitBTree( BTreeNode *&BT ); //初始化二叉树BT ②void CreateBTree( BTreeNode *&BT, char *a ); //根据字符串a所给出的广义表表示的二叉树建立二叉链表存储结构 ③int EmptyBTree( BTreeNode *BT); //检查二叉树BT是否为空，空返回1，否则返回0 ④int DepthBTree( BTreeNode *BT); //求二叉树BT的深度并返回该值 ⑤int FindBTree( BTreeNode *BT, ElemType x); //查找二叉树BT中值为x的结点，若查找成功返回1，否则返回0 ⑥void PreOrder( BTreeNode *BT); //先序遍历二叉树BT ⑦void InOrder( BTreeNode *BT); //中序遍历二叉树BT ⑧void PostOrder( BTreeNode *BT); //后序遍历二叉树BT 算法与数据结构》课程实验报告 一、实验目的 1、实现二叉树的存储结构 2、熟悉二叉树基本术语的含义 3、掌握二叉树相关操作的具体实现方法 二、实验内容及要求 1. 建立二叉树 2. 计算结点所在的层次 3. 统计结点数量和叶结点数量 4. 计算二叉树的高度 5. 计算结点的度 6. 找结点的双亲和子女 7. 二叉树前序、中序、后序遍历的递归实现和非递归实现及层次遍历 8. 二叉树的复制 9. 二叉树的输出等 三、系统分析 （1）数据方面：该二叉树数据元素采用字符char 型，并且约定“ #”作为二叉树输入结束标识符。并在此基础上进行二叉树相关操作。 （2）功能方面：能够实现二叉树的一些基本操作，主要包括： 1. 采用广义表建立二叉树。 2. 计算二叉树高度、统计结点数量、叶节点数量、计算每个结点的度、结点所在层次。 3. 判断结点是否存在二叉树中。 4. 寻找结点父结点、子女结点。 5. 递归、非递归两种方式输出二叉树前序、中序、后序遍历。 6. 进行二叉树的复制。 四、系统设计 （1）设计的主要思路 二叉树是的结点是一个有限集合，该集合或者为空，或者是由一个根节点加上两棵分别称为左子树和右子树、互不相交的二叉树组成。根据实验要求，以及课上老师对于二叉树存储结构、基本应用的讲解，同时课后研究书中涉及二叉树代码完成二叉树模板类，并将所需实现各个功能代码编写完成，在建立菜单对功能进行调试。 （2）数据结构的设计 二叉树的存储结构有数组方式和链表方式。但用数组来存储二叉树有可能会消耗大量的存储空间，故在此选用链表存储，提高存储空间的利用率。根据二叉树的定义，二叉 数据结构 实 验 报 告 1. 实验目的和内容： 掌握二叉树基本操作的实现方法2. 程序分析 2.1存储结构 链式存储 2．程序流程 2.3关键算法分析 算法一：Create(BiNode 算法三：PreOrder(BiNode 实验五-二叉树基本操作的编程实现实验报告 ————————————————————————————————作者：————————————————————————————————日期： HUBEI UNIVERSITY OF AUTOMOTIVE TECHNOLOGY 数据结构 实验报告 这里一定填 写清楚自己 实验项目实验五实验类别基础篇 学生姓名朱忠栋学生学号20120231515 完成日期2014-12-16 指导教师付勇智 实验成绩评阅日期 评阅教师 实验五二叉树基本操作的编程实现 【实验目的】 内容：二叉树基本操作的编程实现 要求： 二叉树基本操作的编程实现（2学时，验证型），掌握二叉树的建立、遍历、插入、删除等基本操作的编程实现，也可以进一步编程实现查找等操作，存储结构主要采用顺序或链接结构。也鼓励学生利用基本操作进行一些应用的程序设计。 【实验性质】 验证性实验（学时数：2H） 【实验内容】 以下的选题都可以作为本次实验的推荐题目 1.建立二叉树，并以前序遍历的方式将结点内容输出。 2.将一个表示二叉树的数组结构转换成链表结构。 3.将表达式二叉树方式存入数组，以递归方式建立表达式之二叉树状结构，再分别输出前序、中序 及后序遍历结果，并计算出表达式之结果。 【注意事项】 1.开发语言：使用C。 2.可以自己增加其他功能。 【实验分析、说明过程】 页面不够，可续页。 根据自己选择的层次不同的实验内容，完善程序代码，调试通过后，分析说明该问题处理的详细算法过程。不需要写出详细的代码，只表达清楚详细的处理算法即可。可以采用流程图、形式语言或者其他数学表达方式来说明。 这次实验考查的主要是：递归建立二叉树，递归输出先序，中序和后序遍历的结果；非递归建立二叉树，再以非递归方式分别输出先序，中序和后序遍历的结果。 而对于基础篇考查的主要是：递归建立二叉树，递归输出先序，中序和后序遍历的结果，是以填空的方式进行考查的。 对于第一空：递归实现的先序遍历，其实现方法是： printf("%d",p->data); if(p->lchild!=NULL) preorder(p->lchild); if(p->rchild!=NULL) preorder(p->rchild); 对于第二空：递归实现的中序遍历，其实现方法是： if(p->lchild!=NULL) inorder(p->lchild); printf("%d",p->data); if(p->rchild!=NULL) inorder(p->rchild); 对于第三空：递归实现的后序遍历，其实现方法是： if(p->lchild!=NULL) postorder(p->lchild); if(p->rchild!=NULL) postorder(p->rchild); printf("%d",p->data); 【思考问题】 页面不够，可续页。 1.二叉树是树吗？它的定义为什么是递归的？ 答：最多有两棵子树的有序树，称为二叉树。二叉树是一种特殊的树。具有n个结点的完全二叉树的深度为log2n +1 ！！！二叉树的计算方法：若一棵二叉树为空,则其深度为0, 二叉树的基本操作实验报告 学号姓名实验日期 2012-12-26 实验室计算机软件技术实验指导教师设备编号 401 实验内容二叉树的基本操作 一实验题目 实现二叉树的基本操作的代码实现 二实验目的 1、掌握二叉树的基本特性 2、掌握二叉树的先序、中序、后序的递归遍历算法 3、通过求二叉树的深度、度为2的结点数和叶子结点数等算法三实习要求 (1)认真阅读书上给出的算法 (2)编写程序并独立调试 四、给出二叉树的抽象数据类型 ADT BinaryTree{ //数据对象D:D是具有相同特性的数据元素的集合。 //数据关系R: // 若D=Φ，则R=Φ，称BinaryTree为空二叉树; // 若D?Φ，则R={H}，H是如下二元关系; // (1)在D中存在惟一的称为根的数据元素root，它在关系H下无前驱; // (2)若D-{root}?Φ，则存在D-{root}={D1,Dr}，且D1?Dr =Φ; // (3)若D1?Φ，则D1中存在惟一的元素x1， // (4)(D1,{H1})是一棵符合本定义的二叉树，称为根的左子树;(Dr,{Hr})是一棵符合本定义的二叉树，称为根的右子树。 //基本操作: CreateBiTree( &T, definition ) // 初始条件:definition给出二叉树T的定义。 // 操作结果:按definiton构造二叉树T。 BiTreeDepth( T ) // 初始条件:二叉树T存在。 // 操作结果:返回T的深度。 PreOrderTraverse( T, visit() ) // 初始条件:二叉树T存在，Visit是对结点操作的应用函数。 // 操作结果:先序遍历T，对每个结点调用函数Visit一次且仅一次。一旦visit()失败，则操 作失败。 InOrderTraverse( T, visit() ) // 初始条件:二叉树T存在，Visit是对结点操作的应用函数。 // 操作结果:中序遍历T，对每个结点调用函数Visit一次且仅一次。一旦visit()失败，则操 作失败。 PostOrderTraverse( T, visit() ) // 初始条件:二叉树T存在，Visit是对结点操作的应用函数。 // 操作结果:后序遍历T，对每个结点调用函数Visit一次且仅一次。一旦visit()失败，则操 作失败。 LeafNodes(p) // 初始条件:二叉树T存在。 // 操作结果:返回T的叶子结点数。数据结构二叉树实验报告
实验三 二叉树的基本操作实现及其应用
二叉树的基本 操作
树和二叉树实验报告
二叉树的基本操作实验
二叉树的建立和遍历的实验报告doc
数据结构——二叉树基本操作源代码
二叉树实验报告及代码
二叉树基本操作+数据结构+实验报告
数据结构实验二叉树
数据结构实验三——二叉树基本操作及运算实验报告
二叉树实验报告
二叉树基本操作经典实例
数据结构实验报告之树与二叉树
实验10 二叉树的基本操作
数据结构实验报告—二叉树
数据结构二叉树的实验报告
实验五-二叉树基本操作的编程实现实验分析报告
二叉树的基本操作实验报告