第6章树和二叉树讲述资料.ppt

2.6 二叉树的存储结构 熟悉二叉树的各种存储结构的特点及适用范围。 1、顺序存储 按照顺序存储结构的定义，用一组地址连续的存储单元依次自上而下、自左至右存储完全二叉树上的结点元素，即将完全二叉树上编号为i的结点元素存储在如上定义的一维数组中下标为i-l的分量中。 优点：存储结构简单 缺点：深度为k的二叉树需2k-1个存储单元，空间利用率低。 2、二叉链表存储结构 设计不同的结点结构可构成不同形式的链式存储结构。 这种存储结构的优点是访问结点的孩子很方便。且空间利用率高。 人有了知识，就会具备各种分析能力， 明辨是非的能力。 所以我们要勤恳读书，广泛阅读， 古人说“书中自有黄金屋。 ”通过阅读科技书籍，我们能丰富知识， 培养逻辑思维能力； 通过阅读文学作品，我们能提高文学鉴赏水平， 培养文学情趣； 通过阅读报刊，我们能增长见识，扩大自己的知识面。 有许多书籍还能培养我们的道德情操， 给我们巨大的精神力量， 鼓舞我们前进。 * 图6.16 树与二叉树的对应关系示例 D E C B A E D C B A E D C B A A D E C B 树 二叉树 对应 A B C D E 存储 存储 解释 解释 从树的二叉链表表示的定义可知，任何一棵树和对应的二叉树，其右子树必空。若把森林中第二棵树的根结点看成是第一棵树的根结点的兄弟，则同样可导出森林和二叉树的对应关系。例如， 森林与二叉树对应 树与二叉树对应 树根连接 D C B A F E J I H G D C B A F E J I H G J I H D C G F E B A 这个一一对应的关系导致森林或树与二叉树可以相互转换，其形式定义如下 一、森林转换成二叉树 如果F={Tl，T2，…，Tm}是森林，则可按如下规则转换成一棵二叉树B=(root，LB，RB)。 (1)若F为空，即m=0，则B为空树； (2)若F非空，即m!=0，则B的根root即为森林中第一棵树的根ROOT(T1)；B的左子树LB是从Tl中根结点的子树森Fl={T11,T12,…T1m}转换而成的二叉树；其右子树RB是从森林F’={T2,T3,…,Tm}转换而成的二叉树。 二、二叉树转换成森林 如果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 赫夫曼树及其应用 赫夫曼(Huffman)树，又称最优树，是一类带权路径长度最短的树。 6.6.1 最优二叉树(赫夫曼树) 首先给出路径和路径长度的概念。从树中一个结点到另一个结点之间的分支构成这两个结点之间的路径，路径上的分支数目称做路径长度。树的路径长度是从树根到每一结点的路径长度之和。6.2.1节中定义的完全二叉树就是这种路径长度最短的二叉树。 若将上述概念推广到一般情况，考虑带权的结点。结点的带权路径长度为从该结点到树