数据结构课件-第六章.ppt

3交换左右子树 6.5 线索二叉树  当以二叉链表作为存储结构时，只能找到结点的左、右孩子信息，而不能直接得到结点在任一序列中的前驱和后继信息，这种信息只有在遍历的动态过程中才能得到。 如何保存这种在遍历过程中得到的信息呢？一个最简单的办法是在每个结点上增加两个指针域fwd和bkwd，分别指示结点在遍历时得到的前驱和后继信息。 以这种结点结构构成的二叉链表作为二叉树的存储结构，叫做线索链表，其中指向结点前驱和后继的指针，叫做线索。加上线索的二叉树称之为线索二叉树（Threaded Binary Tree）。例如图6-5-2（a）所示为中序线索二叉树，与其对应的中序线索链表如图6-5-2（b）所示。 1．双亲表示法 6.6树和森林 6.6.1树的存储结构 2．孩子表示法：树中每个结点可能有多棵子树，一种办法是把每个结点的孩子结点排列起来，看成是一个线性表，且以单链表作存储结构，则n个结点有n个孩子链表（叶子的孩子链表为空表）。 3．孩子兄弟表示法：又称二叉树表示法，或二叉链表表示法。即以二叉链表作树的存储结构。链表中结点的两个链域分别指向该结点的第一个孩子结点和下一个兄弟结点，分别命名为firstchild域和nextsibling域。  6.6.2树、森林与二叉树的转换  任何一棵和树对应的二叉树，其右子树必空。若把森林中第二棵树的根结点看成是第一棵树的根结点的兄弟，则同样可导出森林和二叉树的对应关系。 1．森林转换成二叉树 如果F={T1, T2,…,Tm}是森林，则可按如下规则转换成一棵二叉树B=(root，LB，RB)。 (1)若F为空，即m=0，则B为空树； (2)若F非空，即m≠0，则B的根root即为森林中第一棵树的根ROOT(T1)；B的左子树LB是从T1中根结点的子树森林F1={T11，T12，…，T1m}转换而成的二叉树；其右子树RB是从森林F’={T2，T3，…，Tm}转换而成的二叉树。 2．二叉树转换成森林 如果B=(root，LB，RB)是一棵二叉树，则可按如下规则转换成森林F={ T1，T2，…，Tm）； (1)若B为空，则F为空； (2)若B非空，则F中第一棵树T1的根ROOT(T1)即为二叉树B的根root；T1中根结点的子树森林F1是由B的左子树LB转换而成的森林；F中除T1之外其余树组成的森林F’={ T2，T3，…，Tm}是由B的右子树RB转换而成的森林 6.6.3 树和森林的遍历 由树结构的定义可引出两种次序遍历树的方法：一种是先根（次序）遍历树，即：先访问树的根结点，然后依次先根遍历根的每棵子树；另一种是后根（次序）遍历，即：先依次后根遍历每棵子树，然后访问根结点。 对图6-6-4的树进行先根遍历，可得树的先根序列为 A B C D E 若对此树进行后根遍历，则得树的后根序列为 B D C E A 6.7 哈夫曼树及其应用 最优二叉树，又称哈夫曼(Haffman)树，是指对于一组带有确定权值的叶结点，构造的具有最小带权路径长度的二叉树。 路径：从树中一个结点到另一个结点之间的分支构成这两个结点间的路径。 路径长度：路径上的分支数目称为路径长度。 结点的带权路径长度：从某结点到根结点之间的路径长度与该结点上权的乘积为该结点的带权路径长度。 树的路径长度：从树的根结点到树中每一个结点的路径长度之和。 树的带权路径长度：树中所有叶子结点的带权路径长度之和。 树的带权路径长度通常表示为 其中wk为第k个结点的权值，lk为第k个结点的路径长度 下面给出最优二叉树(哈夫曼树)的正式定义：设有n个权值{w1,w2,……wn}，构造一棵有n个叶子结点的二叉树，每个叶子的权值为wi，则其中WPL最小的二叉树叫做最优二叉树或哈夫曼树。 那么如何找到带权路径长度最小的二叉树(即哈夫曼树)呢？ 哈夫曼(Haffman)依据这一特点提出了一种方法，这种方法的基本思想是：将给定的n个权值{w1,w2,...,wn}作为n个根结点的权值构造一个具有n棵二叉树的森林{T1,T2,...,Tn}，其中每棵二叉树只有一个根结点；1.在森林中选取两棵根结点权值最小的二叉树作为左右子树构造一棵新二叉树，新二叉树的根结点权值为这两棵树根的权值之和；2.在森林中，将上面选择的这两棵根权值最小的二叉树从森林中删除，并将刚刚构造的二叉树加入到森林中；3.重复上面步骤2和步骤3，直到森林中只有一棵二叉树为止。这棵二叉树就是哈夫曼树。 哈夫曼树可用于构造使电文的编码总长最短的编码方案。具体做法如下：设需要编码的字符集合为{d1，d2，…，dn}，它们在电文中出现的次数或频率集合为{w1，w2，…，wn}，