树的概念其实很广泛也很常见。看到这个词不要惊慌，因为在我们的生活中每天都能看到树结构的使用。 。比如公司的组织结构：

另外，我们家族的家谱或者我们的家族结构也是典型的树形结构。另外，在计算领域，我们每天处理的[文件夹]和数据库中存储的数据都是树的典型应用。今天我们将介绍树和二叉树的更多理论定义以及它们的一些属性和特征。

树

从上面的现实例子中，我们可以看到树的结构可以概括它的一些特征。

树是 N (N>0) 个节点的有限集合。它要么是空树（N=0），要么是非空树T。

在这个定义中，我们需要澄清两个问题：一是树必须有节点，二是根据节点的数量，可分为空树和空树两种。但这只是最基本的定义，它还有一些属性。

只有一个节点，称为根。

换句话说，这棵树必须从等于树根的特定节点延伸。它们开始从它向外分支。

除根节点外，其余节点均可分为m（m > 0）个不相交的有限集T1，T2...，Tm。每个字符串本身就是一棵树，称为根。子树（SubTree）

这一段可能不太好理解。其实坦白讲，每个节点只有一个父节点，不能有多个父节点。同理，水平节点之间不能有连接，但可以有多个子节点。

对于树的定义，我们可以看下图。

上图仅显示了标准树和非标准树的样子。其中：

• (a)是一棵只有一个根节点的树。只要有一个节点，就可以称为树结构
• (b)是标准的树结构
• (c)，注意节点C和H之间有一条连接线。这不是一个树。一个节点只能有一个父节点，称为树。这其实就是我们以后要学习的【图】。

与树相关的表达式

与将 (v) 进栈和出栈以及入队和出队相比，与树相关的表达式要复杂得多。无论如何，您需要首先记住这些术语，否则我们稍后讨论的术语只会让您更加困惑。但即使我们现在不记得也没关系。我们可以先得到一个粗略的印象，然后在学习过程中遇到它时再回过头来回顾。这样印象就会更深。

• 节点：节点可以包含数据集或指向其他节点的分支。它可以被认为是一个分支分支的地方。 (b) A、B、C、D、E 等。图中这些是节点的度
• ：一个节点所拥有的子树的数量称为该节点的度。其实就是它有多少个子子节点的度。图(b)中，节点C。该点的度为1，节点D的度为3
• 树度：树中每个节点的度的最大值为最子节点的个数，这棵树的度为， (b) 图中树的度为 3
• 叶子：度为 0 的节点，即没有子节点的节点。 (b) 图中的 K、L、F、G、M、I、J 是这棵树的叶节点
• 父节点和子节点：节点的子节点是其子节点；对于这些子节点，当前节点是父节点，(b) 图中，D 的子节点为 H、I、J，H、I、J 的父节点为级别 D
• ：计数从根节点开始，根节点是第一级，根子节点是第二级，依此类推。 ，(b)图中节点G的层数为3，(a)图中所有层数都只有1
• 树深度（高度）：树的当前最高层数，显然(b)图深度为4
• 兄弟、祖先和孩子：兄弟节点是父节点，这些节点是同一个节点；祖先节点是从根节点到指定节点的所有节点；后代是从给定节点到目标节点的路径上的所有节点。 (b) 图中，E 和 F 是兄弟姐妹，E 的祖先是 A 和 B，E 的后代是 K 或 L
• 表兄弟：所有处于同一级别但父母不同的节点都是表兄弟。同样在图(b)中，G的表兄弟是E和F。此外，H、I和J也是他的表兄弟。

二叉树

树的概念有了一定的了解后，我们进一步学习另一个概念，这也是数据结构和算法中树最重要的形式：二叉树。

一般来说，树的形状会不断变化。例如，一个节点可能有 3 个子节点，而另一节点可能有 300 个子节点。这样一棵没有任何规则的树实际上会很难管理，但是二叉树的定义要简单得多。除了树的属性外，它还有另一个内容：二叉树的每个节点最多有两个子节点。 ，即整个二叉树的度必须为2，并且所有节点的度不会超过2。我们将在下一节的二叉树的属性中详细解释为什么二叉树易于管理。所有的树结构都可以通过一定的适当变形转换为二叉树。

我们还用一个图来展示什么是二叉树。

