数据结构》课件C语言06（NEW.ppt

森林与二叉树的转换 树、森林与二叉树之间有一个自然的一一对应关系。 转换方法： 树 ? 二叉树 兄弟结点间加连接（虚线） 让每个结点只与最左孩子保持联系，与其余孩子的关系去掉 森林 ? 二叉树 森林 ? 树 ? 二叉树 （添加一个虚根结点） 去掉虚根结点 森林与二叉树的转换 森林与二叉树的对应关系 (1) 森林转化成二叉树的形式化规则： 若F={T1，T2，…，Tm} 是森林，则： ? 若F为空，即n = 0，则 对应的二叉树B为空二叉树。 ? 若F不空，则 对应二叉树B的根root (B)是F中第一棵树T1的  根root (T1)； 其左子树为B (T11, T12, …, T1m)，其中，T11,  T12, …, T1m是root (T1)的子树； 其右子树为B (T2, T3, …, Tn)，其中，T2, T3, …,  Tn是除T1外其它树构成的森林。 二叉树到森林的转换 转换方法： 若某结点是其双亲的左孩子，则把该结点的右孩子、右孩子的右孩子、…，都与该结点的双亲结点连接起来。 然后去掉所有双亲结点到右孩子的连线 二叉树 ? 树 仅当根结点无右孩子； 　二叉树 ? 森林 仅当根结点有右孩子。 (2) 二叉树转换为森林的形式化规则： 若B=( root, LB, RB ) 是一棵二叉树，则： ? 如果B为空，则 对应的森林F也为空。 ? 如果B非空，则 F中第一棵树T1的根为root； T1的根的子树森林{ T11, T12, …, T1m }是由  root 的左子树 LB 转换而来； F 中除了 T1 之外其余的树组成的森林{ T2, T3, …,  Tn } 是由 root的右子树 RB 转换而成的森林。 树的遍历 先序遍历 若树非空，则 1、访问根结点 2、依次先序遍历树的各子树 A B C D E F G H I J 先序遍历序列： A，B，E，F，C，G，D，H，I，J 后序遍历 若树非空，则 1、依次后序遍历树的各子树 2、访问根结点 A B C D E F G H I J 遍历序列： E，F，B，G，C，H，I，J， D，A 层序遍历 A B C D E F G H I J 遍历序列： A，B，C，D，E，F，G，H，I，J 6. 6 赫夫曼树及其应用 最优二叉树（赫夫曼树）的概念 路径长度：两个结点之间的路径长度是连接两结点的路径上的分支数。 树的路径长度：是树中各结点到根结点的路径长度之和。 具有不同路径长度的二叉树 树的带权路径长度：是树的各叶结点所带的权值与该结点到根的路径长度的乘积的和。 例：给定4个叶子结点，分别对应权值7，5，2，4，可以构造如下三棵二叉树： 赫夫曼树 在权为w1,w2,…,wn的n个叶子结点的所  有二叉树中，带权路径长度WPL最小的二叉 树中称为最优二叉树（赫夫曼树）。 3 2 4 7 Huffman树 赫夫曼树的特点？ 赫夫曼树的构造方法： (1) 根据给定的n个权值{w1 , w2 , …, wn}，构造n棵二叉树的集合F = {T1, T2, …, Tn}，其中每棵二叉树中均只含一个带权值为wi的根结点,其左、右子树为空树; (2) 在F中选取其根结点的权值为最小的两棵二叉树，将这两棵树合并成一棵新树。即添加一个新结点，将所选的两棵树分别作为新结点的左、右子树，并置这棵新的二叉树根结点的权值为其左、右子树根结点的权值之和; (3) 重复(2)，直至F 中只含一棵树为止。 ?赫夫曼编码 在远程通讯中，要将待传字符串转换成二进制的0、1序列。 最简单的编码方式是采用等长编码 设要传送的字符为： ABACCDA 若编码为：A—00 B—01 C—10 D---11 若将编码设计为长度不等的