二叉树
二叉树的结构
二叉树的类型：
1.空树
2.单节点
3.左单只
4.右单只
5.满二叉树 ：
特征：
满二叉树节点共 2n-1个节点，第n层共2n-1个节点，假设共有k个节点，那么一共有n = log2(k + 1)层
6.完全二叉树
特征：
叶子节点只可能在最后两层出现，从左到右不能有空（如上图）
满二叉树是特殊的完全二叉树
设n0为叶子节点，n1为度为1的节点，n2为度为2的节点，n为总节点
所以n = n0 + n1 + n2 所以共有 1n1 + 22条边
因为n个节点具有n - 1条边 ，所以 n - 1 = n1 + 2n2
所以n0 + n1 + n2 = n1 + 2n2 + 1
得n0 = n2 + 1
==例题：在具有2n个节点的完全二叉树中，叶子节点个数为（ ）==
当树具有偶数个节点的时候 n = n0 + n1 + n2 n1 = 1
因为第一层到k - 1层的节点个数为：2k-1-1为奇数个
如果整棵树具有偶数节点，那么最后一层一定具有奇数个节点
也就是必出现度为1的节点。如下图
如果总节点数为奇数，第k层就是偶数个节点，就不会出现度为1的节点（只有n1,n2），如下图
==回到例题==，本题共有2n个节点，也就是偶数个节点，那么必有一个n1节点
所以2n = n0 + n1 + n2 = n0 + 1 + n0 - 1 得 n0 = n
所以共有n个叶节点，1个度为1的节点，n - 1个度为2的节点
对于具有n个节点的完全二叉树，如果按照从上至下从左到右的顺序对所有节点从0开始编号，则对于序号为i的节点有：
- 若i > 0，双亲序号：(i - 1) / 2；i = 0，i为根节点编号，无双亲节点
- 若2i + 1 < n，左孩子序号：2i + 1，否则五孩子
- 若2i + 2 < n，右孩子序号：2i + 2，否则无右孩子
二叉树的创建
图
图-1
代码
public class BinaryTree {
static class TreeNode {
//创建元素
public char element;
//左节点
TreeNode left;
//右节点
TreeNode right;
//构造方法
public TreeNode(char element) {
this.element = element;
}
}
//创建根节点
public TreeNode root;
//创建一颗二叉树（非递归）
public void createBinaryTree() {
root = 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');
TreeNode G = new TreeNode('G');
root.left = B;
root.right = C;
B.left = D;
B.right = E;
D.left = F;
C.left = G;
}
}
前序递归遍历
思路
前序遍历是中，左，右。
递归最主要的就是判断条件，因为递归的原理就是将一个大问题简化为很多个子问题，而且无论是大问题还是子问题，他们执行的条件必须相同。
所以我们前序递归遍历就是将一个大的二叉树，分为很多小的二叉树。只要是判断条件对了，下面就只管递归就行了。
先看简化后树的执行条件：
1、如果根节点为空
此时直接中止程序就行，没有需要打印的值
2、如果根节点不为空
根节点不为空，此处先打印A（中节点），然后打印左节点B（往左子树走），再打印右节点C（往右节点走）。
所以我们代码的逻辑就是，先判断是不是空，是空返回，不是空打印，然后往左走，左走完再往右走。那通过简化后树的逻辑适不适合复杂的二叉树呢？
这里A是中节点，先打印自身，然后开始遍历左树，到了B节点，他自身也是一颗二叉树（红框），所以也要先打印自身，再往B的左节点走。D也是一颗二叉树，先打印自身，再往左节点F走，F的左右节点为空。返回到D的右节点，D的右节点为空，返回到B的右节点，打印E。E的左右节点为空，此时B这颗树已经走完了，所以A的左子树走完，走右子树。到了C，打印自身，再往G走，打印自身，左右节点为空，返回到C的右节点，为空。执行完毕。
代码
public void preOrder(TreeNode root) {
//判断是否为空
if (root == null) {
return;
}
//打印改节点的值
System.out.println(root.element);
//左子树
preOrder(root.left);
//右子树
preOrder(root.right);
}
带图分析代码（套递归）
为了方便大家理解，初学递归可以带着代码进行套递归操作，❗但是在做题的时候不建议现场套递归❗，因为这样你的大脑会乱（套不了几层就乱了），更建议看子问题的返回值，通过返回值写递归比直接套递归更清晰。那么本题没有返回值，void。所以只是一个判断条件在控制整个递归，如果符合就继续，不符合就退出。后面会有带有返回值的例题，到时候我们再细嗦~~
画图板是Pixso
有树有解析版：
纯代码版：
中序递归遍历
思路
中序递归节点顺序是左中右，那么和前序遍历的判断条件是一样的，只是打印操作和寻找节点的操作调换一下顺序。前序遍历是如果根节点不为空，就打印，并往左子树走，走完左再走右。而中序遍历是先走左，如果左不为空就一直往左走，一直走到黑（节点为空），如果为空，返回并打印返回后所在节点。然后再打印中，在打印右。
代码
public void inorder(TreeNode root) {
if(root == null) {
return;
}
inorder(root.left);
System.out.println(root.element);
inorder(root.right);
}
后序递归遍历
思想
打印顺序：左右中，若树为空返回，先遍历左树（一股劲走到黑），到头之后打印，然后再打印右树，最后再打印根。
代码
public void postorder(TreeNode root) {
if (root == null) {
return;
}
postorder(root.left);
postorder(root.right);
System.out.println(root.element);
}