在二叉树中，左子节点及其子节点可以视为当前节点的左子树。右节点及其后续节点也可以认为是当前节点的右子树。根据一个节点的子节点，有如下图所示的几种二叉树形式。

• (a) 树是只有一个节点的树，也可以称为只有一个节点的二叉树。
• (b) 该树是一棵只有一个左节点的二叉树。
• (c) 树是一棵有一个右节点的二叉树
• (d) 树是一棵有两个左右节点的二叉树

二叉树的性质

性质 1：最多有 2 个 在二叉树第 i 层 i-1 节点 (i >= 1)

性质 2：深度为 k 的二叉树最多有 2k - 1 个节点(k >= 1)

性质 3：对于任意二叉树 T，如果终端节点数为 n0，度为 2 的节点数为 n2，则 n 0 = n 2 + 10 性质 4：n 个节点的完全二叉树的深度为 log2n + 1

性质 5：如果对于 n 个节点的完全二叉树（其深度为 log） n + 1) 节点按层顺序编号（从 1. 层到 log2n + 1 层，每层从左到右），则对于任意节点 i (1

关于二叉树 我们不再详细介绍上述五个性质的数学证明。最终，本系列文章的目的是让大家通过简单的例子来学习数据结构和算法的本质，而不是简单粗暴地使用数学公式。推导和证明，那么我们直接在图中数就可以了。

• 对于性质1，根据公式，我们当前的二叉树在第三层最多可以有23-1节点，即4个节点。第四层最多可以有 24-1，即 23 = 8 个节点
• 对于特征 2，当前图像中树的深度为 4。这意味着在最多 24 - 1 = 15 个节点
• 对于属性 3，我们首先统计度数为 2 的节点数。在该图中，度数为 2 的节点有 7 个，即、A、B、C、D、E、F、G，第四级节点没有子节点，也就是说都是0度，也称为终端节点（叶子节点）。 ），这些节点的总数为 8。现在 n2 = 7。根据性质公式，我们可以得到 n0 = n2 + 1 = 7 + 1 = 8
• 的个数图中的节点数为 15 。使用属性公式 4，我们可以得出 log2n + 1 = log215 + 1 = 3.91（向下取整）+ 1 = 3 + 1 = 4，深度当前树的值为 4，属性 4 和 2 可见。两个操作是互补的
• 对于属性5，注意每个节点边上的数字。作为示例，我们将选择节点 E。节点 E 当前为 5，因此其父节点为 5/2 = 2（向下舍入）； E的左孩子为2i，即2*5=10，E的右孩子为2i + 1，即2*5+1 = 11；属性定义5比较抽象，用叶子节点来说明，目标是整个二叉树，但实际上含义和我们这里解释的一样。您可以与其他节点进行检查。性质5对于使用顺序结构来存储二叉树非常重要，我们稍后会讨论！

请掌握并记住二叉树的这五个属性及其含义，因为在接下来的学习中，无论是二叉树的顺序、链式内存结构还是遍历二叉树，你都可能会接触到上面的内容。内容分为五个属性。可以说它们是二叉树学习中最基本的灵魂。

森林

最后我们简单了解一下什么是“森林”。几棵树连在一起就形成了“森林”。就像上面的二叉树说明图一样，(a)(b)(c)(d)放在一起看作为一个整体就是一个“森林”，而这个“森林”里有(a)(b)(c)(d) ）这四棵树。森林中的树木之间没有任何联系。如果我们想要经营或穿越森林，我们常常把森林变成一棵树。具体算法和步骤不是我们研究的重点，所以任何人都可以理解。想要深入学习的同学可以搜索相关内容或者查看相关教材。

总结

从栈、队列到树的后面，突然感觉自己迈出了一大步？有点困惑？没关系，今天的内容其实是一些基础理论内容。如果你能理解，就理解。如果不懂就继续学习然后再回来看今天的概念。学习并不涉及不断重复进步过程。当然，一切都必须有基础。了解了树数据结构和一些简单的遍历算法后，再回来深入理解和记忆这些概念。我相信一般面试中不会出现关于树木的问题。我们一起努力吧！

参考资料：

《数据结构》第二版，严伟民

《数据结构》第二版，陈越

《数据结构高分笔记》2020年版天琴研究生入学考试