二叉树的应用实验报告总结

数据结构实验报告——二叉树

实 验 报 告

课程名称 ____数据结构上机实验__________ 实验项目 ______二叉树的应用 ____________ 实验仪器 ________PC机___________________

系 别____________________________

专 业_____________________________

班级/学号____________________________ 学生姓名 _____________________________ 实验日期 _______________________

成 绩 _______________________

指导教师 _______________________

数据结构实验报告——二叉树

实验三.二叉树的应用

1. 实验目的：掌握二叉树的链式存储结构和常用算法。利用哈夫曼树设计最优压缩编码。

2. 实验内容：

1) 编写函数，实现建立哈夫曼树和显示哈夫曼树的功能。

2) 编写函数，实现生成哈夫曼编码的功能。

3) 编写主函数，从终端输入一段英文文本；统计各个字符出现的频率，然后构建哈夫曼树并求出对应的哈夫曼编码；显示哈夫曼树和哈夫曼编码

山东工商学院

《数据结构》实验指导及报告书

2012 / 2013 学年

姓名： 学号： 班级： 指导教师：

Xx学院

2012年11月25日

第 一 学期

实验三 二叉树

一、实验目的

1、掌握二叉树的基本特性

2、掌握二叉树的先序、中序、后序的递归遍历算法 3、理解二叉树的先序、中序、后序的非递归遍历算法

4、通过求二叉树的深度、叶子结点数和层序遍历等算法，理解二叉树的基本特性

二、实验预习

说明以下概念

1、二叉树：是另一种树型结构，它的特点是每个结点至多只有两棵子树，并且二叉树有左右之分，其次序不能任意颠倒。 2、递归遍历：

1、 非递归遍历：

4、层序遍历：

三、实验内容和要求

1、阅读并运行下面程序，根据输入写出运行结果，并画出二叉树的形态。 #include #include

#define MAX 20

