一、树
树的概念
🍑这是现实世界的树
🍑而我们这里所说的树，其实是一直特殊的数据结构
之前我们学习的不管是顺序表还是链表、队列、栈，都是一对一的线性结构。但在数据生活中还有很多一对多的情况，所有我们就要用到这种一对多的数据结构——树
📝树(Tree)是n（n≥0）个结点的有限集。n=0时称为空树。 在任意一颗非空树中：
（1）有且仅有一个特定的称为根（root）的结点
（2）当n＞1时，其余结点可分为m（m＞0）个互不相交的有限集 T 1 , T 2 , . . . , T m ， 其中每一个集合本身又是一棵树，并且称为根的子树(SubTree)
有两个点需要注意一下：
- 1.树是递归定义的——也就是说树的定义之中还用到了树的定义
- 2.树形结构中，子树之间不能有交集，否则就不是树形结构
下面来解释一下这两点：
🌰比如这是一个树
下图的子树T1和T2就是根结点A的子树。当然，D,G,H,I组成的树又是B为结点的子树，E、J组成的树是C为结点的树的子树。
🌰一些非树的例子
上面三个就不是树结构，只有右下角的那个称为树型结构
树的结点分类
📝树的结点包含一个数据元素及若干指向其子树的分支。结点拥有的子树数称为结点的度（Degree） 。
📝度为0的结点称为叶结点(Leaf)或终端结点；度不为0的结点称为非终端结点或分支结点。除根结点之外，分支结点也称为内部结点。树的度是树内各结点的度的最大值。
🌰如下图，因为这棵树结点的度的最大值是结点D的度，为3，所以树的度为3.
结点之间的关系
- 1.双亲节点或父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点
- 2.孩子结点或子结点：一个结点含有的子树的根结点称为该结点的子结点
- 3.兄弟节点：具有相同父节点的节点互称为兄弟节点
节点的祖先：从根到该节点所经分支上的所有节点，如上图对于结点H来说，D、B、A都是他的祖先
子孙：以某节点为根的子树中任一节点都称为该节点的子孙。如上图：B的子孙有D、G、H、I
树的存储结构
📝树结构相对线性表就比较复杂了，要存储表示起来就比较麻烦了，实际中树有很多种表示方式，如：双亲表示法，孩子表示法、孩子双亲表示法、孩子兄弟表示法等等。我们这里就简单的了解其中最常用的孩子兄弟表示法。（关于其他几种表示法，大话数据结构这本书里有详细的介绍）
我们观察后发现，任意一棵树，它的结点的第一个孩子如果存在就是唯一的。因此，我们设置两个结点引用，分别指向该结点的第一个孩子和该结点的右兄弟。
结点结构如表所示：
class TreeNode {
int date; // 数据域
TreeNode firstchild; // 该结点的第一个孩子
TreeNode rightbrother; // 该结点的右兄弟
}
那么下面的树：
就可以表示成：
这种表示其实就是把一棵复杂的树变成了一棵二叉树
至于二叉树是什么？这也是咱们接下来要重点聊的内容😁
其他相关概念
📝结点的层次：从一棵树的树根开始，树根所在层为第一层，根的孩子结点所在的层为第二层，依次类推
📝树的高度或深度：树中节点的最大层次
📝堂兄弟节点：双亲在同一层的节点互为堂兄弟
🌻森林：由m（m>0）棵互不相交的树的集合称为森林；
🌻有序树和无序树：如果树中结点的子树从左到右看，谁在左边，谁在右边，是有规定的，这棵树称为有序树；反之称为无序树。
在有序树中，一个结点最左边的子树称为"第一个孩子"，最右边的称为"最后一个孩子"。
二、 二叉树
二叉树的概念
🌻简单地理解，满足以下两个条件的树就是二叉树：
- 1.本身是有序树；
- 2.树中包含的各个节点的度不能超过 2，即只能是 0、1 或者 2；
🌰例如，图 1a) 就是一棵二叉树，而图 1b) 则不是。
再深入的理解就是：
📝 一棵二叉树是结点的一个有限集合，该集合：
1. 或者为空
2. 或者是由一个根节点加上两棵别称为左子树和右子树的二叉树组成
🍑 从上图可以看出：
1. 二叉树不存在度大于2的结点
2. 二叉树的子树有左右之分，次序不能颠倒，因此二叉树是有序树注意：对于任意的二叉树都是由以下几种情况复合而成的：
🍑 自然界的二叉树：
🍑我们数据结构要研究的二叉树：
📝特殊的二叉树
🍑如果二叉树中除了叶子结点，每个结点的度都为 2，则此二叉树称为满二叉树
🍑如果二叉树中除去最后一层节点为满二叉树，且最后一层的结点依次从左到右分布，则此二叉树被称为完全二叉树
如图 3a) 所示是一棵完全二叉树，图 3b) 由于最后一层的节点没有按照从左向右分布，因此只能算作是普通的二叉树。
其实完全二叉树类似这下面这种情况
从中我们也可以发现一些规律，如果一个完全二叉树的某一个结点没有右子树，那么该结点一定没有左子树，有右子树就一定得有左子树。它从左到右一定是连续的，中间不能出现空的。
🔔同时我们需要注意一个慢二叉树一定是一棵完全二叉树，但完全二叉树不一定是满二叉树。
从中我们也可以发现一些规律，如果一个完全二叉树的某一个结点没有右子树，那么该结点一定没有左子树，有右子树就一定得有左子树。它从左到右一定是连续的，中间不能出现空的。
🔔同时我们需要注意一个慢二叉树一定是一棵完全二叉树，但完全二叉树不一定是满二叉树。
我们来观察下面的图形
经过归纳分析，我们很容易得出这个结论
性质2：若规定根节点的层数为1，则深度为k的二叉树的最大结点数是2^k - 1 .（深度为k意思就是有k层的二叉树）
我们前面已经知道，一棵非空二叉树的第i层上2^(i-1) 个结点，那么k层的二叉树的结点树不就是首项是1、公比是2的等比数列求和吗？
性质3：对任何一棵非空二叉树, 如果度为0其叶结点个数为n0 , 度为2的分支结点个数为n2 ,则有n0 ＝n2 ＋1
📝对于二叉树来说，我们会发现（除了根节点）对于每一个结点来说，都有其对应父结点分支指向它，假设树中分枝数为 B，那么总的结点数就是B+1
设总结点数为n，度为0的结点（即叶子结点）个数为n0、度为1的结点个数为n1、度为2的结点个数为n2，那么就有n = n0 + n1 + n2
同时分支数B = n1 + 2 * n2，B + 1 == n
所以就有n0 = n2 + 1
下面我们就用这个性质来做几道题目练练手
🌰第一题
该二叉树的结点数是奇数，而对于结点数是奇数的二叉树，像这样：
你会发现，该二叉树中度为1的结点数一个都没有，这不是偶然，你观察其他的的二叉树，会发现也有这样一个规律。
而对于结点数是偶数的二叉树呢？
你会发现结点数为偶数的二叉树，有且仅有一个度为1的结点
那么这样我们就可以开始算了： 设叶子结点即——度为0的结点数为n0，度为1的结点数为n1（n1 == 0)，度为2的结点数为n2（n2 = n0 -1)
即399 = n0 + n1 + n2 = 2* n0 - 1 --->n0 = 200
🌰第二题
2n说明结点数是偶数个，度为1的结点个数为1，2n = n0 + n1 + n2 = 1 + n0 + (n0 - 1)
即n0 == n，叶子结点个数为n
🌰第三题
答案是：B
🌰第四题
对于这个题目就要用到我们的性质四了
性质四：具有n个结点的完全二叉树的深度k为 log2(n+1)上取整
2^9 == 512，即log2(531 + 1) == 9.xx，向上取整即为10，所以答案就是B
性质五：对于具有n个结点的完全二叉树，如果按照从上至下从左至右的数组顺序对所有节点从0开始编号，则对于序号为i的结点有：
1. 若i>0，i位置节点的双亲序号：(i-1)/2；i=0，i为根节点编号，无双亲节点
2. 若2i+1<n，左孩子序号：2i+1，2i+1>=n否则无左孩子
3. 若2i+2<n，右孩子序号：2i+2，2i+2>=n否则无右孩子
