数据结构第05章 树和二叉树_c.ppt

* * 所得哈夫曼编码： * * 作业： 1、假设用于同信的电文仅由8个字母组成，字母在电文中出现的频率分别为0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10。试为这8个字母设计哈夫曼编码。 0.07 0010 0.19 10 0.02 00000 0.06 0001 0.32 01 0.03 00001 0.21 11 0.10 0011 * * 2.已知二叉树如下图所示，此二叉树的顺序存储结构是：( )。 ? ○A ? / ? ○C ? / \ ? ○F ○G ?? * * 3.一棵二叉树有67个结点，这些结点的度要么是0，要么是2。这棵二叉树中度为2的结点有( )个。 4.树和二叉树的差别。 5.设一棵二叉树结点的先根序列为ABDECFGH，中根序列为DEBAFCHG.则二叉树中叶子结点是( )。 5.假设一棵二叉树的先序遍历序列是 EBADCFHGIKJ；中序遍历序列是 ABCDEFGHIJK。请画出该二叉树。 * * 实验报告 课程：算法与数据结构 试验序号及名称二叉树的操作 一、实验目的：掌握二叉树的基本操作算法 二、实验环境：Tubor C 2.0 三、实验内容： ? 用前序遍历的方法创建一个二叉树, 输出前序、中序、后序遍历序列；编程计算树的高度，并查找指定的数据是否存在。 程序 四、实验结果： * * 小结 1.树的基本概念 2.二叉树概念,满二叉树，完全二叉树 　性质1,2,3,4,5,6 3.二叉树的存储 4.二叉树遍历：DLR、LDR、LRD。 5.利用前序或后序,中序判定一棵二叉树 5.树的存储 7.树,二叉树,森林的转换 8.树,森林的遍历 9.哈夫曼树的构造及其编码算法 * 树型结构是一类重要的非线性结构。树型结构是结点之间有分支，并且具有层次关系的结构，它非常类似于自然界中的树。 * 符号?x?表示不大于x的最大整数，反之，「x┐表示不小于x的最小整数。 * 用一组地址连续的存储单元，以层序顺序存放二叉树的数据元素，结点的相对位置蕴含着结点之间的关系。 * 性质6 含有n个结点的二叉链表中，有n+1个空链域。 二叉树存储方法的选择，主要依赖于所要实施的各种运算的频度。 * 黑板上画这个过程 * 将一颗二叉树变成线索二叉树时，该二叉树的初始状态应该是：每个结点的左右线索标志域均为０，若结点有左孩子或右孩子，则相应的指针域应指向该孩子结点，否则指针域为空，以便在线索化的过程中加入线索。 * * 二叉树到森林的转换示例 * * （1）树的遍历 ① 先序（根）遍历：访问树的根结点，再依次先序遍历根的每棵子树（从左到右）。 ② 后序（根）遍历：依次后序遍历根的每棵子树（从左到右），最后访问根结点。 ③ 层次遍历：从上到下、从左至右访问树的每一个结点。 2、树和森林的遍历 先序遍历序列为ABCEFGD 后序遍历序列为BEFGCDA 层次遍历序列为ABCDEFG * * （2） 森林的遍历 ① 先序遍历。若森林非空，按下述规则遍历： ? 访问森林中第一棵树的根结点。 ? 先序遍历第一棵树根结点的子树森林。 ? 先序遍历除去第一棵树后剩余树构成的森林。 ② 后序遍历。若森林非空，按下述规则遍历： ? 后序遍历森林中第一棵树根结点的子树森林。 ? 访问第一棵树的根结点。 ? 后序遍历除去第一棵树后剩余树构成的森林。 2、树和森林的遍历 先序遍历序列为： ABCEFGDHJKLMNP。 后序遍历序列为： BEFGCDAJKHMNLP。 * * 由森林转换成二叉树时，其第一棵树的子树森林转换成左子树，剩余树构成的森林转换成右子树。因此，森林的先序遍历和后序遍历即为其对应二叉树的先序遍历序列和中序遍历序列。 * * 例题： 1.对下图所示的森林： 　　 (1)求各树的前序序列和后序序列； (2)求森林的前序序列和后序序列； (3)将此森林转换为相应的二叉树； (1) (a)的前序序列：ABCDEF 后序序列：BDEFCA????? (b)的前序序列：GHIJK 后序序列：IJKHG????? (c)的前序序列：LMPQRNO 后序序列：QRPMNOL? (2) 此森林的前序序列： ABCDEFGH