"树与二叉树：定义、基本术语和表示方式"

【数据结构】第七周 树和二叉树 《【数据结构】第七周 树和二叉树.pdf》是个人观看青岛大学王卓老师数据结构课程的课堂笔记。本文主要讨论树和二叉树。 树是由n(n≥0)个结点组成的有限集合。当n=0时，称为空树；当n>0时，它满足以下两个条件：1. 只有一个称为根（root）的结点；2. 其余结点可分为m(m≥0)个互不相交的有限集合T1, T2, T3, ..., Tm，其中每一个集合本身也是一颗树，称为根的子树。树的定义是递归的。树可以有多种表示方式。 树的基本术语如下：1. 根结点：非空树中无前驱结点的结点。2. 结点的度：结点拥有的子树数。3. 树的度：树内各结点的最大度数。4. 叶子：终端结点，度为0。5. 分支结点：非终端结点，度不为0。6. 根结点以外的分支结点称为内部结点。7. 结点的子树的根称为该结点的孩子，该结点称为孩子的双亲。8. 树的度：树内各结点的度的最大值。9. 树的深度：树中结点的最大层次。10. 森林：是m(m≥0)颗互不相交的树的集合。树一定是森林，但森林不一定是树。如果给森林中的各子树加上一个双亲结点，森林就变成了树。因此，一棵树可以看作是一个特殊的森林。 二叉树是一种特殊的树结构，它是由n(n≥0)个结点组成的有限集合。每个结点最多只有两个子树，且子树分别称为左子树和右子树，它们是有序的。二叉树的定义是递归的。 在讨论二叉树时，我们经常提到以下术语：1. 树的度为2，或者说树中每个结点的度最大为2。2. 二叉树的深度：二叉树中结点的最大层次。3. 二叉树的度为0的结点称为叶子结点，度为1的结点称为分支结点。4. 二叉树的左子树和右子树是有序的。5. 满二叉树：如果一个二叉树的所有分支结点的度都为2，并且叶子结点都在同一层上，那么这个二叉树是满二叉树。6. 完全二叉树：对一颗具有n个结点的二叉树按层序编号，如果编号为i(1≤i≤n)的结点与同样深度的满二叉树中编号为i的结点在二叉树中位置完全相同，则这颗二叉树是完全二叉树。 树和二叉树是数据结构中重要的非线性结构，它们在实际应用中有广泛的应用。了解树和二叉树的基本概念、术语以及定义是理解和应用这两种数据结构的基础。通过本文的介绍，读者可以对树和二叉树有一个全面的了解，并能够准确地描述和操作它们。 总结：本文详细介绍了树和二叉树的定义、基本术语以及一些特殊类型的树和二叉树。树和二叉树是非常重要的数据结构，它们在实际应用中有广泛的应用，因此了解它们的概念和特点是非常必要的。通过深入学习和理解树和二叉树的相关知识，读者可以更好地应用它们解决实际问题。