山东大学《数据结构》实验指导04树和二叉树.docx

实验四树和二叉树
一实验任务
1)二叉树的表示与实现
2) Huffman 编码二实验目的
1)掌握二叉树的类型定义和结构特点。
2)掌握二叉树的链式存储表示和实现。
3)掌握赫夫曼树及其应用三实验原理
1 .二叉树的定义
所谓二叉树，是指结点的一个有限集合，它或为空集，或为满足以下性质的 非空集合：有且只有一个根结点，其余结点分成左右两个互不相交的集合Tl、 Tr,且Tl、Tr均为二叉树。
二叉树的抽象数据类型定义如下：
ADT BinaryTree {数据对或 D： D={ai | aiGEIemSet, i=l,2,…,n, n>0}
数据关系R：假设D为空集，那么称为空二叉树。
假设D仅含一个数据元素，那么R为空集，否那么R= {H} , H满足关系：
<!-[if !supportLists]->(l)<!-[endif]->T 中存在唯一的一个结点,它没有前驱，称为树的根，用「oot表示，在集合D中用di表示；
<!-[if !supportLists]->(2)v!-[endif]-->假设 D 中元素个数大于 1,对于任意的数据元素aj£D且心2,存在唯一的数据元素aiED,有 a j > £ H ；
<!-[if!supportLists]->(3)假设 D 中元素个数大于 1,对于任意的数据元素aiGD,仅存在不多于2个数据元素dj,dk£D且j, k>i,有v ai,访 > ,v ai, ak >£H,其中，假设 jvKvspan>,那么称司 为ai的左孩子节点，ak为ai的右孩子节点。
基本操作P：
InitBiTree(&T);操作结果：构造空二叉树T。
CreateBiTree(&T, tree);初始条件：tree给出二叉树T的表示形式。
操作结果：按tree构造二叉树T。
BiTreeEmpty(T);初始条件：二叉树T存在。
操作结果：假设T为空树，那么返回TRUE,否那么返回FALSE。
BiTreeDepth(T);初始条件：二叉树T存在。
操作结果：返回T的深度。
Root(T);初始条件：二叉树T存在。
操作结果：返回T的根。
Value(T, e);初始条件：二叉树T存在，e是需寻找的结点的值。
操作结果：假设找到该结点，那么函数返回TRUE否那么返回FALSE。
Assign(T, e, value);初始条件：二叉树T存在，e是需寻找的结点的值。
操作结果：假设找到该结点，结点e赋值为value,那么函数返回TRUE, 否那么返回FALSE oParent(T, e, P);
初始条件：二叉树T存在，e是需寻找的结点的值。
操作结果：假设树中存在值为e的结点，那么函数返回TRUE否那么返回 FALSE；假设存在该结点，用P返回双亲结点的位置，假设结 点为根结点，那么P返回空。
LeftChild(T, e, P);初始条件：二叉树T存在，e是需寻找的结点的值。
操作结果：假设树中存在值为e的结点，那么函数返回TRUE,否那么返回 FALSE；假设存在该结点，用P返回左孩子结点的位置，假设 结点无左孩子结点，那么P返回空。
RightChild(T, e, P);初始条件：二叉树T存在，e是需寻找的结点的值。
操作结果：假设树中存在值为e的结点，那么函数返回TRUE,否那么返回 FALSE；假设存在该结点，用P返回右孩子结点的位置，假设 结点无右孩子结点，那么P返回空。
DelBiTreeNode(&T, P);初始条件：二叉树T存在，P指向该二叉树中的一个结点。
操作结果：删除P所指向的结点及其子树。
TraverseBiTree(T, visit());初始条件：二叉树T存在，visit是对结点操作的应用函数。
操作结果：按某种次序对T的每个结点调用函数visit()一次且至多 一次。一旦visit。失败，那么操作失败。
ClearBiTree(&T);初始条件：二叉树T存在。
操作结果：将二叉树T清空。
}ADT BinaryTree
2 .二叉树的链式存储表示
二叉树的链式存储结构通常采用二叉链表形式，即在每个结点中设置三个域, 分别为数据域data、左指针域left和右指针域right。其中，数据域用于存储对 应的数据元素，left和right用来分别存储左孩子和右孩子结点的存储位置。
二叉链表的结点类型可定义为：
typedef struct BiTreeNode{ElemType data;
struct BiTreeNode *left;struct BiTreeNode *right;
} BiTreeNode, * BiTreePtr;
3 .二叉树的遍历
二叉树的遍历是二叉树中最重要的运算，也是各种操作的基础。二叉树的遍 历是指按照某个搜索路径寻访树中的每个结点，使得每个结点均被访问一次，而 且仅被访问一次。在遍历的过程中，可以对结点进行各种操作。
根据二叉树的递归定义，一棵非空二叉树由根结点、左子树和右子树组成, 因此，遍历一棵二叉树可以分解为三个问题：访问根结点、遍历左子树、遍历右 子树。假设分别用D、L、R表示上述三个子问题，那么可能有DLR、LDR、LRD、DRL、RDL、RLD几种情况。假设限定先左后右，那么只有前3种情况:
(1) DLR,此时访问根结点的操作在遍历左、右子树之前，故称之为先序遍 历或先根遍历；
(2) LDR,此时访问根结点的操作在遍历左子树之后、右子树之前，故称之 为中序遍历或中根遍历；
(3) LRD,此时访问根结点的操作在遍历左、右子树之后，故称之为后序 遍历或后根遍历。
4 .赫夫曼树
n个带权叶子结点构成的所有二叉树中，带权路径长度WPL最小的二叉树称 作赫夫曼树。权值越大的结点离根越近的二叉树才是最优二叉树。
赫夫曼树构造算法，具体表达如下：
(1)给定n个权值{Wi, W2,…，Wn},对应n个结点，构成具有n棵二叉树的 森林F={Ti,T2,…,Tn},其中每棵二叉树Ti (l<i<n)都只有一个权值为Wi的根 结点，其左右子树均为空。
(2)在森林F中选出两棵根结点的权值最小的树作为一棵新树的左、右子树, 且置新树的根结点的权值为其左、右子树上根结点的权值之和。
(3)从F中删除构成新树的那两棵树，同时把新树加入F中。
(4)重复(2)和(3),直到F中只含有一棵树为止，此树就是赫夫曼树。
5 .赫夫曼编码
假设要设计长短不等的编码，那么要求字符集中任一个字符的编码都不是另一个 字符的编码的前缀，这种编码称做前缀编码。
为了使不等长编码为前缀编码，可用该字符集中的每个字符作为叶子结点生 成一棵编码二叉树，将每个字符出现的次数作为字符结点的权值赋予该结点上, 求出此树的最小带权路径长度，也就是传送电文的最短长度。因此，求传送电文 的最短长度问题就转化为求由字符集中的所有字符作为叶子结点且由字符的出 现频率作为其权值所产生的赫夫曼树的问题。
四实验设备、仪器、工具与资料
微机、VC五实验内容
(1)实验任务1：二叉树建立和遍历
编制C程序实现以下功能：
1)建立二叉树。
2)按先序、中序、后序方式遍历二叉树。
程序的基本要求：采用二叉链表存储结构表示二叉树；通过二叉树广义表输 入所有结点建立二叉树；通过递归算法实现二叉树的遍历并输出结点数据信息。
(2)实验任务2：赫夫曼编码
从键盘上输入n个字符及其权值，编制C程序建立赫夫曼树，并编码输出。 六实验步骤（1）实验预习
1）预习本实验原理中关于二叉树的定义、二叉链表存储表示。
2）分析掌握教材93〜99页中的算法4-1〜4-4、算法4-7-4-7,为完成实验 任务1做好准备。
3）预习本实验原理中关于赫夫曼树、赫夫曼编码的含义及赫夫曼树的构造 方法。
4）分析掌握教材112〜115页中的算法4-14〜4-15,为完成实验任务2做好 准备。
（2）实验步骤
1）问题分析。充分地分析和理解此实验任务，弄清要求作什么，限制条件 是什么。
2）系统的结构设计。按照以数据结构为中心的原那么划分模块。最后写出每 个子程序（过程或函数）的规格说明，列出它们之间的调用关系，可以使用调用 关系图表示那么更加清晰，这样便完成了系统结构设计。
3）详细设计。详细设计的目的是对子程序（过程或函数）的进一步求精。 用IF、WHILE和赋值语句等，以及自然语言写出算法的框架。利用自然语言的 目的是防止陷入细节。
4）编码。在详细设计的基础上，对详细设计的结果进一步求精，用C语言 表示出来。
5）在VC环境下调试程序。
七实验报告要求
实验报告包含程序开发过程所形成的所有文档资料，包括如下内容：
1）需求分析及规格说明：问题描述，求解的问题是什么。
2）概要设计：本程序所用的数据类型定义；主程序流程；程序模块及相互 关系。
3）详细设计：采用C语言定义的数据结构；各模块的伪码算法；各函数调 用关系。
4）调试报告。
5）本实验任务1、2的程序清单及运行结果。
八思考题
1）如何以广义表的形式输出二叉树？
2）如何用非递归算法实现二叉树的中序遍历？
3）如何利用已建好的赫夫曼编码对输入的正文进行译码？