中文版教材主要数据结构.ppt

哈 夫 曼 树 与 哈 夫 曼 编 码 最优树的定义 如何构造最优树 前缀编码 * 线性表的顺序存储结构 typedef struct { } SqList; // 俗称 顺序表 #define LIST_INIT_SIZE 100 // 线性表存储空间的初始分配量 #define LISTINCREMENT 10 // 线性表存储空间的分配增量 ElemType *elem; // 存储空间基址 int length; // 当前长度 int listsize; // 当前分配的存储容量 // (以sizeof(ElemType)为单位) Typedef struct LNode { ElemType data; // 数据域 struct Lnode *next; // 指针域 } LNode, *LinkList; 线性表的链式存储结构 LinkList L； // L 为单链表的头指针 #define MAX_TREE_SIZE 100 // 二叉树的最大结点数 typedef TElemType SqBiTree[MAX_ TREE_SIZE]; // 0号单元存储根结点 SqBiTree bt; 二叉树的顺序存储表示 例如: A B C D E F A B D C E F 0 1 2 3 4 5 6 7 8 9 10 11 12 13 1 4 0 13 2 6 A B C D E F G A B C E D F G root A B C E D F G 树的二叉链表 (孩子-兄弟）存储表示法 最优树的定义 树的路径长度定义为： 树中每个结点的路径长度之和。 结点的路径长度定义为： 从根结点到该结点的路径上 分支的数目。 树的带权路径长度定义为： 树中所有叶子结点的带权路径长度之和 WPL(T) = ?wklk (对所有叶子结点)。 在所有含 n 个叶子结点、并带相同权 值的 m 叉树中，必存在一棵其带权路径 长度取最小值的树，称为“最优树”。 例如： 2 7 9 7 5 4 9 2 WPL(T)= 7?2+5?2+2?3+4?3+9?2 =60 WPL(T)= 7?4+9?4+5?3+4?2+2?1 =89 5 4 根据给定的 n 个权值 {w1, w2, …, wn}， 构造 n 棵二叉树的集合 F = {T1, T2, … , Tn}， 其中每棵二叉树中均只含一个带权值 为 wi 的根结点，其左、右子树为空树； 如何构造最优树 (1) (赫夫曼算法) 以二叉树为例： 在 F 中选取其根结点的权值为最 小的两棵二叉树，分别作为左、 右子树构造一棵新的二叉树，并 置这棵新的二叉树根结点的权值 为其左、右子树根结点的权值之 和； (2) 从F中删去这两棵树，同时加入 刚生成的新树； 重复 (2) 和 (3) 两步，直至 F 中只 含一棵树为止。 (3) (4) 9 例如: 已知权值 W={ 5, 6, 2, 9, 7 } 5 6 2 7 5 2 7 6 9 7 6 7 13 9 5 2 7 6 7 13 9 5 2 7 9 5 2 7 16 6 7 13 29 0 0 0 0 1 1 1 1 00 01 10 110 111 指的是，任何一个字符的编码都 不是同一字符集中另一个字符的编码 的前缀。 前缀编码 利用赫夫曼树可以构造一种不等长的二进制编码，并且构造所得的赫夫曼编码是一种最优前缀编码，即使所传电文的总长度最短。 A