实验四 树和二叉树一 实验任务1）二叉树的表示与实现2）Huffman编码二 实验目的1）掌握二叉树的类型定义和结构特点。2）掌握二叉树的链式存储表示和实现。3）掌握赫夫曼树及其应用三 实验原理1二叉树的定义所谓二叉树，是指结点的一个有限集合，它或为空集，或为满足下列性质的非空集合：有且只有一个根结点，其余结点分成左右两个互不相交的集合TL、TR，且TL、TR均为二叉树。二叉树的抽象数据类型定义如下：ADT BinaryTree 数据对象D：D=ai | aiElemSet, i=1,2, ,n, n0数据关系R：若D为空集，则称为空二叉树。若D仅含一个数据元素，则R为空集，否则RH，H满足关系：(1) T中存在唯一的一个结点，它没有前驱，称为树的根，用root表示，在集合D中用a1表示；(2) 若D中元素个数大于1，对于任意的数据元素ajD且j2，存在唯一的数据元素aiD，有H；(3) 若D中元素个数大于1，对于任意的数据元素aiD，仅存在不多于2个数据元素aj,akD且j, ki，有 , H，其中，若jK，则称aj为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。Parent(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 BinaryTree2二叉树的链式存储表示二叉树的链式存储结构通常采用二叉链表形式，即在每个结点中设置三个域，分别为数据域data、左指针域left和右指针域right。其中，数据域用于存储对应的数据元素，left和right用来分别存储左孩子和右孩子结点的存储位置。二叉链表的结点类型可定义为：typedef struct BiTreeNodeElemType 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个权值w1, w2, , wn，对应n个结点，构成具有n棵二叉树的森林F=T1, T2, , Tn，其中每棵二叉树Ti（1in）都只有一个权值为wi的根结点，其左右子树均为空。(2) 在森林F中选出两棵根结点的权值最小的树作为一棵新树的左、右子树，且置新树的根结点的权值为其左、右子树上根结点的权值之和。(3) 从F中删除构成新树的那两棵树，同时把新树加入F中。(4) 重复(2)和(3)，直到F中只含有一棵树为止，此树就是赫夫曼树。5赫夫曼编码若要设计长短不等的编码，则要求字符集中任一个字符的编码都不是另一个字符的编码的前缀，这种编码称做前缀编码。为了使不等长编码为前缀编码，可用该字符集中的每个字符作为叶子结点生成一棵编码二叉树，将每个字符出现的次数作为字符结点的权值赋予该结点上，求出此树的最小带权路径长度，也就是传送电文的最短长度。因此，求传送电文的最短长度问题就转化为求由字符集中的所有字符作为叶子结点且由字符的出现频率作为其权值所产生的赫夫曼树的问题。四 实验设备、仪器、工具与资料 微机、VC五 实验内容（1）实验任务1：二叉树建立和遍历编制C程序实现下列功能：1）建立二叉树。2）按先序、中序、后序方式遍历二叉树。程序的基本要求：采用二叉链表存储结构表示二叉树；通过二叉树广义表输入所有结点建立二叉树；通过递归算法实现二叉树的遍历并输出结点数据信息。（2）实验任务2：赫夫曼编码从键盘上输入n个字符及其权值，编制C程序建立赫夫曼树，并编码输出。六 实验步骤（1）实验预习1）预习本实验原理中关于二叉树的定义、二叉链表存储表示。2）分析掌握教材9399页中的算法4-14-4、算法4-74-7，为完成实验任务1做好准备。3）预习本实验原理中关于赫夫曼树、赫夫曼编码的含义及赫夫曼树的构造方法。4）分析掌握教材112115页中的算法4-144-15，为完成实验任务2做好准备。（2）实验步骤1）问题分析。充分地分析和理解此实验任务，弄清要求作什么，限制条件是什么。2）系统的结构设计。按照以数据结构为中心的原则划分模块。最后写出每个子程序（过程或函数）的规格说明，列出它们之间的调用关系，可以使用调用关系图表示则更加清晰，这样便完成了系统结构设计。3）详细设计。详细设计的目的是对子程序（过程或函数）的进一步求精。用 IF 、WHILE和赋值语句等，以及自然语言写出算法的框架。利用自然语言的目的是避免陷入细节。4）编码。在详细设计的基础上，对详细设计的结果进一步求精，用C语言表示出来。5）在VC环境下调试程序。七 实验报告要求实验报告包含程序开发过程所形成的所有文档资料，包括如下内容：1）需求分析及规格说明：问题描述，求解的问题是什么。2）概要设计：本程序所用的数据类型定义；主程序流程；程序模块及相互关系。3）详细设计：采用C语言定义的数据结构；各模块的伪码算法；各函数调用关系。4）调试报告。5）本实验任务1、2的程序清单及运行结果。八 思考题1）如何以广义表的形式输出二叉树？2）如何用非递归算法实现二叉树的中序遍历？ 3）如何利用已建好的赫夫曼编码对输入的正文进行译码？