《数据结构》笔记：树与二叉树详解

在清华大学严蔚敏和吴伟民的经典教材《数据结构》中，第六章深入探讨了树和二叉树这一重要主题。树是一种数据结构，由一个特定的根节点以及若干个互不相交的子树组成，每个子树自身也是一个树。树的表示方法多样，包括树形表示法、嵌套集合表示法、凹入表表示法和广义表表示法，这些方法有助于理解和操作树的结构。 树的基本概念包括结点的度（子树数量）、叶子节点和分支节点的定义，以及根节点、开始节点、内部节点等术语。树中的路径和层次关系也是关键概念，如祖先和子孙关系，以及计算节点的层数和树的高度。有序树和无序树的区别在于子树是否有特定的顺序。 二叉树作为树的一种特殊形式，具有独特的性质。它由一个根节点和两个互不相交的子树构成，且子树的度限制在2。二叉树的层上结点数、总结点数与深度之间的关系非常有规律，例如满二叉树和完全二叉树的概念就强调了这些特性。满二叉树每层结点数达到最大，而完全二叉树则是除了最后一层可能不满，其余各层都是满的，且最后一层的结点尽可能地集中在左边。 存储二叉树时，顺序存储结构是一种常用的方法，通过将完全二叉树按照层次和左右顺序编号，然后存储在连续的内存空间中。这种结构便于遍历和搜索，同时也揭示了二叉树的内在结构特征。 总结来说，《数据结构》中的树和二叉树章节为读者提供了深入理解这两个基本数据结构的理论基础和实践操作技巧，这对于从事IT行业的人来说是不可或缺的知识点，无论是进行算法设计、数据库管理还是软件工程，都离不开对树和二叉树的掌握。