这个假期一晃就过去了。昨天就像放假的第一天，今天就开始上班了。既然开工了，那就忍着吧，继续努力吧。接下来，我们将镜头切到元记餐厅。小二：掌柜，最近大家都在忙着种树，说要保护环境。业主：树？我们店里有。几年前种下的藤蔓不是结果子了吗？你吃得最多。孩子：这个........你应该猜到我们今天要讲什么了。之前给大家介绍过链表、栈、哈希表等数据结构。今天，我们来看一个新的数据结构，树。PS：本文内容比较基础。对没有学过数据结构的同学会有帮助。如果已经学过，还可以复习一下，查漏补缺。本系列后续会持续更新。本文大纲注：可能有的同学不喜欢手机阅读，所以我把这篇文章同步到我的仓库了。可以去Github阅读。点击文章底部阅读原文。我们先看看百度百科。树的定义树是n(n>=0)个节点的有限集。当n=0时，我们称它为空树，空树是树的特例。在任何非空树中：存在且只有一个特定节点称为根节点当n>1时，其余节点可分为m(m>0)个不相交的有限集T1，T2，.....Tm，每一个本身就是一棵树，被称为根的子树。我们把上面两句话一起拆解一下。什么是子树？请参见下图中的树。比如上图中，只有一个特定的节点叫做根节点，也就是上图中橙色的节点。.当节点数大于1时，除根节点外的节点可分为m个不相交的有限集T1，T2.....Tm。比如上图中，我们将除根节点以外的节点分成两个有限集T1(2,3,4,5,6,7)和T2(8,9)。那么T1（绿色节点）和T2（蓝色节点）是根节点（橙色节点）的子树。我们拆解后发现，上图中的例子符合树的要求。不知道大家有没有注意到这个地方。根节点以外的节点可以分成m个不相交的有限集。那么这种相互脱节意味着什么呢？见下图。我们将(A),(B),(C),(D)代入上述定义，发现(A),(B)符合树的定义，而(C)和(D)不符合，因为(C),(D)它们都有相交的子树。好了，到这里我们就知道如何识别树了，下面我们通过下面两张图来深入了解一下这棵树。主要从节点类型和节点之间的关系入手。这里节点的高度和深度可能比较好记，我们可以代入实际。当我们求一个物体的深度时，我们从上到下测量它，当我们求它的高度时，我们从下到上测量它。节点的高度和深度也是如此。二叉树我们刷题遇到的就是二叉树。让我们看一下二叉树。二叉树的前提是一棵树，即需要满足我们对树的定义，同时还需要满足如下要求。每个节点最多有两个子节点。,分别是左子节点和右子节点。注意这里我们说的是最多，所以二叉树并不一定要求每个节点都有两个子节点，有的节点可以只有一个左子节点，有的节点只有一个右子节点。下面总结一下二叉树的特点。每个节点至多有两个子树，也就是说二叉树中没有度数大于2的节点，节点的度数可以是0、1、2。左子树和右子树是有序的，有左右之分。如果只有一棵子树，还需要区分是左子树还是右子树。我们已经了解了二叉树的特点，那么我们来分析一下下图中的树是否满足二叉树的定义。有几种类型的二叉树。上图显示了5种不同的二叉树。在二叉树的定义中提到二叉树的左子树和右子树是有序的，所以B和C是两棵不同的二叉树，所以上图展示了5棵不同的二叉树。SpecialBinaryTrees下面说说一些特殊的二叉树，可以帮助我们在写题的时候考虑到特殊情况。FullbinarytreeFullbinarytree：在一棵二叉树中，所有分支节点都有左子树和右子树，并且所有叶子都在同一层。我们称这种树为满二叉树。看下图，我们发现只有(B)符合满二叉树的定义，我们发现满二叉树也是一种完全二叉树。完全二叉树完全二叉树：叶子节点只能出现在底层和第二底层，底层叶子节点集中在树的左边部分。哦！我们可以这样理解，除了最后一层，其他层的节点数都是满的，最后一层的叶子节点一定在左边。让我们来看看这些例子。上面的例子中，(A)(B)是完全二叉树，(C)(D)不是完全二叉树。这很容易理解。倾斜二叉树也是倾斜的。二叉树中，所有节点只有左子树的称为左斜树，所有节点只有右子树的二叉树称为右斜树。不是，下面两个是。另外，二叉树还有一些性质，比如第i层最多有多少个节点？通过叶子节点求度数为2的节点，通过节点树求二叉树的深度等等，这些都是考研经常考的知识，这里就不赘述了.需要的同学可以看看望道或者天琴的数据结构，上面的描述很具体，附上证明过程。好了，二叉树我们已经了解了，那么二叉树怎么存储呢？如何存储二叉树？二叉链存储法下面我们回顾一下如何使用数组来存储一棵完整的二叉树。我们先看根节点，也就是值为1的节点，它在数组中的下标为1，它的左子节点，也就是值为4的节点，索引为2，而右子节点是一个值为2的节点，它的索引为3，我们发现关系了吗？数组中，如果一个节点（非叶子节点）的下标是i，那么它的左孩子节点的下标就是2*i（这里左孩子可以直接相乘，这就是为什么空出来的第一个位置，如果从0开始存，需要2i+1)，右子节点为2i+1，其父节点为i/2。由于我们可以根据索引找到一个节点的左子节点和右子节点，所以我们使用数组存储是没有问题的。但是，让我们再次考虑这种情况。如果我们使用数组来存储倾斜的树会发生什么？如果我们通过2*i来存储左子节点，如果遇到倾斜的树，会浪费大量的存储空间，这样显然是不合适的，所以在存储一棵完整的二叉树时，我们使用数组来存储，这无疑是最节省内存的，但它不适合存储倾斜的树。那么我们再介绍另一种存储结构，链式存储结构。因为二叉树的每个节点至多有两个孩子，所以我们只需要为每个节点定义一个数据字段，这两个指针字段就可以val作为节点的值，left指向左子节点，right指向到右子节点。接下来，我们用链式存储结构存储树1、2、3、4、5、6、7，就是下面这种情况。二叉链表节点结构定义代码left=left;this.right=right;}}另外，我们在刷题的时候，可以自己实现数据结构，加深理解，提高基本功，面试越来越多。好了，下面说说树的遍历。下面我将以动图的形式进行描述。这很容易理解。我也会为大家总结相应的题目。欢迎您阅读。遍历二叉树二叉树的遍历是指从根节点开始，按照一定的顺序依次访问二叉树的所有节点，这样每个节点都被访问过一次。下面我们将介绍二叉树的几种遍历方法及其对应的话题，前序遍历、中序遍历、后序遍历、层序遍历。前中序遍历前序遍历的顺序是，对于树中的一个节点，先遍历该节点，然后遍历它的左子树，最后遍历它的右子树。光看文字有点生硬，直接看动画吧。前序遍历考题：leetcode144二叉树的前序遍历代码实现（递归版）;}publicvoidpreorder(TreeNoderoot,List