typedef struct BTNode{ /*节点结构声明*/

char data ; /*节点数据*/ struct BTNode *lchild;

struct BTNode *rchild ;

二叉树应用实验

实验目的

(1)掌握二叉树的动态链表存储结构及表示。

(2)掌握二叉树的三种遍历算法（递归和非递归两类）。 (3)运用二叉树三种遍历的方法求解有关问题。

实验运行环境

Visual C++

实验任务

为使实验程序简洁直观，下面的部分实验程序中的一些功能实现仍以调用库函数程序\中的函数的形式给出，并假设该库函数中定义了二叉树指针和结点类型分别为bitre和bnode，以及部分常用运算，例如构建二叉树、以某种方式显示二叉树等。各运算的名称较为直观，因而易于理解。为便于数据的描述，将测试数据结构列出，并以一个文件名的形式给出标注，例如测试数据名为full41.cbt的二叉树，其具体结构形式参见二叉树列表中的标有full41.cbt的二叉树。

实验内容

第一题：

求二叉树的高度。 实验测试数据基本要求：

第一组数据： full41.cbt

第二组数据： cbitre.cbt

实验准备：

第一步：将指针指向根结点，判断根结点是否为空，如果是则返回0，否则进入第二步。

第二步：判断当前结点是否有子树，如果没有，当前结点的高度为1，否则进入第三步。

第三步：求当前结点左右子树的高度，并将两者中较大的加1作为该结点的高

实验报告

一、实验目的

1、熟悉二叉树树的基本操作。

2、掌握二叉树的实现以及实际应用。

3、加深二叉树的理解，逐步培养解决实际问题的编程能力。

二、实验环境

1台WINDOWS环境的PC机，装有Visual C++ 6.0。

三、实验内容

【问题描述】 现需要编写一套二叉树的操作函数，以便用户能够方便的利用这些函数来实现自己的应用。其中操作函数包括：

1> 创建二叉树CreateBTNode(*b,*str)：根据二叉树括号表示法的字符串*str生成对应的链

式存储结构。

2> 输出二叉树DispBTNode(*b)：以括号表示法输出一棵二叉树。

3> 查找结点FindNode(*b,x)：在二叉树b中寻找data域值为x的结点,并返回指向该结点

的指针。

4> 求高度BTNodeDepth(*b)：求二叉树b的高度。若二叉树为空,则其高度为0；否则,其

高度等于左子树与右子树中的最大高度加l。 5> 求二叉树的结点个数NodesCount(BTNode *b) 6> 先序遍历的递归算法：void PreOrder(BTNode *b) 7> 中序遍历的递归算法：void InOrder(BTNode *b) 8> 后序遍历递归算法：

实验报告

一、实验目的

1、熟悉二叉树树的基本操作。

2、掌握二叉树的实现以及实际应用。

3、加深二叉树的理解，逐步培养解决实际问题的编程能力。

二、实验环境

1台WINDOWS环境的PC机，装有Visual C++ 6.0。

三、实验内容

【问题描述】 现需要编写一套二叉树的操作函数，以便用户能够方便的利用这些函数来实现自己的应用。其中操作函数包括：

1> 创建二叉树CreateBTNode(*b,*str)：根据二叉树括号表示法的字符串*str生成对应的链

式存储结构。

2> 输出二叉树DispBTNode(*b)：以括号表示法输出一棵二叉树。

3> 查找结点FindNode(*b,x)：在二叉树b中寻找data域值为x的结点,并返回指向该结点

的指针。

4> 求高度BTNodeDepth(*b)：求二叉树b的高度。若二叉树为空,则其高度为0；否则,其

高度等于左子树与右子树中的最大高度加l。 5> 求二叉树的结点个数NodesCount(BTNode *b) 6> 先序遍历的递归算法：void PreOrder(BTNode *b) 7> 中序遍历的递归算法：void InOrder(BTNode *b) 8> 后序遍历递归算法：

题目：

班级：

姓名：

学号：得分： 二叉树的应用举例 信息一班 冯琴琴

120108010001

实验三 二叉树的应用举例

一、 实验目的

要求学生必须掌握二叉树的建立及先序、中序、后序三种遍历方式，在此基础上实现树的一些简单应用问题

二、 实验内容及步骤

1.二叉链表的建立，先（中、后）序遍历

输入：字符串序列

输出：先（中、后）序序列

处理方法：通过补虚结点，使二叉树中各实际结点均具有左右孩子，再对该二叉树按先序遍历进行输入。以字符串的形式:根、左子树、右子树定义一棵二叉树：

1) 空树以空白字符‘#’表示

2) 只含一个根结点的二叉树（图1示）以字符串‘A##’表示

3) 一般的二叉树，以图2为例，以下列字符串表示：AB#C##D##

4) 无论先序、中序、后序遍历二叉树，遍历时的搜索路线是相同的：从根节点出发，逆时针沿二叉树外

缘移动，对每个节点均途经三次。

先序遍历：第一次经过节点时访问。中序遍历：第二次经过节点时访问。后序遍历：第三次经过节点时访问

图1

图2

2. 统计二叉树中叶子结点的个数，计算二叉树的深度。

输入：字符串序列

输出：叶子结点的个数，二叉树的深度

处理方法：

1) 先序遍历二叉树。在遍历过程中查找叶子结点，并计数。由此，需在

题目：

班级：

姓名：

学号：得分： 二叉树的应用举例 信息一班 冯琴琴

120108010001

实验三 二叉树的应用举例

一、 实验目的

要求学生必须掌握二叉树的建立及先序、中序、后序三种遍历方式，在此基础上实现树的一些简单应用问题

二、 实验内容及步骤

1.二叉链表的建立，先（中、后）序遍历

输入：字符串序列

输出：先（中、后）序序列

