本博客将介绍二叉树的基本知识，包括二叉树的概念、特性、模拟实现。
一.二叉树概述
1.二叉树的定义
要明白二叉树是什么，就要明白树是什么。
树：一种非线性数据结构，由节点（Node）和边（Edge）构成。
节点好比一颗树的叶子，边好比一棵树的枝干。
关键概念：
子树（Subtree）：以某节点为根的树
兄弟节点（Siblings）：同一父节点的子节点
叶子结点或终端结点：度为0的结点称为叶结点
双亲结点或父结点：若一个结点含有子结点，则这个结点称为其子结点的父结点
根结点：一棵树中，没有双亲结点的结点
孩子结点或子结点：一个结点含有的子树的根结点称为该结点的子结点
度（Degree）：节点的子节点数量
树的度：一棵树中，所有结点度的最大值称为树的度
层级（Level）：根为第1层，子节点层级=父节点层级+1
高度（Height）：从某节点到最远叶子节点的边数（叶子节点高度=0）
深度（Depth）：从根到该节点的边数（根深度=0）
森林：由m（m>=0）棵互不相交的树组成的集合称为森林
树的特点：
有且仅有一个根节点（Root）（无父节点）
除根节点外，每个节点有且仅有一个父节点（Parent）
节点可以有0或多个子节点（Child）
没有子节点的节点称为叶子节点（Leaf）树
二叉树：
每个节点最多有两个子节点，称为左子节点和右子节点
子树有严格的左右之分（即使单子树也要明确左右）
如下就是一颗简单的二叉树：
2.二叉树的分类
（1）满二叉树（Full Binary Tree）
定义：所有层的节点都达到最大数量
特性：
第k层最多有2**(k-1)个节点
高度为h的满二叉树总节点数2**k-1
如下就是一个满二叉树 ：
（2）完全二叉树（Complete Binary Tree）
定义：除最后一层外全满，最后一层节点左对齐
特性：
适合用数组存储（父节点索引i，左子=2i+1，右子=2i+2）
堆结构的基础形态
如下就是一个完全二叉树：
3.二叉树的数学特性
非空二叉树第k层最大节点数：2*k−1
高度为h的二叉树最大节点数：2**h−1
具有n个节点的二叉树最小高度：h=⌈log2(n+1)⌉（向上取整）
设叶子节点数为n0，度为2的节点数为n2，则：n0=n2+1
4.二叉树的遍历
二叉树有4种主要遍历方式：前序遍历、中序遍历、后序遍历、层序遍历
前三种又称为深度优先遍历，层序遍历又称为广度优先遍历。
ps：遍历本质是递归遍历，结合之后的代码更好理解。
前序遍历(Preorder Traversal)——访问根结点--->根的左子树--->根的右子树
如下访问顺序为1->7
中序遍历(Inorder Traversal)——根的左子树--->根节点--->根的右子树。
后序遍历(Postorder Traversal)——根的左子树--->根的右子树--->根节点
层序遍历：
按层级从左到右访问节点
二.二叉树的模拟实现
二叉树有2种模拟实现方式，一种是链式结构的实现，一种是基于堆（稍后介绍）的实现。
1.基于链式结构的二叉树
由于树是靠边连在一起的，于是我们自然想到了链式结构，用索引套用把节点（Node）连接在一起：
（1）存储结构
public class MyBinaryTree {
// 节点定义
static class TreeNode {
int val;
TreeNode left;
TreeNode right;
public TreeNode(int val) {
this.val = val;
}
}
private TreeNode root; // 根节点（2）遍历
前序遍历(Preorder)
void preOrder(TreeNode root) {
if (root == null) return;
System.out.print(root.val + " "); // 访问根节点
preOrder(root.left); // 递归左子树
preOrder(root.right); // 递归右子树
}中序遍历(Inorder)
void inOrder(TreeNode root) {
if (root == null) return;
inOrder(root.left); // 递归左子树
System.out.print(root.val + " "); // 访问根节点
inOrder(root.right); // 递归右子树
}后序遍历(Postorder)
void postOrder(TreeNode root) {
if (root == null) return;
postOrder(root.left); // 递归左子树
postOrder(root.right); // 递归右子树
System.out.print(root.val + " "); // 访问根节点
}层序遍历
层序遍历稍微复杂点，他调用了一个队列来存储元素：
void levelOrder(TreeNode root) {
Queue<TreeNode> queue = new LinkedList<>();
if (root != null) queue.offer(root);
while (!queue.isEmpty()) {
TreeNode node = queue.poll();
System.out.print(node.val + " ");
if (node.left != null) queue.offer(node.left);
if (node.right != null) queue.offer(node.right);
}
}第一步，根节点入队（根节点非null时）
第二步，循环执行队首出队并打印输出，出队节点的子节点入队
这样就可以按层遍历节点了。
如下：
此时出队节点4无子节点，则不执行入队，其余节点同理出队，最后就可以得到层序遍历的结果：
基于以上遍历，我们可以写出：
（3）按层序的空位插入
public void insert(int val) {
TreeNode newNode = new TreeNode(val);
if (root == null) {
root = newNode;
return;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
TreeNode current = queue.poll();
if (current.left == null) {
current.left = newNode;
return;
} else {
queue.offer(current.left);
}
if (current.right == null) {
current.right = newNode;
return;
} else {
queue.offer(current.right);
}
}
}（4）查找节点
public boolean contains(int val) {
return containsRec(root, val);
}
private boolean containsRec(TreeNode node, int val) {
if (node == null) return false;
if (node.val == val) return true;
return containsRec(node.left, val) || containsRec(node.right, val);
}（5）删除节点
/**
* 删除节点（普通二叉树）
*/
public void delete(int val) {
root = deleteRec(root, val);
}
private TreeNode deleteRec(TreeNode node, int val) {
if (node == null) return null;
if (node.val == val) {
// Case 1: 叶子节点
if (node.left == null && node.right == null) {
return null;
}
// Case 2: 单子节点
if (node.left == null) {
return node.right;
}
if (node.right == null) {
return node.left;
}
// Case 3: 双子节点（找右子树最小值替换）
TreeNode minNode = findMin(node.right);
node.val = minNode.val;
node.right = deleteRec(node.right, minNode.val);
} else {
node.left = deleteRec(node.left, val);
node.right = deleteRec(node.right, val);
}
return node;
}
private TreeNode findMin(TreeNode node) {
while (node.left != null) {
node = node.left;
}
return node;
}（6）计算树高
public int height() {
return heightRec(root);
}
private int heightRec(TreeNode node) {
if (node == null) return 0;
return 1 + Math.max(heightRec(node.left), heightRec(node.right));
}2.基于顺序结构二叉树
基于顺序结构的二叉树，是利用树的数学特性：非空二叉树第k层最大节点数：2*k−1，由此我们就可以用索引划分树的层次：
等价于：
有如下定位规则：
- 如果i为0，则i表示的节点为根节点，否则i节点的双亲节点为 (i - 1)/2。
- 如果2 * i + 1 小于节点个数，则节点i的左孩子下标为2 * i + 1，否则没有左孩子。
- 如果2 * i + 2 小于节点个数，则节点i的右孩子下标为2 * i + 2，否则没有右孩子。
ps：注意：对于非完全二叉树，则不适合使用顺序方式进行存储，因为为了能够还原二叉树，空间中必须要存储空节点，就会导致空间利用率比较低。
基于顺序结构，我们又衍生出了有序的二叉树——堆。
大元素在上层的称为大堆，小元素在上层的称为小堆。
如上就是一个小堆。
由于堆的操作实际上就是优先级队列，请移步以下文章：