1、什么是树？
1.1 简单认识树
在生活中，有杨树，石榴树，枣树，而在计算机中的树呢，是一种非线性结构，是由 n(n>=0) 个有限节点组成一个具有层次关系的集合。当 n==0 也就是没有节点的树，我们称为空树！
这里我们要注意几点：
树的根节点为最顶层的节点，根节点没有前驱
除了根节点之外，其余节点被分为 M(M>0) 个不相交的集合，又是一棵树，我们把这种树称为子树，每棵子树的根节点有且只有一个前驱，可以有0个或者多个后继
树是递归定义的
这也不像一棵树啊，是的，但是他像一颗倒过来的树😏 。
注意：在树型结构中，子树之间不能相交，比如上图中如果 B 与 C 有相交关系了，也就是他俩连起来了，那么这就不能称之为树！
1.2 树的概念
还是拿这张图来说，我们来聊一聊树的概念。
节点的度：一个节点含有子树的个数，也就是他可以分出多少个子树，比如节点 A 的度为 3，节点 F 的度为1。
树的度：一棵树中，所有节点的度里面的最大值，就是这棵树的度，上图树的度为 3。
叶子节点或终端节点：度为0的节点为叶子节点，也就是说，该节点没有任何子树。上图 C E G H 就是叶子节点。
双亲节点或父节点：如果一个节点含有子节点，则这个节点称为其子节点的父节点，上图 B 是 F 的父节点，但是 B 不是 H 的父节点，H 并不是 B 的子节点，而是 F 的子节点，【B是F的父亲，F又是 H 的父亲，那么 B 不就是 H 的爷爷吗？(dog)。】
孩子节点或子节点：如果一个节点含有子树，那么这个子树的根节点就为该节点的子节点，上图 B 是 A 的子节点，但 E 并不是 A 的子节点。
根节点：一棵树中，没有父节点的树为根节点，上图 A 为根节点。
节点的层次：从根节点开始，根为第一层，根的子节点为第二层，以此类推，上图B是第二层，H是第四层。
树的高度：树中节点的最大层次，上图树的深度为 4。
下面的概念不是很重要，了解即可：
非终端节点或分支节点：度不为0的节点，也就是有孩子的节点，都为非终端节点，如上图A B D F。
兄弟节点：具有相同父节点的节点为兄弟节点，如上图 E 和 F 互为兄弟节点。
堂兄弟节点：父节点在同一层的节点互为堂兄弟，如上图 F 和 G 互为堂兄弟节点。
祖先节点：从根到该节点所经分支上的所有节点，都为该节点的祖先节点，如上图 A 是所有节点的祖先节点。
子孙：以某节点为根的子树中任意一个节点都称为该节点的子孙，如上图 F 是 A 的子孙节点，也是 B 的子孙节点。
森林：由m(m>=0) 颗互不相交的树组成的集合叫做森林，一棵树也可以叫做森林。
1.3 树的表示形式
树结构不同于我们前面学习的顺序结构，树型结构的表示方式就有很多了，比如：双亲表示法，孩子表示法，孩子双亲表示法，孩子兄弟表示法等等，最常用的还是孩子兄弟表示法。
孩子兄弟表示法：
2、二叉树
2.1 二叉树的概念
二叉树是一个有限的集合，该集合为空，或者是由一个根节点和两颗子树构成，分别为左子树和右子树，只含有一个根节点的也可也称为二叉树。
注意：
二叉树不存在度大于2的节点
二叉树的子树有左右之分
每个子树的根节点往下都可看作一个新的二叉树
空树和只有一个节点的树都可以称为二叉树
根节点只有左树（或右树）并满足节点度不大于2的情况下，也是二叉树
2.2 特殊的二叉树
这里有个问题，前面学习的 Stack 和 ArrayList 需要判断满的情况并扩容，那么二叉树可能出现满的情况吗？显然不会，因为二叉树是由节点构造而成的，但是如果每层的节点数都达到了最大值，那么这棵树就是满二叉树。换句话说，如果一颗二叉树的层数为k，且总结点的个数是2^k-1，那么就是满二叉树。满二叉树图例：
第二个概念：完全二叉树，篮球哥这里用简短的话来描述，每一层的节点都是从左往右的，依次排列，中间不能空， 完全二叉树是一种效率很高的数据结构，后续讲优先级队列会讲解到，理论看不明白没关系，我们直接看图：
2.3 二叉树的性质
性质1: 如果规定根节点的层数为1，那么一颗非空的二叉树的第 k 层上最多有 2^(k-1) 个节点 k>0。
性质2: 如果规定只有根节点的二叉树的深度为 1，则深度为 k 的二叉树的最大节点数是 2^k - 1（k >= 0）。
性质3: 对于任何一棵二叉树，如果叶子(度为0)节点的个数为 n0，度为2的非叶子节点的个数为 n2，则 n0 = n2 + 1。
性质4: 具有 n 个节点的完全二叉树的深度 k 为 log(n+1) 上取整。（以2为底）
性质5: 对于具有n个节点的完全二叉树，如果从上至下，从左至右的顺序对所有的节点从 0 开始进行编号，如果父节点下标为 i，左孩子节点下标为：2 * i + 1 且 < n，右孩子下标为：2 * i + 2 且 < n，已知孩子节点下标，求父节点：(i - 1) / 2 = 父节点下标，若 i = 0，则 i 为根节点编号。
2.4 二叉树性质相关习题
1. 某二叉树共有 399 个结点，其中有 199 个度为 2 的结点，则该二叉树中的叶子结点数为（ ）
A.不存在这样的二叉树 B.200 C.198 D.199
题解： 这道题我们可以运用上面的二叉树的性质3，任意一颗二叉树中，度为2比度为0的节点多一个，那题目告诉我们有 199 个度为 2 的节点，所以度为 0 的节点就是 199 + 1，本题选 A
2.在具有 2n 个结点的完全二叉树中，叶子结点个数为（ ）
A.n B.n+1 C.n-1 D.n/2
题解：因为二叉树不存在度大于 2 的节点，因此我们可知，度为0的节点 + 度为1的节点 + 度为2的节点 = 2n。 设度为 0 的节点为 n0，度为 1 的节点为 n1，度为 2 的节点为 n2，所以：n0 + n1 + n2 = 2n。得出了这个公式，后面就好办了，我们看图：
3.一个具有767个节点的完全二叉树，其叶子节点个数为（）
A.383 B.384 C.385 D.386
题解：这道题跟上一道题思路类似，同样可以设：度为 0 的节点为 n0，度为 1 的节点为 n1，度为 2 的节点为 n2， 那么是不是得出：767 = n0 + n1 + n2，后面岂不是好办了吗？直接看图：
4.一棵完全二叉树的节点数为531个，那么这棵树的高度为（ ）
A.11 B.10 C.8 D.12
这个题就比较简单了， 运用上面二叉树的性质2，即：531 = 2^k - 1，532 = 2^k
k等于多少？当k等于9时，2^9 = 512，即k=9当前完全二叉树最大节点数为512小于531，不满足题意，当k等于10时，2^10 = 1024，满足题意，所以本题选 B！
3、实现二叉树的基本操作
3.1 了解二叉树的存储结构
二叉树的存储结构分为顺序存储和链式存储，顺序存储后续讲解优先级队列会讲，链式存储跟前面的链表还是有一定区别的。
二叉树的链式存储也是由一个个节点构成的，通常采用二叉链和三叉链(平衡二叉树...)
这样我们就简单构造出如上图一样的一颗二叉树了，下面我们将学习二叉树的一些相关操作，测试样例都是在上图的基础上进行测试。
3.3 二叉树的前序遍历
前序遍历就是先访问根节点，在访问左子树，根的右子树，这里我们一定要弄清楚一个点，根的左子树和右子树也可以看成一棵二叉树，根的左子树的根节点的左右子树又是一棵二叉树。
// 前序遍历 -> 根 左子树 右子树
public void preOrder(TreeNode root) {
if (root == null) {
return;
}
// 碰到根节点就打印
System.out.print(root.val + " ");
// 遍历左子树
preOrder(root.left);
// 遍历右子树
preOrder(root.right);
}
初学者看不懂这个代码没关系，博主来画递归展开图来详细介绍。
由这个递归展开图相信也能看明白，碰到根节点就打印，然后就去遍历当前根的左子树，如果实在不理解，就把博主的代码粘贴下去画递归展开图，多画几遍，你就能慢慢理解递归了！
按照我们这棵树，此时的前序遍历就是：A B D E C F
