实验3 二叉树及其应用
实验目的
1.加深对二叉树的结构特性的理解；
2.熟练掌握二叉树的存储结构，特别是二叉链表类的描述及其实现方法；
3.熟练掌握二叉树的遍历算法原理及实现；
4.学会编写实现二叉树的各种算法；
5.掌握二叉树的应用方法。
实验学时：建议2~4学时
实验内容
内容1：二叉树及其操作
【问题描述】
设计二叉树的二叉链表类，操作主要有建二叉树、遍历二叉树、求该二叉树中、的结点个数等。
【基本要求】
（1）建立二叉树可用先序方式建立，也可根据二叉树的先序和中序序列建立。
（2）对二叉树的遍历可采用递归或非递归的算法。
【实现提示】
（1）二叉链表的结点结构描述
struct btnode{ // 定义结点类型
ElemType data; //数据域
btnode * lchild，* rchild; //左、右指针域/
}; // btnode
（2）可设计以下功能函数：
btnode* createbitree(); //建立二叉链表
void preorder(btnode* bt); //先序遍历二叉树
int sum(btnode* bt); //求二叉树中的结点个数
算法可用递归或非递归实现。
建立二叉树可用以下两种算法实现：
方案1：btnode * createBT ( ) //前序建树
{ bitree T; char ch;
cin >>ch ;
if(ch==’#’) return NULL; //二叉树为空
T=new BinTNode; //申请根结点
T->data=ch;
T->lchild=createBTpre(); //创建根的左子树
1
2
T->rchild=createBTpre(); //创建根的右子树 return T; }
方案2：btnode* createBT ( char *preorder, char *midorder) { //由前序preorder 和中序midorder 建树，返回根指针 if(strlen (preorder) ==0) return NULL; //空二叉树 T= new Node; //建立根结点 T->data=*preorder;
k=locate(midorder ， *preorder); //找根在中序中的位置 lmidorder=fetch(midorder,0,k); //左子树的中序 lpreorder =fetch(preorder,1,k); //左子树的前序 rmidorder=fetch(midorder,k+1); //右子树的中序 rpreorder =fetch(preorder, k+1); //右子树的前序 T->lchild=createBT (lmidorder , lpreorder);//建根的左子树 T->rchild=createBT(rmidorder , rpreorder); //建根的右子树 return T; }
int sum(btnode* bt) //求二叉树中的结点个数 { if(!bt) return 0; //二叉树为空
return sum(bt->lchild) + sum(bt->rchild) +1; }
【选做内容】
（1） 对二叉树进行层次遍历算法。 （2） 求二叉树的深度、宽度等操作。
（3） 复制二叉树，交换二叉树中左右子树的问题怎么实现? 内容2：哈夫曼编码/译码器
【问题描述】设字符集为26个英文字母，其出现频度如下表所示。先建哈夫曼树，再利用此树对报文“This program is my favorite”进行编码和译码。 51 48 1 15 63 57 20 32 5 1 频度
z y x w v u t 字符
1 16
1
18
8
23
80
频度
p 21 f q
15 g r 47 h s o n m l k j 字符 57 103 32 22 13 64 186 频度 i e d c b a 空格
字符
【基本要求】
算法具有以下功能：
（1）CreateHuffmanTree：根据给定字符的出现频数，建立其哈夫曼树。
（2）Encoding：对给定的原字符串进行编码。
（3）Decoding：对给定的编码串进行译码（或解码）。
（4）ShowHuffmanTree：显示哈夫曼树
【实现提示】
（1）用户界面可设计成模拟菜单方式。
（2）原字符串及编码串可从键盘输入。
（3）生成Huffman树的步骤如下：
①由给定的n 个权值{w1, w2, …, wn}构成n棵二叉树的集合（即森林）F =
{ T1, T2, …, Tn }，其中每棵二叉树Ti 中只有一个带权为wi 的根结点，
其左右子树均空。
②在 F 中选取两棵根结点的权值最小的树做为左右子树构造一棵新的二叉
树，且置新的二叉树的根结点的权值为其左右子树上根结点的权值之和。
③在F 中删去这两棵树，同时将新得到的二叉树加入F中。
④重复②和③, 直到 F 只含一棵树为止。这棵树便是赫夫曼树。
【选做内容】
（1）字符的出现频数能否从指定文件中统计而得？
（2）对指定的文件进行编码/解码。
3
实验三二叉树的遍历 一、实验目的 １、熟悉二叉树的结点类型和二叉树的基本操作。 ２、掌握二叉树的前序、中序和后序遍历的算法。 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); }
实验3 二叉树及其应用 实验目的 1.加深对二叉树的结构特性的理解； 2.熟练掌握二叉树的存储结构，特别是二叉链表类的描述及其实现方法； 3.熟练掌握二叉树的遍历算法原理及实现； 4.学会编写实现二叉树的各种算法； 5.掌握二叉树的应用方法。 实验学时：建议2~4学时 实验内容 内容1：二叉树及其操作 【问题描述】 设计二叉树的二叉链表类，操作主要有建二叉树、遍历二叉树、求该二叉树中、的结点个数等。 【基本要求】 （1）建立二叉树可用先序方式建立，也可根据二叉树的先序和中序序列建立。 （2）对二叉树的遍历可采用递归或非递归的算法。 【实现提示】 （1）二叉链表的结点结构描述 struct btnode{ // 定义结点类型 ElemType data; //数据域 btnode * lchild，* rchild; //左、右指针域/ }; // btnode （2）可设计以下功能函数： btnode* createbitree(); //建立二叉链表 void preorder(btnode* bt); //先序遍历二叉树 int sum(btnode* bt); //求二叉树中的结点个数 算法可用递归或非递归实现。 建立二叉树可用以下两种算法实现： 方案1：btnode * createBT ( ) //前序建树 { bitree T; char ch; cin >>ch ; if(ch==’#’) return NULL; //二叉树为空 T=new BinTNode; //申请根结点 T->data=ch; T->lchild=createBTpre(); //创建根的左子树 1
实验题目：实验九——二叉树实验 算法设计（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 （）
实验三：二叉树 学时：2学时 实验目的：掌握树形结构的特点，二叉树的存储方式以及相应操作。 实验内容： 按先序遍历序列建立二叉树的二叉链表，已知先序序列为(F表示空格)：ABCFFDEFGFFFFFF。并写一个函数treenodes()统计该二叉树的节点个数。如果有可能，写一个输出函数treeprint()用树形结构打印出该二叉树。 提示： 1，统计结点数也是一种遍历操作，要首先理解遍历，递归程序。 2，由于printf打印是一行行按顺序的，要打印出树形结构，必须按层次遍历，并且利用空格。关键是控制每一层次打印的空格的数量，以及子树为空的情形。 可参考如下代码： 树的遍历：ch6_traverse.c /* 树的遍历 author: kk.h date: 2006.10 https://www.doczj.com/doc/1e16474343.html, */ #include "stdio.h" typedef char ElemType; typedef struct BiTNode{ ElemType data; struct BiTNode *lchild,*rchild; }BiTNode; /* 先根遍历*/ void preorder(BiTNode *bt) { if(bt!=NULL) { printf("%c ",bt->data); preorder(bt->lchild); preorder(bt->rchild); } } /* 中根遍历*/ void inorder(BiTNode *bt) { if(bt!=NULL) { inorder(bt->lchild);
printf("%c ",bt->data); inorder(bt->rchild); } } /* 后根遍历*/ void postorder(BiTNode *bt) { if(bt!=NULL) { postorder(bt->lchild); postorder(bt->rchild); printf("%c ",bt->data); } } /* 非递归算法的中根遍历（后进先出，用了栈的思想）*/ void inorder_fdg(BiTNode *bt) { int i=0; BiTNode *p,*s[20]; p=bt; do { while(p!=NULL) { s[i++]=p; p=p->lchild; } if(i>0) { p=s[--i]; printf("%c ",p->data); p=p->rchild; } }while(i>0||p!=NULL); } /* 用队列实现层次遍历*/ void lev_traverse(BiTNode* T) { BiTNode *q[100],*p; int head,tail, i; q[0]=T;head=0;tail=1; while(head
二叉树的建立和遍历的实验报告 篇一：二叉树的建立及遍历实验报告 实验三：二叉树的建立及遍历 【实验目的】 （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))))
实验六：二叉树及其应用 一、实验目的 树是数据结构中应用极为广泛的非线性结构，本单元的实验达到熟悉二叉树的存储结构的特性，以及如何应用树结构解决具体问题。 二、问题描述 首先，掌握二叉树的各种存储结构和熟悉对二叉树的基本操作。其次，以二叉树表示算术表达式的基础上，设计一个十进制的四则运算的计算器。 如算术表达式：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()函数。分解出原始中缀表达式中的操作数、操作符以及括号，保存在队列中，以本实验中的数据为例，分解完成后队列中的保存顺序如下图所示：
《数据结构》第六次实验报告 学生姓名 学生班级 学生学号 指导老师
一、实验内容 1) 采用二叉树链表作为存储结构，完成二叉树的建立，先序、中序和后序 以及按层次遍历的操作，求所有叶子及结点总数的操作。 2) 输出树的深度，最大元，最小元。 二、需求分析 遍历二叉树首先有三种方法，即先序遍历，中序遍历和后序遍历。 递归方法比较简单，首先获得结点指针如果指针不为空，且有左子，从左子递归到下一层，如果没有左子，从右子递归到下一层，如果指针为空，则结束一层递归调用。直到递归全部结束。 下面重点来讲述非递归方法： 首先介绍先序遍历： 先序遍历的顺序是根左右，也就是说先访问根结点然后访问其左子再然后访问其右子。具体算法实现如下：如果结点的指针不为空，结点指针入栈，输出相应结点的数据，同时指针指向其左子，如果结点的指针为空，表示左子树访问结束，栈顶结点指针出栈，指针指向其右子，对其右子树进行访问，如此循环，直至结点指针和栈均为空时，遍历结束。 再次介绍中序遍历： 中序遍历的顺序是左根右，中序遍历和先序遍历思想差不多，只是打印顺序稍有变化。具体实现算法如下：如果结点指针不为空，结点入栈，指针指向其左子，如果指针为空，表示左子树访问完成，则栈顶结点指针出栈，并输出相应结点的数据，同时指针指向其右子，对其右子树进行访问。如此循环直至结点指针和栈均为空，遍历结束。 最后介绍后序遍历： 后序遍历的顺序是左右根，后序遍历是比较难的一种，首先需要建立两个栈，一个用来存放结点的指针，另一个存放标志位，也是首先访问根结点，如果结点的指针不为空，根结点入栈，与之对应的标志位也随之入标志位栈，并赋值0，表示该结点的右子还没有访问，指针指向该结点的左子，如果结点指针为空，表示左子访问完成，父结点出栈，与之对应的标志位也随之出栈，如果相应的标志位值为0，表示右子树还没有访问，指针指向其右子，父结点再次入栈，与之对应的标志位也入栈，但要给标志位赋值为1，表示右子访问过。如果相应的标志位值为1，表示右子树已经访问完成，此时要输出相应结点的数据，同时将结点指针赋值为空，如此循环直至结点指针和栈均为空，遍历结束。 三、详细设计 源代码：
江南大学通信与控制工程学院标准实验报告 （实验）课程名称：计算机软件技术基础实验名称：二叉树的遍历和应用 班级：自动化 姓名：李玉书 学号：03 指导教师：卢先领 江南大学通信与控制学院
江南大学 实验报告 学生姓名：张晓蔚学号：0704090304 实验地点：信控机房实验时间：90分钟 一、实验室名称：信控学院计算中心 二、实验项目名称：二叉树的遍历和应用 三、实验学时：4学时 四、实验原理： 二叉树的遍历和应用 五、实验目的： 1、掌握二叉树的数据类型描述及特点。 2、掌握二叉树的存储结构（二叉链表）的建立算法。 3、掌握二叉链表上二叉树的基本运算的实现。 六、实验内容： 阅读后面的程序，并将其输入到计算机中，通过调试为下面的二叉树建立二叉链表，并用递归实现二叉树的先序、中序、后序三种遍历。 七、实验器材（设备、元器件）： 计算机 八、实验步骤： 1、输入示例程序 2、构建按序插入函数实现算法 3、用C语言实现该算法 4、与源程序合并，编译，调试 5、测试，查错，修改
6、生成可执行文件，通过综合测试，完成实验 九、实验数据及结果分析： 测试用例 初始数据：ABDH,,I,,EJ,,K,,CFL,,,G,, 测试结果 十、实验结论： 该程序可以完成线性表的常规功能，且增加了异常处理，在异常情况下，例如： 表空，删除结点号不合法或出界，删除数值未找到等，这些情况下都能作出处理。可以通过边界测试。 十一对本实验过程及方法、手段的改进建议： 对书中程序的几点错误做了改正，见源程序。 附：源程序 #include
实验8 二叉树的遍历与应用 一、实验目的 1.进一步掌握指针变量的含义。 2.掌握二叉树的结构特征，理解并熟悉掌握创建二叉树和实现二叉树的三种遍历。 3.学会编写实现二叉树基本操作的递归算法，领会递归的实质。 二、实验要求 1. 给出程序设计的基本思想、原理和算法描述。 2. 源程序给出注释。 3. 保存和打印出程序的运行结果，并结合程序进行分析。 三、实验题目 1.编写算法，按层输出一棵顺序存储的二叉树所有结点的值。 /**********level.c************/ #include
重庆交通大学综合性设计性实验报告 班级：软件开发专业 2010级一班 实验项目名称：二叉树 实验项目性质：设计性实验 实验所属课程：数据结构 实验室(中心)： 6教 指导教师：鲁云平 实验完成时间： 2012 年 4 月 29 日
一、实验目的 主要完成以下功能: 1. 建立二叉树 2. 计算结点所在的层次 3 .统计结点数量和叶结点数量 4. 计算二叉树的高度 5. 计算结点的度 6. 找结点的双亲和子女 7. 二叉树的遍历 8. 二叉树的输出等等 二、实验内容及要求 1.二叉树的结点结构,二叉树的存储结构由学生自由选择和设定 2.实验完成后上交打印的实验报告,报告内容与前面所给定的实验模板相同 3.将实验报告电子版和源代码在网络教学平台提交 三、实验设备及软件 Visual studio 2010
四、设计方案 ㈠题目（老师给定或学生自定） 二叉树的简单应用 ㈡设计的主要思路 通过递归原理实现大部分遍历二叉树功能 ㈢主要功能 1. 建立二叉树 2. 计算结点所在的层次 3 .统计结点数量和叶结点数量 4. 计算二叉树的高度 5. 计算结点的度 6. 找结点的双亲和子女 7. 二叉树的遍历 8. 二叉树的输出 五、主要代码 栈头文件：stack.h class Stack { public: Stack(int sz=100); ~Stack(){delete[]elements;} void Push(const T &x); bool Pop(T &x); bool getTop(T &x); bool IsEmpty()const{return(top==-1)?true:false;} bool IsFull()const{return(top==maxSize-1)?true:false;} private: T *elements; int top;
二叉树实验报告 09信管石旭琳 20091004418 一、实验目的： 1、理解二叉树的遍历算法及应用 2、理解哈夫曼树及其应用。 3、掌握哈夫曼编码思想。 二、实验内容： 1、建立二叉树二叉链表 2、实现二叉树递归遍历算法（中序、前序、后序） 3、求二叉树高度 4、求二叉树结点个数 5、求二叉树叶子个数 6、将序号为偶数的值赋给左子树 三、主要程序： #include
实验3 树和二叉树 实验性质：验证性 实验学时：4学时 一、实验目的 1.掌握二叉树的特点、在计算机中的存储表示方法及其基本操作的实现； 2.能够利用二叉树求解一些常见问题。 二、实验预备知识 1.阅读并掌握二叉树二叉链表存储方法的类型定义及其创建、遍历等基本操作。 2.阅读并掌握赫夫曼树的创建、赫夫曼编码的求得等基本操作。 三、实验内容 1.理解并用二叉链表的操作运行下列程序： #include 二叉树的遍历实验报告 一、需求分析 在二叉树的应用中，常常要求在树中查找具有某种特征的结点，或者对树中全部结点逐一进行某种处理，这就是二叉树的遍历问题。 对二叉树的数据结构进行定义，建立一棵二叉树，然后进行各种实验操作。 二叉树是一个非线性结构，遍历时要先明确遍历的规则，先访问根结点还时先访问子树，然后先访问左子树还是先访问有右子树，这些要事先定好，因为采用不同的遍历规则会产生不同的结果。本次实验要实现先序、中序、后序三种遍历。 基于二叉树的递归定义，以及遍历规则，本次实验也采用的是先序遍历的规则进行建树的以及用递归的方式进行二叉树的遍历。 二、系统总框图 三、各模块设计分析 （1）建立二叉树结构 建立二叉树时，要先明确是按哪一种遍历规则输入，该二叉树是按你所输入的遍历规则来建立的。本实验用的是先序遍历的规则进行建树。 二叉树用链表存储来实现，因此要先定义一个二叉树链表存储结构。因此要先定义一个结构体。此结构体的每个结点都是由数据域data 、左指针域Lchild 、右指针域Rchild 组成，两个指针域分别指向该结点的左、右孩子，若某结点没有左孩子或者右孩子时，对应的指针域就为空。最后，还需要一个链表的头指针指向根结点。 要注意的是，第一步的时候一定要先定义一个结束标志符号，例如空格键、＃等。当它遇到该标志时，就指向为空。 建立左右子树时，仍然是调用create （）函数，依此递归进行下去， 直到遇到结束标志时停止操作。 （2）输入二叉树元素 输入二叉树时，是按上面所确定的遍历规则输入的。最后，用一个返回值来表示所需要的结果。 （3）先序遍历二叉树 当二叉树为非空时，执行以下三个操作：访问根结点、先序遍历左子树、先序遍历右子树。 （4）中序遍历二叉树 当二叉树为非空时，程序执行以下三个操作：访问根结点、先序遍历左子树、先序遍历右子树。 （5）后序遍历二叉树 当二叉树为非空时，程序执行以下三个操作：访问根结点、先序遍历左子树、先序遍历右子树。 （6）主程序 需列出各个函数，然后进行函数调用。 四、各函数定义及说明 因为此二叉树是用链式存储结构存储的，所以定义一个结构体用以存储。 typedef struct BiTNode { char data; struct BiTNode *Lchild; struct BiTNode *Rchild; 南昌大学实验报告 学生姓名：李木子学号：专业班级：软工 实验类型：□验证□综合□设计□创新实验日期：实验成绩：一、实验项目名称 二叉树的遍历 二、实验目的 学会链式二叉树的结构体定义，创建与前序中序后序遍历三、实验基本原理 四、主要仪器设备及耗材 电脑， 五、实验步骤 ************************************** * 链式二叉树的创建与遍历 * ************************************** ************************************** * 链式二叉树的结构体定义 * ************************************** <> <> ; { ; *; *; }; ************************************** * 链式二叉树函数声明 * ************************************** *(); (*); (*); (*); ************************************** * 链式二叉树创建函数 * ************************************** *() { ; *; (); ('') ; ('\'); { (*)(()); >; >(); >(); } ; } ************************************** * 链式二叉树递归前序遍历函数 * ************************************** (*) { () { ("\">); 题目： 编程实现二叉查找树的建立、中序遍历、元素查找等功能，要求解释实现过程及演示实际例子的运行结果。 算法描述： 首先创建二叉树结点类，其主要包括：二叉树结点数据域，指向左、右子树的指针，构造函数，设置当前结点左、右子树、数据域以及判断当前结点是否为叶子结点等。然后进行二叉树类定义，其私有部分为定义二叉树根结点指针，公有部分主要包括：构造函数、析构函数、判断二叉树是否为空树、先，中，后序遍历的递归与非递归、二叉树删除、层序遍历以及二叉树搜索等。接下来将对一些重要函数算法进行描述： 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即为所给元素所在 竭诚为您提供优质文档/双击可除二叉树的建立和遍历的实验报告 篇一：二叉树遍历实验报告 数据结构实验报告 报告题目：二叉树的基本操作学生班级： 学生姓名：学号： 一．实验目的 1、基本要求：深刻理解二叉树性质和各种存储结构的特点及适用范围；掌握用指针类型描述、访问和处理二叉树的运算；熟练掌握二叉树的遍历算法；。 2、较高要求:在遍历算法的基础上设计二叉树更复杂操作算法；认识哈夫曼树、哈夫曼编码的作用和意义;掌握树与森林的存储与便利。二.实验学时： 课内实验学时：3学时课外实验学时：6学时三．实验题目 1．以二叉链表为存储结构，实现二叉树的创建、遍历（实验类型：验证型）1）问题描述：在主程序中设计一个简单的菜单，分别调用相应的函数功能：1…建立树2…前序 遍历树3…中序遍历树4…后序遍历树5…求二叉树的高度6…求二叉树的叶子节点7…非递归中序遍历树0…结束2）实验要求：在程序中定义下述函数，并实现要求的函数功能：createbinTree(binTree structnode*lchild,*rchild; }binTnode;元素类型： intcreatebinTree(binTree voidpreorder(binTreevoidInorder(binTree voidpostorder(binTreevoidInordern(binTreeintleaf(bi nTree intpostTreeDepth(binTree 2、编写算法实现二叉树的非递归中序遍历和求二叉树高度。1）问题描述：实现二叉树的非递归中序遍历和求二叉树高度2）实验要求：以二叉链表作为存储结构 3)实现过程： 1、实现非递归中序遍历代码： voidcbiTree::Inordern(binTreeinttop=0;p=T;do{ while(p!=nuLL){ stack[top]=p;;top=top+1;p=p->lchild;}; if(top>0){ top=top-1;p=stack[top]; 实验二叉树遍历算法及应用 实验报告二叉树的遍历应用算法测试实验日期:______________ 学生姓 名:______________ 班级:_______________ 一、实习目的: 1、深入了解二叉树的存储结构及二叉树的遍历方法; 2、掌握二叉树的遍历算法及应用。 二、实习内容及要求 ----------------------------------------------------------------------------------------------------------------------------------------- 应用遍历思想，建立一棵如下图所示的二叉树，并能够完成如下操作: 1. 输出该二叉树的先序、中序、后序遍历序列; 2. 拷贝该树，生成一棵新树; 3. 将原树拆分成左右2棵树，并分别输出该二叉树左子树的遍历序列和右子树的遍历序列; 4. 利用遍历算法输出复制生成的树中结点总数、叶子总数、二叉树高度，并能够输出此二叉树中的叶子 结点。 ----------------------------------------------------------------------------------------------------------------------------------------- 附加:应用二叉树的顺序存储结构，实现建树。 并设计一个算法，实现能够输入一棵树中的双亲结点，输出该双亲结点的所有孩子结点的算法。 三、数据结构设计 (请将数据结构设计填写在此部分。) 四、测试 分别给出以下三棵树的测试结果 问题一：二叉树遍历 1.问题描述 设输入该二叉树的前序序列为： ABC##DE#G##F##HI##J#K##（#代表空子树） 请编程完成下列任务： ⑴请根据此输入来建立该二叉树，并输出该二叉树的前序、中序和后序序列； ⑵按层次遍历的方法来输出该二叉树按层次遍历的序列； ⑶求该二叉树的高度。 2.设计描述 （1）二叉树是一种树形结构，遍历就是要让树中的所有节点被且仅被访问一次，即按一定规律排列成一个线性队列。二叉（子）树是一种递归定义的结构，包含三个部分：根结点（N）、左子树（L）、右子树（R）。根据这三个部分的访问次序对二叉树的遍历进行分类，总共有6种遍历方案：NLR、LNR、LRN、NRL、RNL和LNR。研究二叉树的遍历就是研究这6种具体的遍历方案，显然根据简单的对称性，左子树和右子树的遍历可互换，即NLR与NRL、LNR与RNL、LRN 与RLN，分别相类似，因而只需研究NLR、LNR和LRN三种即可，分别称为“先序遍历”、“中序遍历”和“后序遍历”。采用递归方式就可以容易的实现二叉树的遍历，算法简单且直观。 （2）此外，二叉树的层次遍历即按照二叉树的层次结构进行遍历，按照从上到下，同一层从左到右的次序访问各节点。遍历算法可以利用队列来实现，开始时将整个树的根节点入队，然后每从队列中删除一个节点并输出该节点的值时，都将它的非空的左右子树入队，当队列结束时算法结束。 （3）计算二叉树高度也是利用递归来实现：若一颗二叉树为空，则它的深度为0，否则深度等于左右子树的最大深度加一。 3．源程序 1 2 3 4 5 6 7 8 9 10 11 12 13 14 #include 实验报告 课程名称数据结构 实验项目实验三--创建一个二叉树并输出三种遍历结果 系别___ _计算机学院 _ ______ 专业___ ___ 班级/学号___________ 学生姓名 _________ 实验日期_ 成绩_______________________ 指导教师 实验题目：实验三------创建一个二叉树并输出三种遍历结果 一、实验目的 1)掌握二叉树存储结构； 2)掌握并实现二叉树遍历的递归算法和非递归算法； 3)理解树及森林对二叉树的转换； 4)理解二叉树的应用—哈夫曼编码及WPL计算。 二、实验内容 1)以广义表或遍历序列形式创建一个二叉树，存储结构自选； 2)输出先序、中序、后序遍历序列； 3)二选一应用题：1）树和森林向二叉树转换；2）哈夫曼编码的应用问题。（应用型 题目可替换上述前两项实验内容） 三、设计与编码 1)程序结构基本设计框架 （提示：请根据所选定题目，描述程序的基本框架，可以用流程图、界面描述图、框图等来表示） 2)本实验用到的理论知识 遍历二叉树，递归和非递归的方法 （提示：总结本实验用到的理论知识，实现理论与实践相结合。总结尽量简明扼要，并与本次实验密切相关，要求结合自己的题目并阐述自己的理解和想法） 3)具体算法设计 （1）首先，定义二叉树的存储结构为二叉链表存储，每个元素的数据类型Elemtype，定义一棵二叉树，只需定义其根指针。 （2）然后以递归的先序遍历方法创建二叉树，函数为CreateTree()，在输入字符时要注意，当节点的左孩子或者右孩子为空的时候，应 当输入一个特殊的字符（本算法为“#”），表示左孩子或者右孩子为 空。 （3）下一步，创建利用递归方法先序遍历二叉树的函数，函数为PreOrderTree()，创建非递归方法中序遍历二叉树的函数，函数为 InOrderTree()，中序遍历过程是：从二叉树的根节点开始，沿左子树 向下搜索，在搜索过程将所遇到的节点进栈；左子树遍历完毕后， 从栈顶退出栈中的节点并访问；然后再用上述过程遍历右子树，依 次类推，指导整棵二叉树全部访问完毕。创建递归方法后序遍历二 叉树的函数，函数为LaOrderTree()。 （提示：该部分主要是利用C、C++等完成数据结构定义、设计算法实现各种操作，可以用列表分步形式的自然语言描述，也可以利用流程图等描述） 4)编码 #include 福建农林大学计算机与信息学院实验报告 树与二叉树 一、实验目的和要求 1)进一步掌握指针变量、动态变量的含义。 2)掌握二叉树的结构特性及各种存储结构的特点及适用范围。 3)掌握用指针类型描述、访问和处理二叉树的运算。 4)熟悉各种存储结构的特征及如何应用树结构解决具体问题。 二、实验内容和原理 实验内容： 编写程序实现交换二叉树中所有结点的左右子树的算法。 实验原理： 【问题描述】建立一棵二叉树，按层次遍历该二叉树，并实现将二叉树中所有结点的左右子树交换，显示其结果。 【基本要求】从键盘接受输入点（按层次遍历顺序），以“#”号结束，以二叉链表作为存储结构，将其二叉树中所有结点的左右子树交换，并将结果输出。 【实现】交换二叉树中所有结点的左右子树的具体步骤如下: ①将根结点进指针栈seqstack; ②当指针栈不空时，从栈顶取结点，如果此结点的左右孩子不为 空，则把其左右孩子交换，然后再分别将其左右孩子进栈； ③反复执行步骤②，直至指针栈为空时止。 三、实验环境 Windows XP系统 visual c++6.0 四、算法描述及实验步骤 #include "stdio.h" #include"stdlib.h" #define MAXSIZE 100 typedef char elemtype; typedef struct btnode {elemtype data; struct btnode *lchild, *rchild; }bitnode ,*bitree; typedef struct nodd {bitree addr; int parent; }sequre; bitree ins_node (bitree s,bitree t); void print_tree(bitree t); bitree creat_ordbt(); sequre seq[MAXSIZE]; void swap(bitree tree); int n=0; void main() {bitree tree; tree=creat_ordbt(); swap(tree); printf("输出交换后的二叉树\n"); print_tree(tree); } bitree creat_ordbt() {bitree t,s; elemtype x; t=NULL; printf("请按层次输入结点1的值(以#号结束，0号为空的结点)："); scanf("%c",&x); getchar(); while(x!='#') {n++;二叉树的遍历实验报告
数据结构实验二叉树的遍历
二叉树实验报告
二叉树的建立和遍历的实验报告
实验 二叉树遍历算法及应用
数据结构二叉树遍历实验报告
创建一个二叉树并输出三种遍历结果
数据结构实验报告-树与二叉树
相关主题
文本预览