数据结构讲义第6章.ppt

§6.1 树的基本概念 树的基本概念 树的基本操作 树的基本术语 树的逻辑表示 树的逻辑表示 §6.2 二叉树 二叉树的基本运算 二叉树的性质 二叉树的性质 二叉树的性质 二叉树的性质 二叉树的存储结构 二叉树的存储结构 §6.3 二叉树的遍历 二叉树先序遍历 二叉树先序遍历 二叉树中序遍历 二叉树中序遍历 二叉树后序遍历 二叉链表的建立 §6.4 线索二叉树 线索二叉树 线索二叉树的建立 线索二叉树的建立 §6.5 树的存储结构 树的存储结构 树的存储结构 树的遍历 §6.6 哈夫曼树及其应用 哈夫曼树 哈夫曼树构造 哈夫曼编码 哈夫曼编码实现 哈夫曼编码实现 哈夫曼译码的实现 作业 三、孩子兄弟表示法：树的二叉树表示法或二叉链表表示法。 采用二叉链表作为树的存储结构。 结点的两个指针域分别指向该结点的第一个孩子和下一个兄弟。 结点结构： typedef struct CSNode{ ElemType data; struct CSNode *firstchild, *nextsibling; }CSNode, *CSTree; A B C D E F G H firstchild data nextsibling A ^ ^ C E B D ^ ^ F ^ ^ G ^ H ^ 孩子兄弟表示法给出了将树转换为二叉树和将二叉树转换为树的方法。 三种遍历方法： 先根遍历：先访问根结点，然后依次先根遍历根的每棵子树。 后根遍历：先依次后根遍历根的每棵子树，然后访问根结点。（相当于转换成二叉树后的中序遍历） 层次遍历：先访问根结点，然后从左到由访问第二层结点，再照此访问第三层结点。 A B C D E F G H 先根：ABEFCDGH 后根：EFBCGHDA 层次：ABCDEFGH 一、基本术语 路径: 从一结点到另一结点上的分支构成这两个结点的路径。 路径长度: 路径上的分支数目。 树的路径长度: 从根到所有结点的路径长度之和。 结点的带权路径长度: 从该结点到树根之间的路径长度与 结点上权值的乘积。 树的带权路径长度: 树中所有叶子结点的带权路径长度之和。 WPL= ∑ wk Lk n k=1 n 为叶结点数 wk为叶结点k的权值 Lk 为叶结点k的路径长度 定义: 设有n 个权值 {w1,w2,......wn}，试构造具有 n 个叶结点的二叉树，每个叶结点权值为 wi ，则其中带权路径长度WPL最小的二叉树称为哈夫曼树(最优二叉树)。 a b c d 7 5 2 4 a b c d 7 5 2 4 a b 7 5 c d 2 4 WPL=2*（7+5+2+4）=36 WPL=3*（7+5）+2*4+2=46 WPL=3*（2+4）+2*5+7=35 特点:权值越大的叶子离根越近。 若叶结点上的权值均相同，则完全二叉树一定是最优二叉树，否则完全二叉树不一定是最优二叉树。 (1) 根据给定的n个权值 {w1,w2,......wn}, 生成 n 棵二叉树的集合F= {T1,T2,.......Tm};其中每棵二叉树Ti只有一个带权为Wi的根结点，左右子树为空。 (2) 在 F 中选择两棵根结点值最小的树 Ti ,Tj 作为左右子树,构成一棵新二叉树Tk , Tk根结点值为Ti ,Tj根结点权值之和; (3) 在 F 中删除Ti ,Tj ,并把 Tk 加到 F中; (4) 重复 (2) (3),直到 F中只含一棵树。 例：w={7，5，2，4} 7 5 2 4 6 7 5 2 4 4 2 7 11 5 6 18 7 11 5 6 2 4 数据的压缩过程称为编码，解压过程称为解码。 编码：将文件中的字符转换为唯一的一个二进制串。 解码：将一个二进制串转换为对应的字符。 定长编码：设编码字符个数为n,码长为k，则k= ?log2n+1?。 不等长编码：使出现频率最多的字符采用尽可能短的编码。 前缀编码：对不等长编码，要求任一字符的编码都不是另一个字符的编码的前缀。 采用二叉树设计前缀编码：用二叉树的叶结点表示待编码的字符，并约定左分支表示字符‘0’，右分支表示字符‘1’，则从根结点到叶子结点的路径上分支字符组成的字符串作为该叶子结点的编码。由此得到的编码必为二进制的前缀编码。 方法：以n种字符出现的频率作权，设计一棵哈夫曼树，由此得到字符的二进制前缀