实验报告(二叉树的构建基本操作和遍历.docVIP

实验报告 课程：数据结构（c语言） 实验名称：二叉树的构建、基本操作和遍历 系别：数字媒体技术 实验日期： 专业班级：媒体161 组别：无 姓名： 学号： 实验报告内容 验证性实验 预习准备： 实验目的： 1、熟练掌握二叉树的结构特性，熟悉二叉树的各种存储结构的特点及适用范围； 2、熟练掌握二叉树的遍历方法及遍历算法； 3、掌握建立哈夫曼树和哈夫曼编码的方法及带权路径长度的计算。 实验环境：Widows操作系统、VC6.0 实验原理： 定义： 树：树(tree)是n(n0)个结点的有限集T，其中，有且仅有一个特定的结点，称为树的根(root)。当n1时，其余结点可分为m(m0)个互不相交的有限集T1,T2,……Tm，其中每一个集合本身又是一棵树，称为根的子树(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,……wn}，构造n棵只有根 结点的二叉树，令起权值为wj； (2) 在森林中选取两棵根结点权值最小的树作左右子树，构造一棵新的二叉树，置新二叉树根结点权值为其左右子树根结点权值之和； (3) 在森林中删除这两棵树，同时将新得到的二叉树加入森林中重复上述两步，直到只含一棵树为止，这棵树即哈夫曼树。 4. 实验内容和要求： （1）二叉树 建立如下图所示的二叉树： 要求：1、建立带头结点的二叉树，将二叉树初始化为空； 2、依次将二叉树的所有结点插入，建立上图所示的二叉树； 3、用户可由键盘输入数据实现对二叉树各结点的插入、删除等操作； 4、打印二叉树； 5、对二叉树实现前序、中序、后序遍历； 算法思想： 建立一棵只有头结点的二叉树，并通过调用插入左子树和插入右子树操作，依次将上图中的结点插入二叉树中，利用二叉树的特殊中序遍历方法将该树以凹入表示法打印显示。最后，调用二叉树的前序、中序、后序遍历函数对二叉树进行遍历，并显示遍历结果。 (2)、哈夫曼树 设有字符集{A、B、C、D}，各字符在电文中出现的次数集为{1，3，5，7}，设计各字符的哈夫曼编码。 要求： 1、构造字符集的哈夫曼树，其结点数据结构如下： weight flag parent leftChild rightChild 2、由哈夫曼树构造哈夫曼编码，输出权值及其对应的编码。 算法思想： 首先，由给定的n个权值构造有2n-1个结点的哈夫曼树。在哈夫曼树中，其叶结点的权值为相应的给定权值，非叶结点的权值为其孩子结点的权值之和。 哈夫曼树构造过程如下： 1. 根据给定的 n 个权值 {w1，w2，…，wn}，构成的 n 棵二叉树的森林 F = {T1，T2，…，Tn}，其中每棵二叉树 Ti 中只有一个权值为 wi 的结点，其左、右子树均为空； 2. 在 F 中选取根结点的权值最小和次小的两棵树作为左、右子树构造一棵新的二叉树，且置新二叉树的根结点的权值为其左、右子树上根结点的权值之和； 3. 在 F 中删除这两棵二叉树，并将新二叉树加入到 F 中； 4. 重复 2 和 3，直到 F 中只含一棵树为止。这棵树就是哈夫曼树。 其次，对n个结点的哈夫曼树进行不等长编码。保证任何一个字符的哈夫曼编码不为另一字符的哈夫曼编码的前缀。 实验过程： 实验中的关键语句： 前序遍历中序遍历什么的都是一个道理，只是输出的时候的顺序不同，都是先访问左孩子或者右孩子后在访问另一边 (1) 先序遍历二叉树T的递归算