树其实很宽泛，也很常见。看到这个词不要惊慌，因为你每天都能看到我们生活中的树状结构。应用。比如公司的组织结构：另外，我们家的家谱，或者说我们的家族结构，也是典型的树型结构。另外，在计算机领域，我们每天要打交道的【文件夹】，我们存储在数据库中的数据，都是树的典型应用。今天我们要学习的是树和二叉树的更理论化的定义，以及它们的一些属性。树从上面现实生活中的例子，我们可以看出树结构可以概括它的一些特点。树（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的节点，即没有子节点的节点，图中的K、L、F、G、M、I、Jb)是这棵树的叶节点。父子节点：一个节点的子节点是它的子节点；对于这些子节点，当前节点是它的父节点。(b)图中，D的子节点为H、I、J，而H、I、J的父节点为D层：从根节点开始计算，根节点为第一层，子节点为D层root为第二层，以此类推，(b)图中G节点的层级为3，(a)图中所有层级都只有1层树的深度（高度）：树的当前最大层级，显然，(b)图的深度是4个兄弟，祖先和后代：兄弟节点是这些节点的父节点是同一个A节点；祖先节点是从根节点到指定节点途中的所有节点；后代是从某个节点到目标节点的所有节点。(b)图中E和F是兄弟，E的祖先是A和B，E的后代是K或L的表亲（cousin）兄弟：同层但父代不同的所有节点是cousins，同样在图（b）中，G的表亲是E，F，而H，I，J也是它的表亲。二叉树对树的概念有了一定的了解之后，我们再进一步学习另一个概念，也是数据结构和算法中树最重要的一种形式：二叉树。一般来说，树的形状是可以变化的，比如一个节点可能有3个子节点，而另一个节点可能有300个子节点。这样一棵没有任何规则的树其实操作起来很麻烦，二叉树的定义就简单多了。除了树的性质外，它还多了一个内容：二叉树的每个节点至多有两个子节点，也就是说整棵二叉树的度数必须为2，并且所有的度数节点不会超过2个。至于二叉树为什么好操作，我们会在下一节二叉树的属性中详细讲解。所有的树结构都可以通过一定的规则变形转化为二叉树。我们还用一张图来说明什么是二叉树。在二叉树中，左子节点及其后代可以看作是当前节点的左子树。右节点及其后代也可以看作是当前节点的右子树。根据节点的子节点，上图中有几种二叉树形式。(a)一棵树是一棵只有一个节点的树，或者一棵二叉树只有一个节点(b)一棵树是一棵只有一个左节点的二叉树(c)一棵树是一棵只有一个右节点的二叉树(d)该树是一棵具有左右节点的二叉树。性质1：二叉树的第i层最多有2i-1个节点（i>=1）。性质2：一棵深度为k的二叉树至多有2k-1个节点（k>=1）性质3：对于任意二叉树T，若终端节点数为n0，且度数为2的节点数为n2，则n0=n2+1性质4：具有n个节点的完全二叉树的深度为log2n+1。性质5：如果具有n个节点的完全二叉树的节点（其深度为log2n+1)按顺序编号（从第1层到log2n+1层，每层从左到右），那么对于任意节点i（1<=i<=n），有：如果i=1，则节点i是二叉树的根节点，没有父节点；如果i>1，它的父节点是节点i/2。如果2i>n，那么节点i没有左孩子（节点i是叶子节点）；否则它的左孩子是节点2i。如果2i+1>n，则节点i没有右孩子；否则，它的右孩子就是节点2i+1。关于二叉树的上述五个性质的数学证明，我们不再赘述。毕竟我们这个系列文章的目的就是让简单的例子让大家学到数据结构和算法的精髓，而不是简单的直接用数学公式推导证明，然后直接上图算就行了。对于性质1，根据公式，我们现在的二叉树第三层最多只能有23-1个节点，也就是4个节点。第4层最多只能有24-1个，即23=8个节点。对于性质2，当前图中树的深度为4，即最多有24-1=15个节点。3的情况，我们先统计度数为2的节点个数，在这个图中，有7个度数为2的节点，即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)这四棵树。森林中的树木之间没有联系。如果我们要经营或穿越一片森林，往往会将森林变成一棵树。具体的算法和步骤不是我们研究的重点，大家可以了解一下。想深入学习的同学可以搜索相关内容或查阅相关教材。小结从栈和队列推进到树之后，是不是突然觉得自己迈出了一大步？有点困惑？没关系，今天的内容其实就是一些基础的理论内容。如果你能理解它，你就能理解它。如果看不懂，可以继续研究，然后再回来看今天的概念。学习不是不断重复进步的过程。当然，一切还是要建立在基础之上。在你理解了树的数据结构和一些简单的遍历算法之后，再回来深入理解这些概念并记住它们。相信一般面试中树相关的话题不会有问题，一起努力吧！参考资料：《数据结构》第2版闫伟民《数据结构》第2版陈越《数据结构高分笔记》2020年版天琴考研============各媒体平台均可搜索【硬核项目经理】】
