树的概念其实十分地宽泛，也十分地常见，大家见到这个词千万不要惊恐，因为真的每天你都能见到树结构在咱们生存中的利用。比如说公司的组织构造：

另外像咱们家里的族谱，或者说是咱们的家庭构造，也是一个典型的树结构。此外，在计算机领域，咱们天天要打交道的【文件夹】、数据库中咱们存储的数据，都是树的典型的利用。明天咱们来学习的就是比拟偏实践的对于树和二叉树的定义以及它们的一些属性特点。

树

从下面理论生存中的例子里，咱们能够看出，树这种构造是能够演绎出它的一些特点的。

树（Tree）是 N (N>0)个结点的无限集，它或为空树（N=0）; 或为非空树 T。

在这个定义中，咱们须要明确两个问题：一是树肯定是有结点的，二是依据结点数量能够分为空树和非空树两种。不过这只是最根本的定义，它还有一些个性。

有且仅有一个称之为根的结点。

也就是说，这个树肯定是从某一个结点开始扩大进去的，这个结点就向树根一样。从它开始向外开枝散叶。

除根结点以外的其余结点可分为 m (m > 0) 个互不相交的无限集 T1，T2 ……，Tm 其中每一个汇合自身又是一颗树，并且称为根的子树（SubTree）

这一段可能会不太好了解，其实说白了就是每个结点只有一个下级结点，不能有多个下级结点。同理，平级结点之间也不能有分割，然而它能够有多个上级结点。

对于树的定义咱们能够看下上面这个图。

上图中简略的列举了规范的树和不规范的树是什么样子的。其中：

• (a)，是只有一个根结点的树，只有有一个结点，它就能够称为一个树结构
• (b)，是一个规范的树结构
• (c)，留神它的 C 和 H 结点之间有一条连接线，这个就不是树了，结点只能有一个下级结点的才称为树，这个其实就是咱们未来要学的【图】了

树的相干术语

绝对于栈的压（入）栈、出栈，队列的入队、出队来说，树的相干术语可就简单的多了。不论如何，首先你得先记住这些术语，要不前面讲的货色用得那些术语只会让你更晕。不过咱们一时记不住也没关系，先有个大略的印象，在前面的学习过程中遇到了再回来温习，这样印象反而会更加粗浅。

• 结点：一个结点可能蕴含一组数据，或者指向其它结点的分支，能够看作是树枝分叉的那个中央，(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：在二叉树的第 i 层上至少有 2^i-1 个结点（i >= 1）

性质 2：深度为 k 的二叉树至少有 2^k – 1 个结点（k >= 1）

性质 3：对任何一颗二叉树 T，如果其终端结点数为 n₀，度为 2 的结点数为 n₂，则 n₀ = n₂ + 1

性质 4：具备 n 个结点 的齐全二叉树的深度为 log₂n + 1

性质 5：如果对一颗有 n 个结点 的齐全二叉树（其深度为 log₂n + 1）的结点按层序编号（从第 1 层到第 log₂n + 1 层，每层从左到右），则对任一结点 i（1 <= i <= n），有：

1. 如果 i = 1，则结点 i 是二叉树的根，无双亲；如果 i > 1，则其双亲是结点 i / 2
2. 如果 2i > n，则结点 i 无左孩子（结点 i 为叶子结点）；否则其左孩子是结点 2i
3. 如果 2i + 1 > n，则结点 i 无右孩子；否则其右孩子是结点 2i + 1

对于二叉树的上述五个性质的数学证实咱们就不具体说了，毕竟咱们这一系列的文章的主旨也是心愿通过简略的示例让大家学习到数据结构和算法的精华，而不是简略粗犷的间接用数学公式来推导证实，那么咱们就间接来图上数一数就好了。

• 对于 性质 1 来说，咱们以后这个二叉树依据公式的话，在第 3 层上最多只能有 2^3-1 个结点，也就是 4 个结点。第 4 层上最多只能有 2^4-1，也就是 2³ = 8 个结点
• 对于 性质 2 来说，以后这图中的树的深度为 4，也就是最多有 2⁴ – 1 = 15 个结点
• 性质 3 的话，咱们先数数度为 2 的结点有多少，在这个图中，度为 2 的结点有 7 个，也就是 A、B、C、D、E、F、G，第 4 层的结点都是没有子结点的，也就是说它们都是 0 度的，也称为终端结点（叶子结点），这些结点的数量一共是 8 个。当初 n₂ = 7，依据性质公式就能够得出 n₀ = n₂ + 1 = 7 + 1 = 8
• 图中的结点数量为 15 个，套用 性质 4 的公式能够得出 log₂n + 1 = log₂15 + 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 版，天勤考研

===========

各自媒体平台均可搜寻【硬核项目经理】