【Java 数据结构】树和二叉树
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 了解二叉树的存储结构
二叉树的存储结构分为顺序存储和链式存储，顺序存储后续讲解优先级队列会讲，链式存储跟前面的链表还是有一定区别的。
二叉树的链式存储也是由一个个节点构成的，通常采用二叉链和三叉链(平衡二叉树...)
// 孩子表示法public class TreeNode { private char val; //数据域 private TreeNode left; //左孩子的引用，以左孩子为根的整棵树 private TreeNode right; //右孩子的引用，以右孩子为根的整棵树} // 孩子双亲表示法public class TreeNode { private char val; //数据域 private TreeNode left; //左孩子的引用，以左孩子为根的整棵树 private TreeNode right; //右孩子的引用，以右孩子为根的整棵树 private TreeNode parent; //当前节点的根节点的引用}
3.2 简单构造一棵二叉树
由于目前的学习深度不够，为了降低成本，我们需要先学习简单的二叉树的操作， 熟练掌握这些操作之后，下期我们在讲解二叉树的练习题时会讲到如何构造一颗二叉树，比如将字符串转换成二叉树，而这里我们采用列举的方法来构造一颗二叉树。
如图：
public TreeNode creationTree() { // 这里我们用列举的方法创建一颗树 TreeNode A = new TreeNode('A'); TreeNode B = new TreeNode('B'); TreeNode C = new TreeNode('C'); TreeNode D = new TreeNode('D'); TreeNode E = new TreeNode('E'); TreeNode F = new TreeNode('F'); A.left = B; A.right = C; B.left = D; B.right = E; C.left = F; return A;}
这样我们就简单构造出如上图一样的一颗二叉树了，下面我们将学习二叉树的一些相关操作，测试样例都是在上图的基础上进行测试。
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
3.4 二叉树的中序，后序遍历
有了前序遍历的学习，其实中序后序遍历就很简单了，但是我们还是要了解他们的概念。
- 中序遍历：根的左子树 -> 根 -> 根的右子树
- 后序遍历：根的左子树 -> 根的右子树 -> 根
代码实现：
// 中序遍历 -> 左子树 根 右子树public void inOrder(TreeNode root) { if (root == null) { return; } // 遍历左子树 inOrder(root.left); // 打印根节点 System.out.print(root.val + " "); // 遍历右子树 inOrder(root.right);} // 后序遍历 -> 左子树 右子树 根public void postOrder(TreeNode root) { if (root == null) { return; } // 遍历左子树 postOrder(root.left); // 遍历右子树 postOrder(root.right); // 打印根节点 System.out.print(root.val + " ");}
至于递归展开图，博主就不画了，不理解的小伙伴可以自己去画一画，还是那句话，数据结构多画图！
3.5 获取二叉树节点的个数
这道题我们仍然可以采用前序遍历的思想，先看代码，在作解释：
// 获取二叉树中节点的个数public int size(TreeNode root) { // 采用前序遍历的方式来获取这个树的节点个数 if (root == null) { return 0; } return size(root.left) + size(root.right) + 1;}
如果以任意一颗树的根节点的角度看，我的左子树为null，我的右子树也为空，那么是不是意味着这颗子树走完了，也就是上述方法结束了，既然我方法结束了，我是不是要归回去，递归从哪来回哪去，那么是不是也要统计一下走完的这个根节点，也即加1，这个代码采用的是子问题思想，如果还不熟悉递归，一定要下去画递归展开图，就像博主画上面前序遍历那样。
3.6 获取二叉树叶子节点个数
// 获取叶子节点的个数public int getLeafNodeCount(TreeNode root) { if (root == null) { return 0; } // 叶子节点的左孩子和右孩子都为null if (root.left == null && root.right == null) { return 1; } return getLeafNodeCount(root.left) + getLeafNodeCount(root.right);}
在二叉树的性质，我们提到过，叶子节点的左子树为空，右子树也为空，如果采用子问题思路，可以写出如上的代码。 如果不理解这个递归，一定要画递归展开图哦，多画几次就理解了！
3.7 获取第k层的节点个数
这个方法其实很简单，前面我们会求节点个数，那么第 k 层的节点个数，是不是就是第 k-1 层的子节点个数呢？所以当我们递归到第 k 层的时候，我们就不用往后递归了。
// 获取第K层节点的个数public int getKLevelNodeCount(TreeNode root, int k) { // 第k层节点的个数，也就是第k-1层的子节点个数 if (root == null) { return 0; } if (k == 1) { return 1; } return getKLevelNodeCount(root.left, k - 1) + getKLevelNodeCount(root.right, k - 1);}
3.8 获取二叉树的高度
二叉树的高度，如果用子问题方法来解决的话，那是不是以任意一个根节点为树的高度都是左子树右子树的高度较大值+1 ？
// 获取二叉树的高度public int getHeight(TreeNode root) { // 求左子树的高度和右子树的高度，返回他们的较大值 if (root == null) { return 0; } int leftH = getHeight(root.left); int rightH = getHeight(root.right); return leftH > rightH ? leftH + 1 : rightH + 1;}
3.9 检测值为value的元素是否存在
这道题仍然可以采用遍历二叉树的思想，我们要注意的是，如果找到了这个节点，是不是就不用递归了？换句话说，如果我在任意一棵左子树中找到了val，我还需要去右子树找吗？肯定是不需要的，如果左子树右子树都找完了，还是找不到，就返回 null 了。
// 检测值为value的元素是否存在TreeNode find(TreeNode root, char val) { if (root == null) { return null; } if (root.val == val) { return root; } // 递归左子树和右子树 TreeNode l = find(root.left, val); if (l != null) { //如果我的左子树返回值不为null,表示在左子树找到了val值对应的节点 //直接返回该节点,不用再去递归右子树了！ return l; } TreeNode r = find(root.right, val); if (r != null) { //如果我的右子树返回值不为null,表示在右子树找到了val值对应的节点 return r; } return null;}
3.10 层序遍历
解决这个方法我们来换一种思路，采用非递归的方式，思路是这样的，定义一个队列，先把根节点入队，如果队列不为空，将队头的元素出队放入临时变量中，接着入队临时变量不为空的左右子节点，左右节点为 null 则不入队，上述循环，当队列为空，层序遍历结束。
//层序遍历public void levelOrder(TreeNode root) { Queue<TreeNode> queue = new LinkedList<>(); queue.offer(root); while (!queue.isEmpty()) { //出队头元素 TreeNode tmp = queue.poll(); System.out.print(tmp.val + " "); if (tmp.left != null) { queue.offer(tmp.left); } if (tmp.right != null) { queue.offer(tmp.right); } }}
3.11 判断一棵二叉树是否为完全二叉树
这个方法实现思路跟上述差不多，具体就是左右子树为null的时候也要入栈，当发现出队出到了null，如果是完全二叉树，队列的后续节点应该都为空，否则则不是完全二叉树！
// 判断一棵树是不是完全二叉树public boolean isCompleteTree(TreeNode root) { Queue<TreeNode> queue = new LinkedList<>(); queue.offer(root); while (!queue.isEmpty()) { TreeNode tmp = queue.poll(); if (tmp != null) { queue.offer(tmp.left); queue.offer(tmp.right); } else { // 走到这里表示碰到了null节点，因为是完全二叉树，而我们又是层序遍历 // 所以此时如果是完全二叉树的情况，队列剩下的元素都是null // 在遍历队列剩余的元素中，一旦发现不为有一个元素不为null，都不是完全二叉树 while (!queue.isEmpty()) { tmp = queue.poll(); if (tmp != null) { return false; } } } } return true;}
以上就是二叉树的一些基本操作了，有了二叉树的基础，我们后面学习优先级队列或者二叉搜索树会更轻松，初学者刚接触二叉树可能有点难，但不用担心，慢慢来就好，多画图。
