【本章小结】 　　在这一章讨论了树和二叉树两种数据类型的定义以及它们的实现方法。树是以分支关系定义的层次结构，结构中的数据元素之间存在着"一对多"的关系，因此它为计算机应用中出现的具有层次关系或分支关系的数据，提供了一种自然的表示方法。如用树描述人类社会的族谱和各种社会组织机构。在计算机学科和应用领域中树也得到广泛应用，例如在编译程序中，用树来表示源程序的语法结构等。 　　二叉树是和树不同的另一种树型结构，它有明确的左子树和右子树，因此当用二叉树来描述层次关系时，其"左孩子"表示"下属关系"，而"右孩子"表示的是"同一层次的关系"。由于二叉树还是以后各章中讨论其它问题时经常用到的工具，因此二叉树的几个重要特性是我们应该熟练掌握的。 　　树和二叉树的遍历算法是实现各种操作的基础。对非线性结构的遍历需要选择合适的搜索路径，以确保在这条路径上可以访问到结构中的所有数据元素，并使每一个数据元素只被访问一次。由于树和二叉树是层次分明的结构，因此按层次进行遍历是自然的事，它必能实现既访问到所有元素，又不会重复访问。此外，对树和二叉树还可进行先左后右的遍历。 　　遍历的实质是按某种规则将二叉树中的数据元素排列成一个线性序列，二叉树的线索链表便可看成是二叉树的一种"线性"存储结构，在线索链表上可对二叉树进行"线性化"的遍历，即不需要"递归"，而是从"第一个元素"起，逐个访问"后继元素"直至"后继"为"空"止。因此线索链表是通过遍历生成的，即在遍历过程中保存结点之间的"前驱"和"后继"的关系，并为方便起见，在线索链表中添加一个"头结点"，并由此构成一个"双向循环链表"。在实际应用时也可简化为"单向循环链表"（即只保存后继或前驱关系）。 　　在这一章作为应用，介绍了最优树和最优前缀编码的构造方法，最优树是一种"带权路径长度最短"的树，最优前缀编码是最优二叉树的一种应用。

【本章小结】