数据结构6.树和二叉树.ppt

二、前缀码与等长码的比较 weight llink rlink plink 14 0 0 7 23 0 0 8 7 0 0 6 6 0 0 6 50 0 0 9 13 4 3 7 27 6 1 8 50 2 7 9 5 8 0 100 14 23 50 6 7 13 27 50 (2) 找两个根结点的值最小的二叉树 50 和 50构造一个新的二叉树。 100 在静态三叉链中构造huffman树 1 2 3 4 5 6 7 8 9 1 1 1 \0 23 0 0 8 7 0 0 6 6 0 0 6 50 0 0 9 14 23 50 6 7 13 27 50 100 三、构造huffman码 hc[1] Hc[2]hc[3]hc[4]hc[5] 1 0 0 \0 1 0 1 2 3 4 5 cd 0 0 0 0 1 1 1 1 23 7 6 50 例如：abcabcddaabbadabda 编码：010101011010001101001100 译码：？？？？？？？？？？？？ 问题：？？？？？ 为什么？ 思考：设通信用4个字符a,b,c,d, 分别出现 7, 5, 2和4次 编码分别为：0，1，10，01 结果？ 小结: 树形结构的逻辑特点是，每个结点最多只有一个前驱，但可以有多个后继，可以有多个终端结点。 树和二叉树是两种典型的树形结构。在树中，每个结点的度数不受限制。在二叉树中，每个结点的度数最多是2，而且有有左子树和右子树之分。 满二叉树和完全二叉树是两种形态特殊的二叉树。高度为h的满二叉树一定有2h－1个结点。高度为h的完全二叉树结点个数大于2h－1-1小于等于2h－1，而且最底层的结点都集中在该层最左边的若干连续的位置上。 双亲数组、孩子链表和二叉链表是树的三种常用的存储结构。 二叉树一般用二叉链表表示。 顺序表示法一般只用于表示完全二叉树。 小结: 遍历树形结构实际上是一个将树形结构中的结点排成一个线性序列的过程。这个线性序列与树形结构的存储方法无关，但与遍历的具体方法有关。 树的遍历方法常用的有前序遍历、后序遍历和层次遍历三种。二叉树的遍历方法常用的有前序遍历、中序遍历、后序遍历和层次遍历四种。 二叉树前序遍历、中序遍历和后序遍历都是以递归的形式定义的，因此，很容易用递归算法描述。 用非递归算法描述二叉树的前序遍历、中序遍历和后序遍历，需要定义栈。 在二叉树的层次遍历算法中要使用队列。 在本章中要求学生熟练掌握二叉树的遍历方法和算法, 并能够灵活应用。 小结: 线索二叉树也是一种用来表示二叉树的二叉链表。在这种二叉链表中，每个结点的空的左孩子指针域中放入了在某种遍历次序下该结点的前驱结点的地址；每个结点的空的右孩子指针域中放入了在这种遍历次序下该结点的后继结点的地址。这种附加的指针值称为线索。给二叉树的二叉链表存储结构加上线索的过程称为线索化二叉树。这个过程可通过对二叉树进行相应次序的遍历来实现。根据遍历方法的不同，线索二叉树一般分前序线索二叉树、中序线索二叉树和后序线索二叉树三种。 小结: 最优二叉树是一种特殊的二叉树：不存在度为1的结点，每个树叶都对应一个权值，而且具有最小的带权路径长度值。 哈夫曼树是指用哈夫曼方法构造出来的最优二叉树。 哈夫曼树可用于字符的编码。哈夫曼编码是一种不等长的二进制编码。其特点是字符的编码长度和字符的使用频率成反比；各字符的编码之间不需要分隔符。 * 欢迎辞 * * * * 森林是m（m=0）棵互不相交的树的集合。 6.4.2 树的存储结构1、双亲表示法 O a c g b d e f 2、孩子链表 O a c g b d e f 3、孩子—兄弟链 (左孩子-右兄弟) O a c g b d e f 6.4.3 树、森林与二叉树的转换 1、树转换成二叉树 O a c g b d e f O a c g b d e f (左孩子-右兄弟) 2、森林转换成二叉树 O a c g b d e f (2) 沿右兄弟链将多个树链在一起 a b O c g d e f (1) 将每一个树转换成二叉树 6.4.4 树和森林的遍历 1、树的遍历 O a c g b d e f 先序遍历： （1）访问根结点 （2）先序遍历每一个子树   先序