20147 §6.5树和森林 §6.5树和森林 1. 树、森林与二叉树的转换 2. 树的存储结构 ③二叉树=>树或森林 ①双亲链表表示法 设x是y的左孩子，则将x的右孩子，右孩子的右孩子。 每结点双亲唯一 故存储结点时，增加一个 都与y相连 parent城指向双亲，用向量表示较方便使 去掉所有双亲到右孩子的连线 0 123456 7890 d A B C D E F G H 1J Fi6. met-1000112333 特点：向上链接，根的parent为-1 求指定结点双亲(O(1)及祖先(O(h)方便 求指定结点孩子及后代须遍历数组O( 类型说明略) §6.5树和森林 §6.5树和森林 2树的存储结构 2树的存储结构 少孩子链表表示法 孩子链表表示法（续） 若k叉树用k叉链表表示，会导致浪费空间 特点：易实现找结点的孩子及子州向下查找易】 :树边n-1条 难实现找结点的双亲及祖先（向上查找难） 空指针kn-n-1)=n(k-1)+1 双亲孩子链衰囊示法 设度数域，结点不等长、运算不便 在孩子链表中，增加parent位域 热新表膏被鑫警轩佳表。持结点及相应玻子 此方法结合了双亲链表和孩子链表的优点，向上向下 查找均方仅 rot0厚 置四 类型说明：略 ③孩子兄弟链表表示法 品吧四 制=之二叉树时，结点关系由：量左孩子、右邻兄弟表 SF A Leftmootchid data rightsibling 相当干二又链表 §65树和森林 s6.6 Huffman?树及其应用 3. 树和森林的遍历 86.6.1最优二叉树 ①先序速历树 1. 概念 先访问树的根；然后依次先序速历根的每棵子树 结点路径长度：根到该结点所经过的边数 后序速历制 先依次后序遍历根的每棵子树：然后访问树的根： 树的路径长度：所有结点的路径长度之和 雪先序撞历森林 (结点数相同时，完全二叉树的路径长度最短) 先访问森林中第一棵树的根；然后先序遍历第一操树中 ●结点的带权路径长度： 点的各子 成的森林：最后先序遍历除第一棵 外其它树构成的森林 结点的权值W,X结点的路径长度 ④后序速历森林 ●树的带权路径长度（实际上是加权外部路径长度 后序速历森林中第一操树的根结点的各子树所抱成的森 所有叶子的加权路径长度之和 林，然后访问第一操制的根：景后后序遍历除幕一棵外 其它树构成的林 P一∑以形：第个叶子的权（实数 1:第í个叶子的路径长度2014/4/7 8 §6.5 树和森林 1. 树、森林与二叉树的转换 ③ 二叉树 => 树或森林 • 设x是y的左孩子，则将x的右孩子，右孩子的右孩子， 都与y相连 • 去掉所有双亲到右孩子的连线 43 §6.5 树和森林 2. 树的存储结构 ① 双亲链表表示法 ∵每结点双亲唯一，故存储结点时，增加一个 parent域指向双亲，用向量表示较方便 44 • 特点：向上链接，根的parent为-1 求指定结点双亲(O(1))及祖先(O(h))方便 求指定结点孩子及后代须遍历数组O(n) • 类型说明(略) §6.5 树和森林 2. 树的存储结构 ② 孩子链表表示法 • 若k叉树用k叉链表表示，会导致浪费空间 ∵ 树边n-1条 ∴ 空指针kn-(n-1)=n(k-1)+1 • 设度数域，结点不等长、运算不便 45 • 孩子链表：每结点设一孩子链表，将结点及相应孩子 链表的头指针放在一向量中。 §6.5 树和森林 2. 树的存储结构 ② 孩子链表表示法（续） • 特点：易实现找结点的孩子及子孙(向下查找易) 难实现找结点的双亲及祖先(向上查找难) • 双亲孩子链表表示法 在孩子链表中，增加parent域 46 此方法结合了双亲链表和孩子链表的优点，向上向下 查找均方便 • 类型说明：略 ③ 孩子兄弟链表表示法 树 => 二叉树时，结点关系由：最左孩子、右邻兄弟表 示 §6.5 树和森林 3. 树和森林的遍历 ① 先序遍历树 先访问树的根；然后依次先序遍历根的每棵子树 ② 后序遍历树 先依次后序遍历根的每棵子树；然后访问树的根； ③ 先序遍历森林 先访问森林中第 棵树的根 然后先序遍历第 棵树中 47 先访问森林中第一棵树的根；然后先序遍历第一棵树中 根结点的各子树所构成的森林；最后先序遍历除第一棵 外其它树构成的森林 ④ 后序遍历森林 后序遍历森林中第一棵树的根结点的各子树所构成的森 林；然后访问第一棵树的根；最后后序遍历除第一棵外 其它树构成的森林 先序遍历恰好等价于先序遍历对应的二叉树，后序遍历 恰好等价于中序遍历对应的二叉树。 §6.6 Huffman树及其应用 §6.6.1 最优二叉树 1. 概念  结点路径长度：根到该结点所经过的边数  树的路径长度：所有结点的路径长度之和 (结点数相同时，完全二叉树的路径长度最短)  结点的带权路径长度 48 ： 结点的权值Wi × 结点的路径长度li  树的带权路径长度(实际上是加权外部路径长度) 所有叶子的加权路径长度之和 1 : i : i n ii i i i WPL wl w l = =  第 个叶子的权(实数) 第 个叶子的路径长度