第三章：树-2021-11

【树的定义与基本术语】 树是一种抽象的数据结构，它由相同类型的元素构成的集合，具有特定的层次关系。在树中，有一个特殊的结点称为根结点，它是树的起点。除了根结点，剩余的结点可以分为k个互不相交的子集，每个子集自身也构成一棵树，这些子树被称为根结点的子树。这种结构通过递归的方式定义，即每一棵子树都可以看作是一棵独立的树。 在数学模型中，一棵树可以用二元关系R来表示，其中R定义了树中结点之间的父子关系。根结点在关系R下没有前驱结点，而其他非根结点则有唯一的前驱结点。树的划分对应于子树，每个子树由对应的二元关系划分出来，并且这些子树自身满足树的定义。 【二叉树】 二叉树是树的一个特例，每个结点最多有两个子结点，分别称为左子结点和右子结点。二叉树通常有两种存储方式：顺序存储结构（如数组）和链式存储结构（如指针链接）。二叉树的遍历有四种主要方法：前序遍历（根-左-右）、中序遍历（左-根-右）、后序遍历（左-右-根）以及层次遍历。线索二叉树是一种特殊的二叉树，通过添加线索指针使得在非递归情况下也能进行二叉树遍历。 【树的性质与应用】 树的结构性质包括度（结点的子树数量）、高度（从根结点到最远叶子结点的最长路径）、路径、路径长度等。树在计算机科学中有广泛应用，例如二叉排序树用于排序，平衡二叉树（如AVL树和红黑树）保持树的平衡以提高查找效率，哈夫曼树则用于数据压缩的哈夫曼编码。 【森林与二叉树的转换】 森林是由多棵树组成的集合，可以通过一定的转换规则转化为二叉树，反之亦然。这种转换有助于理解和操作复杂的树结构。 【教学要求】 学习树数据结构与算法，要求理解树的基本概念，掌握二叉树的定义、性质和遍历算法，理解树的存储表示方法，熟悉森林与二叉树的相互转换，以及树在各种实际问题中的应用，比如二叉排序树、平衡二叉树和哈夫曼树等。 总结来说，树是数据结构中的核心概念，二叉树作为其特例，在计算机科学中扮演着重要角色。理解树的定义、性质、存储和遍历算法，对于掌握高级数据结构和算法至关重要。