二叉树操作实验报告
XX学院实验报告
五、实验总结和思考：（填写收获和体会，分析成功或失败的原因）
收获：只有通过不断练习，才能获取经验，避免下次犯同样的错误！
成功和失败：在实验过程中，遇到了一些细节性的问题，不好寻找，导致结果错误。结果：找到了问题所在，发现了一些平时不曾注意的问题。
附件：（源代码）
/* 说明
1、树的元素类型为字符形；
2、实现对二叉树的先序遍历操作；
3、实现对二叉树的中序遍历操作；
4、实现对二叉树的后序遍历操作；
5、求二叉树的深度；
6、求二叉树的叶结点数；
7、将二叉树中所有结点的左、右子树相互交换；*/
#include "stdio.h"
#include "conio.h"
#define OVERFLOW -1
typedef char telemtype;
typedef struct bitnode
{
telemtype data;
struct bitnode *lchild,*rchild;
}bitnode,*bitree;
void createbitree(bitree *t)
{
telemtype ch;
scanf("%c",&ch);
if(ch==' ') *t=NULL;
else
{
*t=(bitnode *)malloc(sizeof(bitnode));
if(!(*t)) exit(OVERFLOW);
(*t)->data=ch;
createbitree(&((*t)->lchild));
createbitree(&((*t)->rchild));
}
return;
}
void preordertraverse(bitree t)
{
if(t)
{
printf("%c ",t->data);
preordertraverse(t->lchild);
preordertraverse(t->rchild);
}
}
void inordertraverse(bitree t)
{
if(t)
{
inordertraverse(t->lchild);
printf("%c ",t->data);
inordertraverse(t->rchild);
}
}
void postordertraverse(bitree t)
{
if(t)
{
postordertraverse(t->lchild);
postordertraverse(t->rchild);
printf("%c ",t->data);
}
}
int height(bitree t)
{
if(t==NULL) return 0;
else
return((height(t->lchild))>(height(t->rchild))?((height(t->lchild))+1):((height(t->rchild))+1)); }
int leafnum(bitree t)
{
if(t==NULL) return 0;
else{
if((t->lchild==NULL)&&(t->rchild==NULL)) return 1;
else return(leafnum(t->lchild)+leafnum(t->rchild));
}
}
void changelr(bitree *t)
{
bitnode *p;
if(*t)
{
p=(*t)->lchild;(*t)->lchild=(*t)->rchild;(*t)->rchild=p;
changelr(&((*t)->lchild));
changelr(&((*t)->rchild));
}
return ;
}
int menu()
{
printf("\t\t\t**********************************************\n");
printf("\t\t\t*1.create the tree *\n");
printf("\t\t\t*2.preorder traverse the tree *\n");
printf("\t\t\t*3.inorder traver the tree *\n");
printf("\t\t\t*4.post traver the tree *\n");
printf("\t\t\t*5.the depth of the tree *\n");
printf("\t\t\t*6.the leafs of the tree *\n");
printf("\t\t\t*7.change the rchild and lchild of the tree *\n");
printf("\t\t\t*8.help *\n");
printf("\t\t\t*9.exit *\n");
printf("\t\t\t**********************************************\n");
printf("\n");
printf("please input your choice:");
}
main()
{ int a,i;
bitree t;
while(1){
menu();
scanf("%d",&a);
switch(a)
{
case 1: printf("please input the elem of the tree in preorder:\n");createbitree(&t);printf("\n");break;
case 2: printf("\n");preordertraverse(t);printf("\n");break;
case 3: printf("\n");inordertraverse(t);printf("\n");break;
case 4: printf("\n");postordertraverse(t);printf("\n");break;
case 5: printf("\n the depth of the tree is:");i=height(t);printf("%d\n",&i);break;
case 6: printf("\n the leafs of the tree is:");i=leafnum(t);printf("%d\n",&i);break;
case 7: printf("\n the tree after change the left and right is:"); preordertraverse(t);printf("\n");break;
case 8: printf("help");break;
case 9: exit(0);
}
}
getch();
}
树和二叉树的实验报告
《数据结构》实验报告 题目：树和二叉树
一、用二叉树来表示代数表达式 （一）需求分析 输入一个正确的代数表达式，包括数字和用字母表示的数，运算符号+ - * / ^ =及括号。系统根据输入的表达式建立二叉树，按照先括号里面的后括号外面的，先乘后除的原则，每个节点里放一个数字或一个字母或一个操作符，括号不放在节点里。分别先序遍历，中序遍历，后序遍历此二叉树，并输出表达式的前缀式，中缀式和后缀式。 （二）系统设计 1. 本程序中用到的所有抽象数据类型的定义； typedef struct BiNode 主程序的流程以及各程序模块之间的层次调用关系，函数的调用关系图： 3．列出各个功能模块的主要功能及输入输出参数 void push(char cc) 初始条件：输入表达式中的某个符号 操作结果：将输入的字符存入buf数组中去 BiTree Create_RTree() 初始条件：给出二叉树的定义表达式 操作结果：构造二叉树的右子树，即存储表达式等号右侧的字符组 BiTree Create_RootTree() 初始条件：给出二叉树的定义表达式
操作结果：构造存储输入表达式的二叉树，其中左子树存储‘X’，根节点存储‘：=’void PreOrderTraverse(BiTree T) 初始条件：二叉树T存在 操作结果：先序遍历T，对每个节点调用函数Visit一次且仅一次 void InOrderTraverse(BiTree T) 初始条件：二叉树T存在 操作结果：中序遍历T，对每个节点调用函数Visit一次且仅一次 void PostOrderTraverse(BiTree T) 初始条件：二叉树T存在 操作结果：后序遍历T，对每个节点调用函数Visit一次且仅一次 int main() 主函数，调用各方法，操作成功后返回0 （三）调试分析 调试过程中还是出现了一些拼写错误，经检查后都能及时修正。有些是语法设计上的小错误，比如一些参变量的初始值设置错误，使得程序调试出错。还有操作符优先级设计不够合理，在输出遍历表达式结果时有错误。在小组讨论分析后纠正了这些结果，并尽量改进了算法的性能，减小时间复杂度。 有输入表达式建立二叉树的时间复杂度为O(n),先序遍历和中序遍历及后序遍历的时间复杂度都为O(n). （四）测试结果 X：=(-b+(b^2-4*a*c)^/(2*a) （五）用户手册 打开界面后，根据提示，输入代数表达式，包括包括数字和用字母表示的数，运算符号+ - * / ^ =及括号。输入完毕回车后系统将显示表达式的前缀式，中缀式，后缀式。（六）附录 源程序： #include<>
实验三 二叉树的基本操作实现及其应用
二叉树的基本操作实现及其应用 一、实验目的 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 实验三二叉树的遍历 一、实验目的 １、熟悉二叉树的结点类型和二叉树的基本操作。 ２、掌握二叉树的前序、中序和后序遍历的算法。 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、熟练掌握二叉树的各种遍历算法。 二、实验内容 [问题描述] 建立一棵二叉树，试编程实现二叉树的如下基本操作： 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). // 对二叉树的基本操作的类模板封装 //------------------------------------------------------------------------------------------------------------------------ #include 实验题目：实验九——二叉树实验 算法设计（3） 问题分析： 1、题目要求：编写算法交换二叉树中所有结点的左右子树 2、设计思路：首先定义一个二叉树的数据类型，使用先序遍历建立该二叉树，遍历二叉树，设计左右子树交换的函数，再次遍历交换之后的二叉树，与先前二叉树进行比较。遍历算法与交换算法使用递归设计更加简洁。 3、测试数据： A、输入：1 2 4 0 0 5 0 0 3 0 0 交换前中序遍历：4 2 5 1 3 交换后中序遍历：3 1 5 2 4 交换前：交换后： B、输入：3 7 11 0 0 18 17 0 0 19 0 0 6 13 0 0 16 0 0 交换前中序遍历：11 7 17 18 19 3 13 6 16 交换后中序遍历：16 6 13 3 19 18 17 7 11 概要设计： 1、为了实现上述功能：①构造一个空的二叉树；②应用先序遍历输入，建立二叉树；③中序遍历二叉树；④调用左右子树交换函数；⑤中序遍历交换过后的二叉树。 2、本程序包括4个函数： ①主函数main（） ②先序遍历二叉树建立函数creat_bt（） ③中序遍历二叉树函数inorder（） ④左右子树交换函数 exchange（） 各函数间关系如下： 详细设计： 1、结点类型 typedef struct binode //定义二叉树 { int data; //数据域 struct binode *lchild,*rchild; //左孩子、右孩子 }binode,*bitree; 2、各函数操作 ① 先序遍历建二叉树函数 bitree creat_bt() { 输入结点数据； 判断是否为0{ 若是，为空； 不是，递归；} 返回二叉树； } ② 左右子树交换函数 void exchange(bitree t) { 判断结点是否为空{ 否，交换左右子树； 递归；} } ③ 中序遍历函数 void inorder(bitree bt) { 判断是否为空{ 递归左子树； 输出； 递归右子树；} } main （） creat_bt （） inorder （） exchange （） 实验六：二叉树及其应用 一、实验目的 树是数据结构中应用极为广泛的非线性结构，本单元的实验达到熟悉二叉树的存储结构的特性，以及如何应用树结构解决具体问题。 二、问题描述 首先，掌握二叉树的各种存储结构和熟悉对二叉树的基本操作。其次，以二叉树表示算术表达式的基础上，设计一个十进制的四则运算的计算器。 如算术表达式：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）掌握利用先序序列建立二叉树的二叉链表的过程。 （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)))) 重庆交通大学综合性设计性实验报告 姓名姚远学号 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 本程序由SOGOF完成 该完整程序主要是递归函数的使用及模板的使用，完成了对二叉树基本的链表操作，主要有二叉树的建立，前序、中序、后序遍历，求树的高度，每层结点数（包含树的最大宽度），左右结点对换，二叉树的内存释放，求解树的叶子数。 #include 二叉树的创建与遍历 一、试验内容 根据输入的字符串创建树或二叉树，输出树或二叉树的先序遍历和后序遍历序列。 二、运行环境 Visual C++ 三、需求分析 1、建立一棵用二叉链表方式存储的二叉树。 2、从键盘接受扩展先序序列，以二叉链表作为存储结构。 3、建立二叉树，并将遍历结果打印输出。采用递归和非递归两种 方法实现。 四、设计概要 //——————二叉树的二叉链表存储表示—————— typedef struct BiTBode{ TElemType data; Struct BiTNode *lchild, *rchild //左右孩子指针 }BiTNode, *BiTree; //—————基本操作的函数原型说明———————— Status CreateBiTree(BiTree &T); //按先序次序输入二叉树中结点的值（一个字符），空格字符表示空树。 //构造二叉树链表表示的二叉树T。 Status PreOrderTraverse(BiTree T, status(*visit)(TElemType e)); //采用二叉链表存储结构，visit是对结点操作的应用函数。 //先序遍历二叉树T，对每个结点调用函数visit一次且仅以次。 //一旦visit（）失败，则操作失败。 Status PostOrderTraverse(BiTree T, status(*visit)(TElemType e)); //采用二叉链表存储结构，visit是对结点操作的应用函数。 //后序遍历二叉树T，对每个结点调用函数visit一次且仅以次。 //一旦visit（）失败，则操作失败。 —————先序遍历二叉树基本操作的递归算法———— Status PreOrderTraverse(BiTree T,Status(*visit)(TElemType e)){ //采用二叉链表存储结构，visit是对数据元素操作的应用函数， 浙江大学城市学院实验报告 课程名称数据结构基础 实验项目名称实验十二叉树的基本操作 学生姓名专业班级学号 实验成绩指导老师（签名）日期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）建立二叉树结构 建立二叉树时，要先明确是按哪一种遍历规则输入，该二叉树是按你所输入的遍历规则来建立的。本实验用的是先序遍历的规则进行建树。 二叉树用链表存储来实现，因此要先定义一个二叉树链表存储结构。因此要先定义一个结构体。此结构体的每个结点都是由数据域data 、左指针域Lchild 、右指针域Rchild 组成，两个指针域分别指向该结点的左、右孩子，若某结点没有左孩子或者右孩子时，对应的指针域就为空。最后，还需要一个链表的头指针指向根结点。 要注意的是，第一步的时候一定要先定义一个结束标志符号，例如空格键、＃等。当它遇到该标志时，就指向为空。 建立左右子树时，仍然是调用create （）函数，依此递归进行下去， 直到遇到结束标志时停止操作。 （2）输入二叉树元素 输入二叉树时，是按上面所确定的遍历规则输入的。最后，用一个返回值来表示所需要的结果。 （3）先序遍历二叉树 当二叉树为非空时，执行以下三个操作：访问根结点、先序遍历左子树、先序遍历右子树。 （4）中序遍历二叉树 当二叉树为非空时，程序执行以下三个操作：访问根结点、先序遍历左子树、先序遍历右子树。 （5）后序遍历二叉树 当二叉树为非空时，程序执行以下三个操作：访问根结点、先序遍历左子树、先序遍历右子树。 （6）主程序 需列出各个函数，然后进行函数调用。 四、各函数定义及说明 因为此二叉树是用链式存储结构存储的，所以定义一个结构体用以存储。 typedef struct BiTNode { char data; struct BiTNode *Lchild; struct BiTNode *Rchild; 实验五-二叉树基本操作的编程实现实验报告 ————————————————————————————————作者：————————————————————————————————日期： 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的叶子结点数。 郑州轻工业学院数据结构实验报告 题目 学生姓名 学号 专业班级 完成时间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,数据结构二叉树实验报告
二叉树的基本操作实验
数据结构——二叉树基本操作源代码
二叉树实验报告
数据结构实验二叉树
数据结构实验三——二叉树基本操作及运算实验报告
二叉树的建立和遍历的实验报告doc
二叉树实验报告及代码
二叉树基本操作经典实例
二叉树实验报告
实验10 二叉树的基本操作
二叉树的遍历实验报告
实验五-二叉树基本操作的编程实现实验分析报告
二叉树的基本操作实验报告
二叉树基本操作+数据结构+实验报告