实验报告(二叉树)
实验报告
课程：数据结构(c 语言)
实验名称：二叉树的构建、基
本操作和遍历
姓名：
实验报告内容
验证性实验
一、预习准备：
实验目的：
1、 熟练掌握二叉树的结构特性，熟悉二叉树的各种存储结构的 特点及适用范围；
2、 熟练掌握二叉树的遍历方法及遍历算法；
3、掌握建立哈夫曼树和哈夫曼编码的方法及带权路径长度的计 算。 实验环境：Widow 操作系统、
实验原理：
1. 定义：
树：树(tree)是n(n>0)个结点的有限集T ,其中，有且仅有一个 特定的结点，称为树的根(root)。当n>1时，其余结点可分为
m(m>0个互不相交的有限集T1,T2,……Tn ,其中每一个集合本
系别：数字媒体技术
实验日期： 专业班级：媒体 161
组别：无
学号：
身又是一棵树，称为根的子树(subtree)
二叉树：二叉树是n(n>=0)个结点的有限集，它或为空树(n=0)，
或由一个根结点和两棵分别称为左子树和右子树的互不相交的
二叉树构成。
哈夫曼树：最优二叉树——赫夫曼树设有n个权值
{w1,w2, .... wn},构造一棵有n个叶子结点的二叉树，每个叶
子的权值为wi,则wpl最小的二叉树叫Huffman树。。
2. 特点：
树：树中至少有一个结点——根
树中各子树是互不相交的集合
二叉树：每个结点至多有二棵子树(即不存在度大于2的结点)二叉树的子树有左、右之分，且其次序不能任意颠倒哈夫曼树：一棵有n个叶子结点的Huffman树有2n-1个结点
采用顺序存储结构——动态分配数组存储
3. 表示：
遍历二叉树：
先序遍历：先访问根结点, 然后分别先序遍历左子树、右子
中序遍历：先中序遍历左子树，然后访问根结点，最后中序遍历右子树
后序遍历：先后序遍历左、右子树，然后访问根结点
按层次遍历：从上到下、从左到右访问各结点
构造Huffman 树的方法 ---- Huffman 算法
(1) ..................................................... 根据给定的n 个权值
{w1,w2, .............................................. w n},构造n 棵只有 根结
点的二叉树，令起权值为wj ;
(2) 在森林中选取两棵根结点权值最小的树作左右子树构 造一棵
新的二叉树，置新二叉树根结点权值为其左右子树根 结点权值之和；
(3) 在森林中删除这两棵树，同时将新得到的二叉树加入 森林中
重复上述两步，直到只含一棵树为止,这棵树即哈夫 曼树。
4. 实验内容和要求:
(1)二叉树
建立如下图所示的二叉树:
树；
3 、用户可由键盘输入数据实现对二叉树各结点的插入、
删除等操作； 4
、打印二叉树； 5
、对二叉树实现前序、中序、后序遍历;
算法思想: 建立一棵只有头结点的二叉树，并通过调用插入左子树和插入右 子树操作，依次将上图中的结点插入二叉树中，利用二叉树的特殊中 序遍历方法将该树以凹入表示法打印显示。最后，调用二叉树的前序、 中序、后序遍历函数对
要求:
2
二叉树进行遍历，并显示遍历结果。
⑵、哈夫曼树
设有字符集｛A、B、C D｝，各字符在电文中出现的次数集为｛1，3, 5, 7｝，设计各字符的哈夫曼编码。
要求：
1、构造字符集的哈夫曼树，其结点数据结构如下：
2、由哈夫曼树构造哈夫曼编码，输出权值及其对应的编码。算法思想：
首先，由给定的n个权值构造有2n-1个结点的哈夫曼树。在哈夫曼树中，其叶结点的权值为相应的给定权值，非叶结点的权值为其孩子结点的权值之和。
哈夫曼树构造过程如下：
1. 根据给定的n个权值｛wi，驱，…，w｝，构成的n棵二叉
树的森林F = ｛T 1, T2,…，Tn｝，其中每棵二叉树Ti中只有一
个权值为wi的结点，其左、右子树均为空；
2. 在F中选取根结点的权值最小和次小的两棵树作为左、右子树构造
一棵新的二叉树，且置新二叉树的根结点的权值为其左、右子树上根结
点的权值之和；
3. 在F中删除这两棵二叉树，并将新二叉树加入到F中；
4. 重复2和3，直到F中只含一棵树为止。这棵树就是哈夫曼树。
其次，对n个结点的哈夫曼树进行不等长编码。保证任何一个字符的哈夫曼编码不为另一字符的哈夫曼编码的前缀。
、实验过程:
实验中的关键语句：
前序遍历中序遍历什么的都是一个道理，只是输出的时候的顺序不同，都是先访问左孩子或者右孩子后在访问另一边
(1)先序遍历二叉树T的递归算法
Status PreOrderTraverse( BiTree T, Status(*Visit)(ElemType) ) { Status PrintElement( ElemType e ) {
printf( e );
return OK;
}
PreOrderTraverse(T, PrintElement);
if (T) {
if (Visit(T->data))
if (PreOrderTraverse(T->lchild, Visit))
if (PreOrderTraverse(T->rchild, Visit)) return OK;
return ERROR;
} else return OK;
} eight=a[i];
HTree[i].lchild=-1;
HTree[i].rchild=-1;
HTree[i].parent=-1;
}
static int k=0;
int bb[1000];
static int y;
int min=1000;
for(int jj=0;jj { if(HTree[jj].weight { min=HTree[jj].weight; static int x; x=jj; } } bb[k]=x; k++; int _min=1000; for(int jjj=0;jjj { int kk; for( kk=0;kk { if(jjj==bb[kk]) kk=k+2; } if(kk==k) { if(HTree[jjj].weight>=HTree[x].weight) { if(HTree[jjj].weight<_min) { _min=HTree[jjj].weight; y=jjj; } } } } } bb[k]=y; k++; HTree[x].parent=HTree[y].parent=n; HTree[n].weight=HTree[x].weight+HTree[y].weig ht; HTree[n].lchild=x; HTree[n].rchild=y; HTree[n].parent=-1; for(int ii=n+1;ii<2*n-1;ii++) { min=1000; for(int jj=0;jj { int kk; for( kk=0;kk { 实验三二叉树的遍历 一、实验目的 １、熟悉二叉树的结点类型和二叉树的基本操作。 ２、掌握二叉树的前序、中序和后序遍历的算法。 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.认真阅读和掌握本实验的程序。 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. 编写程序，实现二叉树的建立，并实现先序、中序和后序遍历。 如：输入先序序列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 实验题目：实验九——二叉树实验 算法设计（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 （） 题目： 编程实现二叉查找树的建立、中序遍历、元素查找等功能，要求解释实现过程及演示实际例子的运行结果。 算法描述： 首先创建二叉树结点类，其主要包括：二叉树结点数据域，指向左、右子树的指针，构造函数，设置当前结点左、右子树、数据域以及判断当前结点是否为叶子结点等。然后进行二叉树类定义，其私有部分为定义二叉树根结点指针，公有部分主要包括：构造函数、析构函数、判断二叉树是否为空树、先，中，后序遍历的递归与非递归、二叉树删除、层序遍历以及二叉树搜索等。接下来将对一些重要函数算法进行描述： 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即为所给元素所在 学生实验报告 学院：软通学院 课程名称：数据结构与算法 专业班级：软件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 << " "; } } 运行截图： 算法与数据结构》课程实验报告 一、实验目的 1、实现二叉树的存储结构 2、熟悉二叉树基本术语的含义 3、掌握二叉树相关操作的具体实现方法 二、实验内容及要求 1. 建立二叉树 2. 计算结点所在的层次 3. 统计结点数量和叶结点数量 4. 计算二叉树的高度 5. 计算结点的度 6. 找结点的双亲和子女 7. 二叉树前序、中序、后序遍历的递归实现和非递归实现及层次遍历 8. 二叉树的复制 9. 二叉树的输出等 三、系统分析 （1）数据方面：该二叉树数据元素采用字符char 型，并且约定“ #”作为二叉树输入结束标识符。并在此基础上进行二叉树相关操作。 （2）功能方面：能够实现二叉树的一些基本操作，主要包括： 1. 采用广义表建立二叉树。 2. 计算二叉树高度、统计结点数量、叶节点数量、计算每个结点的度、结点所在层次。 3. 判断结点是否存在二叉树中。 4. 寻找结点父结点、子女结点。 5. 递归、非递归两种方式输出二叉树前序、中序、后序遍历。 6. 进行二叉树的复制。 四、系统设计 （1）设计的主要思路 二叉树是的结点是一个有限集合，该集合或者为空，或者是由一个根节点加上两棵分别称为左子树和右子树、互不相交的二叉树组成。根据实验要求，以及课上老师对于二叉树存储结构、基本应用的讲解，同时课后研究书中涉及二叉树代码完成二叉树模板类，并将所需实现各个功能代码编写完成，在建立菜单对功能进行调试。 （2）数据结构的设计 二叉树的存储结构有数组方式和链表方式。但用数组来存储二叉树有可能会消耗大量的存储空间，故在此选用链表存储，提高存储空间的利用率。根据二叉树的定义，二叉 二叉树的创建与遍历 一、试验内容 根据输入的字符串创建树或二叉树，输出树或二叉树的先序遍历和后序遍历序列。 二、运行环境 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是对数据元素操作的应用函数， 数据结构 实 验 报 告 1. 实验目的和内容： 掌握二叉树基本操作的实现方法2. 程序分析 2.1存储结构 链式存储 2．程序流程 2.3关键算法分析 算法一：Create(BiNode 算法三：PreOrder(BiNode 《数据结构与数据库》 实验报告 实验题目 二叉树的基本操作及运算 一、需要分析 问题描述： 实现二叉树（包括二叉排序树）的建立，并实现先序、中序、后序和按层次遍历，计算叶子结点数、树的深度、树的宽度，求树的非空子孙结点个数、度为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）建立二叉树结构 建立二叉树时，要先明确是按哪一种遍历规则输入，该二叉树是按你所输入的遍历规则来建立的。本实验用的是先序遍历的规则进行建树。 二叉树用链表存储来实现，因此要先定义一个二叉树链表存储结构。因此要先定义一个结构体。此结构体的每个结点都是由数据域data 、左指针域Lchild 、右指针域Rchild 组成，两个指针域分别指向该结点的左、右孩子，若某结点没有左孩子或者右孩子时，对应的指针域就为空。最后，还需要一个链表的头指针指向根结点。 要注意的是，第一步的时候一定要先定义一个结束标志符号，例如空格键、＃等。当它遇到该标志时，就指向为空。 建立左右子树时，仍然是调用create （）函数，依此递归进行下去， 直到遇到结束标志时停止操作。 （2）输入二叉树元素 输入二叉树时，是按上面所确定的遍历规则输入的。最后，用一个返回值来表示所需要的结果。 （3）先序遍历二叉树 当二叉树为非空时，执行以下三个操作：访问根结点、先序遍历左子树、先序遍历右子树。 （4）中序遍历二叉树 当二叉树为非空时，程序执行以下三个操作：访问根结点、先序遍历左子树、先序遍历右子树。 （5）后序遍历二叉树 当二叉树为非空时，程序执行以下三个操作：访问根结点、先序遍历左子树、先序遍历右子树。 （6）主程序 需列出各个函数，然后进行函数调用。 四、各函数定义及说明 因为此二叉树是用链式存储结构存储的，所以定义一个结构体用以存储。 typedef struct BiTNode { char data; struct BiTNode *Lchild; struct BiTNode *Rchild; 问题一：二叉树遍历 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）问题描述：①用先序递归过程建立二叉树 (存储结构：二叉链表)。 输入数据按先序遍历所得序列输入，当某结点左子树或右子树为空时，输入‘*’号，如输入abc**d**e**得到的二叉树为： ②编写递归算法，计算二叉树中叶子结点的数目。 ③按凹入表方式输出该二叉树。 （2）分析：①此题要求用二叉链表作为存储结构，首先要定义二叉链表： typedef struct BiTNode { char data; struct BiTNode *lchild, *rchild; }BiTNode, * BiTree; struct BiTNode *lchild, *rchild 中lchild ，rchild 分别表示该结点的左右孩子。 ②输入时，按先序遍历所得序列输入，当某结点左子树或右子树为空时，输入‘*’号。 ③输出以凹入表的形式输出。 算法思想 （1）按照要求，这道题采用二叉链表来存储矩阵的有关信息。 存储结构定义为： typedef struct BiTNode { char data; struct BiTNode *lchild, *rchild; }BiTNode, * BiTree; 题中共有四个函数，包括主函数main()，创建二叉树函数Status preorder(BiTree &T)，计算叶子结点函数Status calLeaf(BiTree &T)，输出函数Status output(BiTree &T,int)。其中，主函数首先调用preorder()创建二叉树，然后调用函数calLeaf()。最后调用函数output()，输出二叉树。 （2）算法描述： a b e c d 《数据结构与算法》实验报告 专业班级姓名学号 实验项目 实验三二叉树。 实验目的 1、掌握用递归方法实现二叉树的遍历。 2、加深对二叉树的理解，逐步培养解决实际问题的编程能力。 题目： (1)编写二叉树的遍历操作函数。 ①先序遍历，递归方法re_preOrder(TREE *tree) ②中序遍历，递归方法re_midOrder(TREE *tree) ③后序遍历，递归方法re_postOrder(TREE *tree) (2)调用上述函数实现先序、中序和后序遍历二叉树操作。 算法设计分析 （一）数据结构的定义 要求用c语言编写一个演示程序，首先建立一个二叉树，让用户输入一个二叉树，实现该二叉树的便利操作。 二叉树型存储结构定义为： typedef struct TNode { char data;//字符型数据 struct TNode *lchild,*rchild;//左右孩子指针 }TNode,* Tree; （二）总体设计 程序由主函数、二叉树建立函数、先序遍历函数、中序遍历函数、后序遍历函数五个函数组成。其功能描述如下： （1）主函数：统筹调用各个函数以实现相应功能。 int main() （2）二叉树建立函数：根据用户意愿运用先序遍历建立一个二叉树。 int CreateBiTree(Tree &T) （3）先序遍历函数：将所建立的二叉树先序遍历输出。 void PreOrder(Tree T) （4）中序遍历函数：将所建立的二叉树中序遍历输出。 void InOrder(Tree T) （5）后序遍历函数：将所建立的二叉树后序遍历输出。 void PostOrder(Tree T) [题目]建立二叉树并求指定结点路径、深度、叶子个数和左右子树交换。 [问题描述] 要求能够按先序遍历次序输入二叉树中结点的值来构造二叉树T；然后用递归和非递归算法实现二叉树T 的中序遍历；接着编写算法实现求二叉树T中指定结点的路径，即从键盘输入二叉树T 的任一结点，可以输出从根结点到该结点所经历的结点；最后编写二叉树的三个应用算法（求二叉树的深度、求二叉树的叶子结点个数、将二叉树左右子树交换）。[基本要求] 分别建立二叉树存储结构的输入输出函数、输出中序遍历函数、指定节点路径函数、求深度函数、求叶子个数函数和将二叉树左右子树交换函数 一、需求与规格说明 1、定义二叉树的存储结构，每个结点中设置三个域，即值域、左指针域、右指针域。要建立二叉树T的链式存储结构，即建立二叉链表。根据输入二叉树结点的形式不同，建立的方法也不同，本系统采用先序序列递归建立二叉树，建立如下图所示的二叉树。应该在程序运行窗口的主控菜单后，先选择“1”并回车，紧接着在程序运行窗口中提示信息“输入二叉树的先序序列结点值:”之后，采用以下字符序列：abc@@de@g@@f@@@（以@替代空格，但是程序中直接输入空格就是，详细见代码注释）作为建立二叉树T的输入字符序列并回车，窗口出现：二叉树的链式存储结构建立完成! 图1 二叉树的图形结构 2、二叉树的遍历。本系统采用非递归中序遍历算法进行中序遍历，这意味着遍历右子树时不再需要保存当前层的根指针，可直接修改栈顶记录中的指针即可。需要在程序运行窗口的主控菜单中选择“2”并回车，程序运行窗口会出现以下中序遍历序列：该二叉树 的中序遍历序列是: cbegdfa 3、求二叉树的指定结点路径。在程序运行窗口的主控菜单中选择“3”并回车，在程序运行窗口中提示信息“输入要求路径的结点值:”输入“g”并回车，会得到结果为：→a→b→d→e→g如果输入“i”并回车，会得到结果为：没有要求的结点！ 4、求二叉树的深度。在程序运行窗口的主控菜单中选择“4”并回车，在会得到结果为：该二叉树的深度为：5 5、求二叉树的叶子结点个数。在程序运行窗口的主控菜单中选择“5”并回车，在会得到结果为：该二叉树的叶子结点数为：3 6、将二叉树左右子树交换（此处我用交换后的中序遍历来检验是否成功）。在程序运行窗口的主控菜单中选择“6”并回车.得到结果为：该二叉树的左右节点已交换成功，其中序遍历序列是：afdgebc 7、退出程序。在程序运行窗口的主控菜单中选择“0”并回车。退出程序。 二、设计 1、设计思想 在二叉树上无论采用哪种遍历方法，都能够访问遍树中的所有结点。由于访问结点的顺序不同，前序遍历和中序遍历都很难达到设计的要求（求路径）；但采用后序遍历二叉树是可行的，因为后序遍历是最后访问根结点，按这个顺序将访问过的结点存储到一个顺序栈中，然后再输出即可。因此，我们可以非递归地后序遍历二叉树T，当后序遍历访问到结点*p时，此时栈中存放的所有结点均为给定结点*p的祖先，而由这些祖先便构成了一条从根结点到结点*p之间的路径。而求二叉树的深度和叶子结点数可以直接判断结点孩子的数目来完成，将二叉树的左右子树交换也可以利用递归的方法，交换左右孩子来实现。 2、设计表示 为实现上述的设计思想，首先要定义二叉树的链式存储结构，我们采用二叉链表的方式，相应的类型说明为： typedef char DataType; typedef struct node{ DataType data; struct node *lchild,*rchild; }BinTNode,*BinTree; 齐鲁工业大学实验报告成绩 课程名称数据结构指导教师单健芳实验日期 院（系）信息学院专业班级计科（嵌入）14-1 实验地点 学生姓名高晨悦学号201403071007 同组人无 实验项目名称二叉树的递归算法 一、实验目的和要求 1.实现二叉树的先序，中序与后序遍历的递归算法与非递归算法。 2.求二叉树的结点个数，叶子结点个数，二叉树的高度，度为2的结点个数。 二、实验环境 微型计算机vc 6.0 三、实验内容 1.实现二叉树的先序，中序与后序遍历的递归算法与非递归算法。 2.求二叉树的结点个数，叶子结点个数，二叉树的高度，度为2的结点个数。 四、实验步骤 一．实验内容 1.实现二叉树的先序，中序与后序遍历的递归算法与非递归算法。 2.求二叉树的结点个数，叶子结点个数，二叉树的高度，度为2的结点个数。二．程序的设计思想 1实现二叉树的先序，中序与后序遍历的递归算法与非递归算法。 先构造二叉树，根据先序遍历的思想，输入根后，再输入左子树，直至左子树为空则输入上一层右字树。 （1）二叉树的非递归遍历是用显示栈来存储二叉树的结点指针，先序遍历时，按二叉树前序遍历的顺序访问结点，并将结点的指针入栈，直到栈顶指针指向结点的左指针域为空时取出栈顶指针并删除栈顶指针，访问刚取出的指针指向的结点的右指针指向的结点并将其指针入栈，如此反复执行则为非递归操作。 （2）二叉树的递归遍历：若二叉树为空，则空操作 先序遍历： （a）访问根结点； （b）先序遍历左子树； （c）先序遍历右子树。 中序遍历： （a）中序遍历左子树； （b）访问根结点； （c）中序遍历右子树 后序遍历： （a）后序遍历左子树； （b）后序遍历右子树； （c）访问根结点。 2.求二叉树的结点个数，叶子结点个数，二叉树的高度，度为2的结点个数。 （1）求二叉树的叶子结点个数：先分别求得左右子树中个叶子结点的个数，再计算出两者之和即为二叉树的叶子结点数。 （2）二叉树的结点个数之和：先分别求得左子树右子树中结点之和，再计算两者之和即为所求。 （3）二叉树的高度：首先判断二叉树是否为空，若为空则此二叉树高度为0,。否则，就先分别求出左右子树的深度进行比较，取较大的树加一即为所求。 （4）二叉树的度为2的结点个数：计算有左右孩子的结点个数，即为度为2的结点个数。三．编程过程中遇到的问题及解决办法 《数据结构》实验报告 题目：树和二叉树 一、 用二叉树来表示代数表达式 （一）需求分析 输入一个正确的代数表达式，包括数字和用字母表示的数，运算符号+ - * / ^ =及括号。系统根据输入的表达式建立二叉树，按照先括号里面的后括号外面的，先乘后除的原则，每个节点里放一个数字或一个字母或一个操作符，括号不放在节点里。分别先序遍历，中序遍历，后序遍历此二叉树，并输出表达式的前缀式，中缀式和后缀式。 （二）系统设计 1. 本程序中用到的所有抽象数据类型的定义； typedef struct BiNode //二叉树的存储类型 { char s[20]; struct BiNode *lchild,*rchild; }BiTNode,*BiTree; 2. 主程序的流程以及各程序模块之间的层次调用关系，函数的调用关系图： 3．列出各个功能模块的主要功能及输入输出参数 void push(char cc) 初始条件：输入表达式中的某个符号 操作结果：将输入的字符存入buf 数组中去 BiTree Create_RTree() 初始条件：给出二叉树的定义表达式 操作结果：构造二叉树的右子树，即存储表达式等号右侧的字符组 BiTree Create_RootTree() Create_RootTree() 构造二叉树 Main() Create_RTree() 构造右子树 PreOrderTraverse(BiTree T) 先序遍历二叉树 InOrderTraverse(BiTree T) 中序遍历二叉树 PostOrderTraverse(BiTree T) 后序遍历二叉树 1．实验题目 二叉树的建立与遍历 [问题描述] 建立一棵二叉树，并对其进行遍历（先序、中序、后序），打印输出遍历结果。2．需求分析 （1）输入的形式和输入值的范围：以字符形式按先序遍历输入 （2）输出的形式：依次按递归先序、中序、后序遍历，非递归先序、中序、后序遍历结果输出 (3) 程序所能达到的功能：从键盘接受输入（先序）进行遍历（先序、中序、后序），将遍历结果打印输。 (4) 测试数据： ABCффDEфGффFффф（其中ф表示空格字符） 则输出结果为先序：ABCDEGF 中序：CBEGDFA 后序：CGBFDBA 3．概要设计 （1）struct btnode{ char data; 数据 struct btnode *Lchild;左子数指针 struct btnode *Rchild; 右子数指针 }; struct btnode *createbt(struct btnode *bt ) 初始条件：空二叉树存在 操作结果：先序建立二叉树 void preOrder(struct btnode *bt) 初始条件：二叉树存在 递归先序遍历二叉树 void preOrder1(struct btnode *bt) 初始条件：二叉树存在 操作结果：非递归先序遍历 void midOrder(struct btnode *bt) 初始条件：二叉树存在 操作结果：递归中序遍历 void midOrder1(struct btnode *bt) 初始条件：二叉树存在 操作结果：非递归中序遍历 void postOrder(struct btnode *bt) 初始条件：二叉树存在 操作结果：递归后序遍历 void postOrder1 (struct btnode *bt) 初始条件：二叉树存在 操作结果：非递归后序遍历 void main() 主函数 （2）void main() 主函数 精品文档 实习报告 题目：编写一个实现基于二叉树表示的算术表达式Expression 操作程序 班级：姓名：学号：完成日期// 一、需求分析 算术表达式 Expression 内可以含有变量（ a～ z）、常量（ 0～9）和二元算术符（ +,-,*,/, ∧（乘幂））。实现以下操作： （1）ReadExpr(E) ――以字符序列的形式输入语法正确的前缀表达式并构 造表达式 E。 （2） WriteExpr(E) ――用带括号的中缀表达式输出表达式 E。 （3） Assign(V ，c) ――实现对变量 V 的赋值（ V=c），变量的初值为 0。 （4） Value(E) ――对算术表达式 E 求值。 （5） CompoundExpr(p,E1,E2)――构造一个新的复合表达式（ E1）p（E2）。 二、概要设计 1、数据类型的声明： 在这个课程设计中，采用了链表二叉树的存储结构，以及两个顺序栈的辅助 存储结构 /* 头文件以及存储结构 */ #include数据结构二叉树实验报告
树和二叉树实验报告
二叉树的建立和遍历的实验报告doc
二叉树实验报告及代码
二叉树实验报告
二叉树实验报告
数据结构实验报告之树与二叉树
数据结构实验报告—二叉树
二叉树实验报告
数据结构二叉树的实验报告
数据结构实验三——二叉树基本操作及运算实验报告
二叉树的遍历实验报告
数据结构二叉树遍历实验报告
二叉树实验报告
数据结构实验报告二叉树
二叉树的建立和遍历实验报告
数据结构二叉树的递归算法实验报告
树和二叉树的实验报告
二叉树遍历实验报告
树和二叉树——数据结构实验报告