石河子大学信息科学与技术学院数据结构课件第六章 树和二叉树（3）.ppt

* 数据结构 tjm * 《 数据结构》 第六章 树和二叉树 (下) 静态双亲链表的类型定义参见P135 6.4 树和森林 6.4.1 树的存储结构 双亲表示法 实现：定义数组存放树的结点，每个结点含两个域： 数据域：存放结点本身信息。双亲域：指示本结点的双亲结点在数组中的位置。 特点：找双亲容易，找孩子难。 a b c d e f h g i －1 0 1 1 2 4 4 4 0 a c d e f g h i b data parent 5 0 1 2 3 4 6 7 8 a b c d e f h g i 1 2 ^ 3 4 ^ 8 6 7 ^ 5 ^ 5 0 1 2 3 4 6 7 8 a c d e f g h i b ^ ^ ^ ^ ^ data fc 孩子链表表示法（类型定义参见P136） 每个结点的孩子结点用单链表存储，再用含n个元素的数组指向每个孩子链表。 5 0 1 2 3 4 6 7 8 a c d e f g h i b data fc 1 2 3 4 8 6 7 5 ^ ^ ^ ^ ^ ^ ^ ^ ^ －1 0 1 1 2 4 4 4 0 parent a b c d e f h g i 带双亲的孩子链表 a b c d e f h g i a b c d e f g h i ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ 孩子兄弟表示法（二叉树表示法） 实现：用二叉链表作树的存储结构，链表中每个结点的两个指针域分别指向其第一个孩子结点和下一个兄弟结点。 A C B E D 树 A B C D E 二叉树 A ^ ^ B C ^ D ^ ^ E ^ A ^ ^ B C ^ D ^ ^ E ^ 6.4.2 森林与二叉树的转换 A ^ ^ B C ^ D ^ ^ E ^ A B C D E F G H I A B C D E F G H I A B C D E F G H I A B C D E F G H I A B C D E F G H I 树转换成的二叉树其右子树一定为空。 加线：在兄弟之间加一连线。抹线：对每个结点，除了其左孩子外，抹掉其与其余孩子之间的连线。旋转：将树作适当的旋转即可。 将树转换成二叉树 A B C D E F G H I A B C D E F G H I A B C D E F G H I A B C D E F G H I A B C D E F G H I 将二叉树转换成树加线：若某结点是双亲结点的左孩子，则将该结点的右孩子，右孩子的右孩子，……沿分支找到的所有右孩子，都与该结点的双亲用线连起来。抹线：抹掉原二叉树中双亲与右孩子之间的连线。调整：将结点按层次排列，形成树结构。 A B C D E F G H I J A B C D E F G H I J A B C D E F G H I J A B C D E F G H I J 森林转换成二叉树将各棵树分别转换成二叉树。将每棵树的根结点用线相连。以第一棵树根结点为二叉树的根，再以根结点为轴心，顺时针旋转，构成二叉树型结构。 A B C D E F G H I J A B C D E F G H I J A B C D E F G H I J A B C D E F G H I J 二叉树转换成森林抹线：将二叉树中根结点与其右孩子连线，及沿右分支有哪些信誉好的足球投注网站到的所有右孩子间连线全部抹掉，使之变成孤立的二叉树。还原：将孤立的二叉树还原成树。 6.4.3 树的遍历 （1）树的先根遍历 树的后根遍历 （2）森林的先序遍历 森林的中序遍历 若给定树的先根和后根序列则可唯一地确定一棵树。 6.6 哈夫曼树及其应用 6.6.1 最优二叉树（哈夫曼树） 从树中一个结点到另一个结点之间的分支构成这两个结点间的路径。路径长度：路径上的分支数。树的路径长度：从树根到每个结点的路径长度之和。 结点的带权路径长度：从该结点到树根之间的路径长度与结点上权的乘积。 树的带权路径长度：树中所有叶子结点的带权路径长度之和。记作： 设有n个权值{w1,w2,……wn}，构造一棵有n个叶子结点的二叉树，第i个叶子的权值为wi,则wpl最小的二叉树叫最优二叉树（哈夫曼树）,即带权路径长度最短的