文档详情

第六章树(数据结构).ppt

发布:2017-12-29约1.94万字共89页下载文档
文本预览下载声明
* 讨论2:二叉树怎样还原为树? a b e i d f h g c 要点:把所有右孩子变为兄弟! a b e i d f h g c * 法一: ① 各森林先各自转为二叉树; ② 依次连到前一个二叉树的右子树上。 讨论3:森林如何转为二叉树? 法二:森林直接变兄弟,再转为二叉树 (参见教材P138图6.17,两种方法都有转换示意图) 即F={T1, T2, …,Tm} B={root, LB, RB} * A B C D E F G H J I A B C D E F G H J I A B C D E F G H J I 森林转二叉树举例:(法二) 兄弟相连 长兄为父 孩子靠左 头根为根 A * 讨论4:二叉树如何还原为森林? 要点:把最右边的子树变为森林,其余右子树变为兄弟 A B C D E F G H J I A B C D E F G H J I E F A B C D G H J I 即B={root, LB, RB} F={T1, T2, …,Tm} * 2. 树和森林的存储方式 树有三种常用存储方式: ①双亲表示法 ②孩子表示法 ③孩子兄弟表示法 (1)用双亲表示法来存储 思路:用一组连续空间来存储树的结点,同时在每个结点中附设一个指示器,指示其双亲结点在链表中的位置。 parents data 结点结构 data parents 1 树结构 2 3 n * A B C G E I D H F 缺点:求结点的孩子时需要遍历整个结构。 0 1 2 3 4 5 6 7 8 1 2 2 3 3 A B C D E F G H I -1 0 0 1 例1: 双亲表示法 * 思路:将每个结点的孩子排列起来,形成一个带表头(装父结点)的线性表(n个结点要设立n个链表); 再将n个表头用数组存放起来,这样就形成一个混合结构。 例如: a b e c d f h g d e f g h g f e d c b a h 1 2 3 4 5 6 7 8 (2)用孩子表示法来存储 b c * 思路:用二叉链表来表示树,但链表中的两个指针域含义不同。 左指针指向该结点的第一个孩子; 右指针指向该结点的下一个兄弟结点。 nextsibling data firstchild (3)用孩子兄弟表示法来存储 指向左孩子 指向右兄弟 * a b e c d f h g b a c e d f g h 问:树转二叉树的“连线—抹线—旋转” 如何由计算机自动实现? 答:用“左孩子右兄弟”表示法来存储即可。 存储的过程就是转换的过程! 例如: * 先序遍历 若森林为空,返回; 访问森林中第一棵树的根结点; 先序遍历第一棵树中根结点的子树森林; 先序遍历除去第一棵树之后剩余的树构成的森林。 中序遍历 若森林为空,返回; 中序遍历森林中第一棵树的根结点的子树森林; 访问第一棵树的根结点; 中序遍历除去第一棵树之后剩余的树构成的森林。 3.森林的遍历 A B C D E F G H J I * 路 径: 路径长度: 树的路径长度: 带权路径长度: 树的带权路径长度: 霍 夫 曼 树: 6.5 Huffman树及其应用 一、最优二叉树(霍夫曼树) 由一结点到另一结点间的分支所构成 路径上的分支数目 从树根到每一结点的路径长度之和。 结点到根的路径长度与结点上权的乘积 预备知识:若干术语 d e b a c f g 树中所有叶子结点的带权路径长度之和 带权路径长度最小的树。 a→e的路径长度= 树长度= 2 10 * Huffman树简介: 树的带权路径长度如何计算? WPL = ?wklk k=1 n a b d c 7 5 2 4 (a) c d a b 2 4 5 7 (b) b d a c 7 5 2 4 (c) 经典之例: WPL=36 WPL=46 WPL= 35 哈夫曼树则是:WPL 最小的树。 Huffman树 Weighted Path Length * (1) 由给定的 n 个权值{w0, w1, w2, …, wn-1},构造具有 n 棵扩充二叉树的森林F = { T0, T1, T2, …, Tn-1 },其中每一棵扩充二叉树 Ti 只有一个带有权值 wi 的根结点,其左、右子树均为空。 (2) 重复以下步骤, 直到 F 中仅剩下一棵树为止: ① 在 F 中选取两棵根结点的权值最小的扩充二叉树, 做为左、右子树构造一棵新的二叉树。置新的二叉树的根结点的权值为其左、右子树上根结点的权值之和。 ② 在 F 中删去这两棵二叉树。 ③ 把新的二叉树加入 F。 构造霍夫曼树的基本思想: 构造Huffman树的步骤(即Huffman算
显示全部
相似文档