大厂首发：必考的算法与数据结构，再问你一遍二叉树很难吗？

前言

这次梳理的内容是数据结构专题中的树，如果你看到树这类数据结构时，满脑子头疼，觉得它很难理解，如果是这样子的话，那么本文可能对你或许有点帮助。

树的基本概念

树是用来模拟具有树状结构性质的数据集合。或者你可以把它认为是一种抽象数据结构或是实现这种抽象数据类型的数据结构，用来模拟具有树状结构性质的数据集合。

那么根据维基百科给出的定义，我们似乎可以这么理解：

它是由n（n>0）个有限节点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。它具有以下的特点：

• 每个节点都只有有限个子节点或无子节点；
• 没有父节点的节点称为根节点；
• 每一个非根节点有且只有一个父节点；
• 除了根节点外，每个子节点可以分为多个不相交的子树；
• 树里面没有环路(cycle)

这个时候，我们就需要拿出一张图来看👇

从图中来看，以上的五个特点都可以很好的总结出来

• A节点作为根节点，没有父节点，所以是根节点。
• 除根节点（A）外，其他的节点都有父节点，并且每个节点只有有限个子节点或无子节点。
• 从某个节点开始，可以分为很多个子树，举个例子，从B节点开始，即是如此。

既然对树有一定认识后，我们需要了解它的一些术语。

基本术语

为了更加规范的总结，这里给出的描述来自于维基百科：

1. 节点的度：一个节点含有的子树的个数称为该节点的度；
2. 树的度：一棵树中，最大的节点度称为树的度；
3. 叶节点或终端节点：度为零的节点；
4. 非终端节点或分支节点：度不为零的节点；
5. 父亲节点或父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点；
6. 孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点；
7. 兄弟节点：具有相同父节点的节点互称为兄弟节点；
8. 节点的层次：从根开始定义起，根为第1层，根的子节点为第2层，以此类推；
9. 深度：对于任意节点n,n的深度为从根到n的唯一路径长，根的深度为0；
10. 高度ÿ