| 出版日期：2003-03-03 总期号：507 本年期号：07 |
|
 |
树的复习与总结
《中国电脑教育报》陈智罡 树是整个《数据结构》的重点章节，而其中的二叉树又是本章的重点内容。本章在试题中所占分数达到20%左右，如加上其他章节与二叉树有关的二叉排序树等内容，则占有四分之一以上的分值，可见树是十分重要的内容，务必仔细掌握各个知识点。 在这一章里要了解树的定义熟悉二叉树的定义、性质、存储结构、遍历、线索化和树的存储结构、遍历以及树、森林与二叉树的转换，哈夫曼树及哈夫曼编码等内容。算法的重点是二叉树的遍历及其有关应用，这也是本章的难点。 树与二叉树 树的逻辑结构特征是：树中任一结点都可以有零个或多个直接后继（孩子）结点，但至多只能有一个直接前趋（双亲）结点。树形结构是非线性结构。二叉树是n（n≥0）个结点的有限集，它或者是空集（n=0），或者由一个根结点及两棵互不相交的分别称作这个根的左子树和右子树的二叉树组成。 二叉树不是树的特殊情形，这一点似乎不容易理解。问题就在于二叉树是无论结点是否只有一个孩子，它都要确定是左孩子或右孩子，而度数为二的有序树虽然很像二叉树，但是当结点只有一个孩子时，就无须区分它是左还是右的次序。（也就是二叉树每个结点位置或者说次序都是固定的，可以是空，但是不可以说它没有位置，而树的结点位置是相对于别的结点来说的，没有别的结点时，它就无所谓左右了），因此二者是不同的。二叉树的画法是一定要会。 二叉树的顺序存储结构就是把二叉树的所有结点按照一定次序（从根结点起，从上层到下层，从左往右编号就得到了存放的次序）存储到一片连续的存储单元中 。对于顺序存储方式的二叉树，可以根据结点的编号可以直接得出结点之间的逻辑关系，这里应该会计算应用，比如知道一个结点的序号为3，要我们计算其双亲的序号，兄弟、孩子等序号。只要对完全二叉树的形态了如指掌，这样的计算也是易如反掌的。 顺序存储方式对于完全二叉树而言，其结构简单又节省空间，但是对于一般二叉树并不合适。因此树的存储结构更多的是用链式存储。结点的结构为两个指针域lchild和rchild分别指向该结点的左孩子和右孩子，另有一个数据域data存放结点数据。把所有二叉树的结点，加上一个指向根结点的指针就构成了二叉树的链式存储结构，称为二叉链表。它就是由根指针root惟一确定的。 二叉树的遍历 根据访问结点的次序不同可得三种遍历：先序遍历（前序遍历或先根遍历），中序遍历（或中根遍历）、后序遍历（或后根遍历）。遍历的算法就是一个递归算法。对于一给定的二叉树，根据不同的遍历方法，应能得出其相应的结点访问次序。只要将搜索路线上所有在第一次、第二次、第三次经过的结点分别列表就可得到该二叉树的前序序列、中序序列和后序序列。 树和森林 树和森林及二叉树的转换：三者是惟一对应的，它们之间的转换办法应掌握。树的存储结构：有双亲链表表示法（就是在每个结点设一指针指向其双亲以惟一的表示任何一棵树，用向量表示），这种表示法中指针是向上链接的，所以对于求指定结点的双亲或祖先十分方便，但不适于求指定结点的孩子及后代。 还有“孩子链表”表示法（就是为树中每个结点设置一个孩子链表，并将结点及相应的孩子链表的头指针存放在一个向量中）孩子链表表示便于实现涉及孩子结点及子孙的运算，但不便于实现与双亲有关的运算。因此可以两种表示法结合形成双亲孩子链表表示法。 第三种是“孩子兄弟链表”表示法（就是在存储结点信息的同时，附加两个分别指向该结点的最左孩子和右邻兄弟的指针域）这种存储结构的最大优点是，它和二叉树的二叉链表表示完全一样，因此可利用二叉树的算法来实现对树的操作。 因为树和森林每个结点都有两棵以上的子树，因此不便于讨论中根次序遍历，但是其前序遍历和后序遍历还是应该了解的。 事实上，树和森林的前序遍历和后序遍历可用与该树（森林）相对应的二叉树的前序遍历和中序遍历算法来实现。它们是相同的。 哈夫曼树及其应用 树的应用很广泛，哈夫曼树就是其中之一。哈夫曼树的应用最广泛的是在编码技术上，它能够容易地求出给定字符集及其概率分布的最优前缀码。（最优前缀码就是平均码长最小的前缀码） 哈夫曼编码的构造很容易，只要画好了哈夫曼树，按分支情况在左路径上写代码0，右路径上写代码1，然后从上到下到叶结点的相应路径上的代码的序列就是该结点的最优前缀码。 例：在什么样的情况下，等长编码是最优的前缀码﹖ 答：在每个字符的使用概率相同的情况下，也即在哈夫曼树中每片叶子的权重相等的时候，等长编码是最优的前缀码。 |
||||||||||||||||||||||
