第五章树
实验目的：
1.掌握二叉树的链式存储结构的定义及实现方法。
2.掌握二叉树的先序、中序和后序遍历方法。
3.掌握二叉树的结点个数和树的深度的计算方法。
实验内容：
1.建立一棵含有n个结点的二叉树，采用二叉链表存储。
2.分别用前序、中序和后序遍历该二叉树，输出访问到的结点。
3.计算该二叉树的结点个数和二叉树的深度，输出计算结果。
//参考代码
#include
#include
#include
template
struct BinTreeNode {//二叉树结点类定义
T data; //数据域
BinTreeNode
//左子女、右子女链域
BinTreeNode ():leftChild(NULL),rightChild(NULL){}
//构造函数
BinTreeNode (T x, BinTreeNode
template
class BinaryTree { //二叉树类定义
public:
BinaryTree (T value) : RefValue(value), root(NULL) //构造函数
{
CreateBinTree (cin,root);
}
BinaryTree (BinaryTree
//复制构造函数
~BinaryTree () { destroy(root); } //析构函数
bool IsEmpty () { return root == NULL;}//判二叉树空否
int Height () { return Height(root); } //求树高度
int Size (){ return Size(root); } //求结点数
BinTreeNode
void preOrder (void (*visit) (BinTreeNode
{ preOrder (root, visit); }
void inOrder (void (*visit) (BinTreeNode
{ inOrder (root, visit); }
void postOrder (void (*visit) (BinTreeNode
{ postOrder (root, visit); }
protected:
BinTreeNode
T RefValue; //数据输入停止标志
void CreateBinTree (istream& in,BinTreeNode
void destroy (BinTreeNode
void preOrder (BinTreeNode
void inOrder (BinTreeNode
int Size (BinTreeNode
int Height ( BinTreeNode
//其他函数略
};
template
void BinaryTree
//删除根为subTree的子树
if (subTree != NULL) {
destroy (subTree->leftChild); //删除左子树
destroy (subTree->rightChild); //删除右子树
delete subTree; //删除根结点
}
}
template
void BinaryTree
if ( !in.eof () )
{ //未读完, 读入并建树
in >> item; //读入根结点的值
if (item != RefValue)
{
subTree = new BinTreeNode
//建立根结点
if (subTree == NULL)
{cerr << "存储分配错!"<< endl; exit (1);}
CreateBinTree (in, subTree->leftChild);
//递归建立左子树
CreateBinTree (in, subTree->rightChild);
//递归建立右子树
}
else subTree = NULL; //封闭指向空子树的指针
}
}
template
void BinaryTree
if (subTree!= NULL) {
visit (subTree); //访问根结点
preOrder (subTree->leftChild, visit); //遍历左子树
preOrder (subTree->rightChild, visit); //遍历右子树
}
}
template
void BinaryTree
if (subTree != NULL) {
inOrder (subTree->leftChild, visit); //遍历左子树
visit (subTree); //访问根结点
inOrder (subTree->rightChild, visit); //遍历右子树
}
}
template
void BinaryTree
if (subTree != NULL ) {
postOrder (subTree->leftChild, visit);//遍历左子树
postOrder (subTree->rightChild, visit); //遍历右子树
visit (subTree); //访问根结点
}
}
template
int BinaryTree
if (subTree == NULL) return 0; //空树
else return 1+Size (subTree->leftChild)+ Size (subTree->rightChild); }
template
int BinaryTree
else {
int i = Height (subTree->leftChild);
int j = Height (subTree->rightChild);
return (i < j) ? j+1 : i+1; }
}
void print(BinTreeNode
{
cout<
}
void main()
{
BinaryTree
cout<<"前序遍历结果为：";
T.preOrder(print);
cout< T.inOrder(print); cout< T.postOrder(print); cout< int i=T.Height(); cout< i=T.Size(); cout< } 测试数据： 输入：ab##cd##e## 输出： 说明：输入中的#号是分支结束的标志。 实验三二叉树的操作及应用 实验课程名：数据结构与算法 专业班级：15计科1班学号：201540410109 姓名：刘江 实验时间：2016.10.24-10.31 实验地点：K4-102 指导教师：冯珊 成绩: 一、实验目的及要求 1、进一步掌握指针变量、动态变量的含义。 2、掌握二叉树的结构特性，以及各种存储结构的特点和适用范围。 3、掌握用指针类型描述、访问和处理二叉树的运算。 二、实验内容 任务一：完成下列程序，该程序以二叉链表作存储结构，构建如图1所示的二叉树， 并依次进行二叉树的前序、中序、后序及层次遍历。 图1 解答： （1）源代码：#include else { if(!(T=(Node*)malloc(sizeof(Node)))){printf("Overflow.\n") ;exit(0);} T->data =ch; CreatBiTree(T->lchild ); CreatBiTree(T->rchild ); } return T; } void PrintData(DataType x) { printf("%c",x); } void PreOrder(BiTree T, void (*Visit)( DataType item)) /*前序遍历二叉树T，访问操作为Visit()函数*/ { if(T!= NULL) { Visit(T->data); PreOrder(T->lchild, Visit); PreOrder(T->rchild, Visit); } } void InOrder(BiTree T, void (*Visit)( DataType item)) /*中序t */ { if(T!= NULL) { InOrder(T->lchild, Visit); Visit(T->data); InOrder(T->rchild, Visit); } } void PostOrder(BiTree T, void (*Visit)( DataType item)) /*后序 */ { if(T!= NULL) { PostOrder(T->lchild, Visit); PostOrder(T->rchild, Visit); Visit(T->data); } 实验三二叉树的遍历 一、实验目的 １、熟悉二叉树的结点类型和二叉树的基本操作。 ２、掌握二叉树的前序、中序和后序遍历的算法。 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、测试数据： 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）掌握利用先序序列建立二叉树的二叉链表的过程。 （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()函数。分解出原始中缀表达式中的操作数、操作符以及括号，保存在队列中，以本实验中的数据为例，分解完成后队列中的保存顺序如下图所示： 江南大学通信与控制工程学院标准实验报告 （实验）课程名称：计算机软件技术基础实验名称：二叉树的遍历和应用 班级：自动化 姓名：李玉书 学号：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 树和二叉树 一、实验目的 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 重庆交通大学综合性设计性实验报告 班级：软件开发专业 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; 南昌大学实验报告 学生姓名：李木子学号：专业班级：软工 实验类型：□验证□综合□设计□创新实验日期：实验成绩：一、实验项目名称 二叉树的遍历 二、实验目的 学会链式二叉树的结构体定义，创建与前序中序后序遍历三、实验基本原理 四、主要仪器设备及耗材 电脑， 五、实验步骤 ************************************** * 链式二叉树的创建与遍历 * ************************************** ************************************** * 链式二叉树的结构体定义 * ************************************** <> <> ; { ; *; *; }; ************************************** * 链式二叉树函数声明 * ************************************** *(); (*); (*); (*); ************************************** * 链式二叉树创建函数 * ************************************** *() { ; *; (); ('') ; ('\'); { (*)(()); >; >(); >(); } ; } ************************************** * 链式二叉树递归前序遍历函数 * ************************************** (*) { () { ("\">); 《数据结构》实验报告三 学院：班级： 学号：姓名： 日期：2010.04.29 程序名：L61.CPP,L62.CPP 一、上机实验的问题和要求： 要求采用二叉链表作为存储结构，完成二叉树的建立，前序、中序和后序遍历的操作，求所有叶子及结点总数的操作等。具体实现要求： 1.基于先序遍历的构造算法：输入是二叉树的先序序列，但必须在其中加入虚结点以示空 指针的位置。假设虚结点输入时用空格字符表示。 2.用广义表表示所建二叉树。 3.用凹入表表示所建二叉树。 4.分别利用前序遍历、中序遍历、后序遍历所建二叉树。 5.求二叉树结点总数，观察输出结果。 6.求二叉树叶子总数，观察输出结果。 7.交换各结点的左右子树，用广义表表示法显示新的二叉树。 8.（★）二叉树采用链接存储结构，其根结点指针为T，设计一个算法对这棵二叉树的每 个结点赋值：（注意要修改DataType类型） ?叶结点的值为3 ?只有左孩子或右孩子的结点则其值分别等于左孩子或右孩子的值 ?左、右孩子均有的结点，则其值等于左、右孩子结点的值之和 ?用广义表表示法显示所建二叉树 阅读理解建立Huffman树的算法，对该算法进行运行及调试。具体实现要求： 1.调试并运行Huffman算法，验算《回家作业六》的第3题。 2.（★）求Huffman树的带权路径长度WPL。 二、程序设计的基本思想，原理和算法描述： （包括程序的结构，数据结构，输入/输出设计，符号名说明等） 三、源程序及注释： #include //二叉树的链式存储表示 typedef char DataType; //应由用户定义DataType的实际类型typedef struct node { DataType data; struct node *lchild, *rchild; //左右孩子指针 } BinTNode; //结点类型 typedef BinTNode *BinTree; void main() { void ListBinTree(BinTree T); //用广义表表示二叉树 void DisplayBinTree(BinTree T); //用凹入表表示二叉树 void CreateBinTree(BinTree *T); //构造二叉链表 void Preorder(BinTree T); //前序遍历二叉树 void Inorder(BinTree T); //中序遍历二叉树 void Postorder(BinTree T); //后序遍历二叉树 int nodes(BinTree T); //计算总结点数 int leafs(BinTree T); //计算总叶子数 BinTree swap(BinTree T); //交换左右子树 BinTree T; printf("请输入先序序列（虚结点用空格表示）：\n"); CreateBinTree(&T); ListBinTree(T); printf("\n"); DisplayBinTree(T); printf("前序遍历：\n"); Preorder(T); printf("\n"); printf("中序遍历：\n"); Inorder(T); printf("\n"); printf("后序遍历：\n"); Postorder(T); printf("\n"); printf("二叉树的总结点数为%d\n",nodes(T)); printf("二叉树的总叶子结点数为%d\n",leafs(T)); T=swap(T); ListBinTree(T); printf("\n"); } /*构造二叉链表*/ void CreateBinTree(BinTree *T) { 题目： 编程实现二叉查找树的建立、中序遍历、元素查找等功能，要求解释实现过程及演示实际例子的运行结果。 算法描述： 首先创建二叉树结点类，其主要包括：二叉树结点数据域，指向左、右子树的指针，构造函数，设置当前结点左、右子树、数据域以及判断当前结点是否为叶子结点等。然后进行二叉树类定义，其私有部分为定义二叉树根结点指针，公有部分主要包括：构造函数、析构函数、判断二叉树是否为空树、先，中，后序遍历的递归与非递归、二叉树删除、层序遍历以及二叉树搜索等。接下来将对一些重要函数算法进行描述： 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.问题描述 设输入该二叉树的前序序列为： 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)熟悉各种存储结构的特征及如何应用树结构解决具体问题。 二、实验内容和原理 实验内容： 编写程序实现交换二叉树中所有结点的左右子树的算法。 实验原理： 【问题描述】建立一棵二叉树，按层次遍历该二叉树，并实现将二叉树中所有结点的左右子树交换，显示其结果。 【基本要求】从键盘接受输入点（按层次遍历顺序），以“#”号结束，以二叉链表作为存储结构，将其二叉树中所有结点的左右子树交换，并将结果输出。 【实现】交换二叉树中所有结点的左右子树的具体步骤如下: ①将根结点进指针栈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++; 实验四二叉树的建立和遍历 学院专业班 学号姓名 一．实习目的 1.掌握二叉链表的存储结构； 2.掌握二叉链表的建立； 3.掌握二叉树的先序遍历、中序遍历、后序遍历的递归算法； 4. 掌握二叉树遍历算法的应用； 二．实习内容 1.按先序序列建立二叉树的二叉链表（算法6.4）（空树用#表示） 2.对生成的二叉树分别进行先序遍历、中序遍历、后序遍历，输出结果。 3．统计二叉树中结点个数； 4. 求二叉树的高度； 三．实验步骤 1.定义二叉链表的存储结构 #include "stdio.h" #include "stdlib.h" typedef char TElemType; typedef struct BiTNode { TElemType data; struct BiTNode *lchild, *rchild; // 左右孩子指针 }BiTNode,*BiTree; 2.编写函数CreateBiTree，按先序序列建立二叉树的二叉链表; 测试的字符序列为abdg###e##c#f##; 程序代码为： void CreateBiTree(BiTree &T) { // 算法6.4：按先序次序输入二叉树中结点的值(可为字符型或整型，在主程中定义)，构造二叉链表表示的二叉树T。以#表示空树 TElemType ch; scanf("%c",&ch); if(ch=='#') // 空 T=NULL; else { T=(BiTree )malloc(sizeof(BiTNode)); // 生成根结点 if(!T) exit(-1); T->data=ch; CreateBiTree(T->lchild);// 递归构造左子树 CreateBiTree(T->rchild);// 构造右子树 } } 2. 编写二叉树的先序遍历、中序遍历、后序遍历的递归算法 int preOrderTraverse(BiTree T) { // 初始条件：二叉树T存在，先序递归遍历T； if(T==NULL) return 1; if(T!=NULL) // T不空 {printf("%5c",T->data); // 访问根结点preOrderTraverse(T->lchild);// 先序遍历左子树 preOrderTraverse(T->rchild);// 先序遍历右子树 } } int inOrderTraverse(BiTree T) { // 初始条件：二叉树T存在，中序递归遍历T； if(T==NULL) return 1; if(T!=NULL) // T不空 { inOrderTraverse(T->lchild);// 中序遍历左子树 printf("%5c",T->data); // 访问根结点inOrderTraverse(T->rchild);// 中序遍历右子树 } } int postOrderTraverse(BiTree T) { // 初始条件：二叉树T存在， // 操作结果：后序递归遍历T； if(T==NULL) return 1; if(T!=NULL) // T不空 { postOrderTraverse(T->lchild);// 后序遍历左子树 postOrderTraverse(T->rchild);// 后序遍历右子树 printf("%5c",T->data); // 访问根结点实验三 二叉树的操作及应用
数据结构二叉树实验报告
二叉树实验报告
二叉树的建立和遍历的实验报告doc
数据结构实验二叉树
实验四 二叉树的遍历和应用04
实验八：二叉树的遍历与应用
树和二叉树实验报告
二叉树实验报告
二叉树的遍历算法实验报告
实验3 树和二叉树
二叉树的遍历实验报告
数据结构实验二叉树的遍历
实验三树和二叉树
二叉树实验报告
二叉树的建立和遍历的实验报告
数据结构二叉树遍历实验报告
数据结构实验报告-树与二叉树
二叉树的建立和遍历实验报告
相关主题
文本预览