数据结构－第06章 节 －树和二叉树_02.pptVIP

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 6.6 赫夫曼编码–概述 主要用途是实现数据压缩。如在远程通讯中，要将待传字符转换成二进制的字符串： 设要传送的字符为： 若编码为：A—00 B—01 C—10 D—11 若将编码设计为长度不等的二进制编码，即让待传字符串中出现次数较多的字符采用尽可能短的编码，则转换的二进制字符串便可能减少。 00010010101100 ABACCDA 6.6 赫夫曼编码–概述续 设要传送的字符为：ABACCDA 若编码为：A—0 B—00 C—1 D—01 关键：要设计长度不等的编码，则必须使任一字符的编码都不是另一个字符的编码的前缀。 ABACCDA 000011010 但： 0000 AAAA ABA BB 重码 第六章 树和二叉树 6.1 树的定义和基本概念 6.2 二叉树 6.2.1 树的定义和基本术语 6.2.2 二叉树的性质 6.2.3 二叉树的存储结构 6.3 遍历二叉树和线索二叉树 6.3.1 遍历二叉树 6.4 树和森林 6.4.1 树的存储结构 6.4.2 森林与二叉树的转换 6.6 Huffman树及其应用 6.6.1 Huffman树 6.6.2 Huffman编码 第六章 树和二叉树 主要内容及基本要求 1、主要内容 树的定义和基本术语（6.1节） 二叉树及其存储结构（6.2节） 遍历二叉树（6.3.1节） 哈夫曼树（6.6节） 2、基本要求 掌握二叉树的结构特征 掌握二叉树的基本操作，特别是遍历算法 学会运用遍历算法实现二叉树的其它操作 掌握Huffman编码方法 6.4 树和森林 6.4.1 树的三种存储结构 一、双亲表示法 二、孩子链表表示法 三、孩子兄弟表示法 树的存储结构——1.双亲表示法 6.4 树与森林 6.4 树与森林 树的存储结构－－双亲表示法 typedef struct PTNode { Elem data; int parent; // 双亲位置域 } PTNode; data parent #define MAX_TREE_SIZE 100 结点结构: 6.4 树与森林 树的存储结构——2. 孩子表示法 A B C D E F G H I J A B C D E F G H I J 1 2 3 7 8 9 4 5 6 0 1 2 3 4 5 6 7 8 9 树的存储－－孩子表示法 typedef struct CTNode { //孩子结点结构 int child; struct CTNode *next; } *ChildPtr; ? typedef struct { // 孩子链的头指针 TElemType data; ChildPtr firstchild; } CTBox; 6.4 树与森林 data firstchild child next 6.4 树与森林 树的存储－－孩子表示法 typedef struct { CTBox nodes[MAX_TREE_SIZE]; int n, r; // 结点数和根结点的位置 } CTree; 6.4 树与森林 双亲-孩子表示法（改进孩子表示法） A B C D E F G H I J -1 A 0 B 0 C 0 D 1 E 1 F 2 G 3 H 3 I 3 J 1 2 3 7 8 9 4 5 6 0 1 2 3 4 5 6 7 8 9 3. 孩子兄弟表示法（左孩子-右兄弟表示法） 树的左子女-右兄弟表示 data firstChild nextSibling 6.4 树与森林 6.4.2 森林与二叉树的转换 图 6.17 6.4.2 森林与二叉树的转换 (1) 森林转化成二叉树的规则