处理方法：通过补虚结点，使二叉树中各实际结点均具有左右孩子，再对该二叉树按先序遍历进行输入。以字符串的形式:根、左子树、右子树定义一棵二叉树：

1) 空树以空白字符‘#’表示

2) 只含一个根结点的二叉树（图1示）以字符串‘A##’表示

3) 一般的二叉树，以图2为例，以下列字符串表示：AB#C##D##

4) 无论先序、中序、后序遍历二叉树，遍历时的搜索路线是相同的：从根节点出发，逆时针沿二叉树外

缘移动，对每个节点均途经三次。

先序遍历：第一次经过节点时访问。中序遍历：第二次经过节点时访问。后序遍历：第三次经过节点时访问

图1

图2

2. 统计二叉树中叶子结点的个数，计算二叉树的深度。

输入：字符串序列

输出：叶子结点的个数，二叉树的深度

处理方法：

1) 先序遍历二叉树。在遍历过程中查找叶子结点，并计数。由此，需在

实验 五 二叉树及其应用

1.目的要求：

（1） 通过实验掌握二叉树的两种基本的存储结构，及二叉树的建立、遍历，并加以

应用。

（2） Huffman树建立、编码。 2.实验内容：

（1） 按先序次序输入二叉树中结点的值，建立一棵以二叉链表作存储结构的二叉树，

然后按先序、中序、后序顺序分别遍历这棵二叉树，并完成二叉树的相应信息的统计（如各种结点数目、二叉树的高度等）；

（2） 建立一棵二叉排序树，并对其进行先序、中序、后序遍历。 （3） 应用队列结构实现二叉树的层次遍历。

（4） 设计一个完整的编码系统：针对一篇文档，统计各个字符的出现次数，并为其设

计Huffman编码。

注：（1）～（2）必做，（3）～（4）选做。

三.实验主要流程、基本操作或核心代码、算法片段（该部分如不够填写，请另加附页）

（1） 按先序次序输入二叉树中结点的值，建立一棵以二叉链表作存储结构的二叉树，

然后按先序、中序、后序顺序分别遍历这棵二叉树，并完成二叉树的相应信息的统计（如各种结点数目、二叉树的高度等）；

? 程序代码：

头文件：

#ifndef _H_ #define _H_

#define OK 1 #define ERROR 0 #define

特殊线性表

班级：计算机11-1 学号： 姓名： 成绩：_________

实验七 二叉树操作验证

一、 实验目的

⑴ 掌握二叉树的逻辑结构；

⑵ 掌握二叉树的二叉链表存储结构；

⑶ 掌握基于二叉链表存储的二叉树的遍历操作的实现。

二、 实验内容

⑴ 建立一棵含有n个结点的二叉树，采用二叉链表存储；

⑵ 前序（或中序、后序）遍历该二叉树。

三、设计与编码

#include <iostream>

using namespace std;

template <class T>

struct BiNode

{

T data;

BiNode<T> *lchild, *rchild;

};

template <class T>

class BiTree

{

public:

BiTree(); //有参构造函数，初始化一棵二叉树，其前序序列由键盘输入 BiNode<T> *Getroot();

~BiTree(void); //析构函数，释放二叉链表中各结点的存储空间

void PreOrder(BiNode<T> *root); //前序遍历二叉树

void InOrder(

数据结构上机实验报告

二叉树问题

陈冠豪

2010210501

0101015

二O一O年5月26号

验的目建一棵立二树叉要，分别求递用归和递非方法实归二现 叉树的先、序序中和序遍后历。

实现代码:

#ifndef TREE_H #define TREE_H #include <stdio.h> #include <malloc.h> #include <stack> #include <queue> #include <assert.h> using namespace std; typedefintElemType; typedef struct treeT { ElemType key; struct treeT* left; struct treeT* right; }treeT, *pTreeT;

static void visit(pTreeT root) { if (NULL != root) { printf(" %d\n", root->key); } } static pTreeT BT_MakeNode(E