「二叉树 binary tree」是一种非线性数据结构，代表着祖先与后代之间的派生关系，体现着“一分为二”的分治逻辑。与链表类似，二叉树的基本单元是节点，每个节点包含：值、左子节点引用、右子节点引用。
/* 二叉树节点类 */
class TreeNode {
int val; // 节点值
TreeNode left; // 左子节点引用
TreeNode right; // 右子节点引用
TreeNode(int x) { val = x; }
}每个节点都有两个引用（指针），分别指向「左子节点 left-child node」和「右子节点 right-child node」，该节点被称为这两个子节点的「父节点 parent node」。当给定一个二叉树的节点时，我们将该节点的左子节点及其以下节点形成的树称为该节点的「左子树 left subtree」，同理可得「右子树 right subtree」。
在二叉树中，除叶节点外，其他所有节点都包含子节点和非空子树。如图 7-1 所示，如果将“节点 2”视为父节点，则其左子节点和右子节点分别是“节点 4”和“节点 5”，左子树是“节点 4 及其以下节点形成的树”，右子树是“节点 5 及其以下节点形成的树”。
二叉树常见术语
二叉树的常用术语如图 7-2 所示。
- 根节点 root node：位于二叉树顶层的节点，没有父节点。
- 叶节点 leaf node：没有子节点的节点，其两个指针均指向 None 。
- 边 edge：连接两个节点的线段，即节点引用（指针）。
- 节点所在的层 leve：从顶至底递增，根节点所在层为 1 。
- 节点的度 degree：节点的子节点的数量。在二叉树中，度的取值范围是 0、1、2 。
- 二叉树的高度 height：从根节点到最远叶节点所经过的边的数量。
- 节点的深度 depth：从根节点到该节点所经过的边的数量。
- 节点的高度 height：从距离该节点最远的叶节点到该节点所经过的边的数量。
📌请注意，我们通常将“高度”和“深度”定义为“走过边的数量”，但有些题目或教材可能会将其定义为“走过节点的数量”。在这种情况下，高度和深度都需要加 1 。
二叉树基本操作
初始化二叉树
与链表类似，首先初始化节点，然后构建引用（指针）。
// 初始化节点
TreeNode n1 = new TreeNode(1);
TreeNode n2 = new TreeNode(2);
TreeNode n3 = new TreeNode(3);
TreeNode n4 = new TreeNode(4);
TreeNode n5 = new TreeNode(5);
// 构建引用指向（即指针）
n1.left = n2;
n1.right = n3;
n2.left = n4;
n2.right = n5;插入与删除节点
与链表类似，在二叉树中插入与删除节点可以通过修改指针来实现。图 7-3 给出了一个示例。
TreeNode P = new TreeNode(0);
// 在 n1 -> n2 中间插入节点 P
n1.left = P;
P.left = n2;
// 删除节点 P
n1.left = n2;👉需要注意的是，插入节点可能会改变二叉树的原有逻辑结构，而删除节点通常意味着删除该节点及其所有子树。因此，在二叉树中，插入与删除操作通常是由一套操作配合完成的，以实现有实际意义的操作。
常见二叉树类型
完美二叉树
「完美二叉树 perfect binary tree」所有层的节点都被完全填满。在完美二叉树中，叶节点的度为 0 ，其余所有节点的度都为 2 ；若树高度为 ℎ ，则节点总数为 2ℎ+1−1 ，呈现标准的指数级关系，反映了自然界中常见的细胞分裂现象。
👉请注意，在中文社区中，完美二叉树常被称为「满二叉树」。
完全二叉树
如图 7-5 所示，「完全二叉树 complete binary tree」只有最底层的节点未被填满，且最底层节点尽量靠左填充。
完满二叉树
如图 7-6 所示，「完满二叉树 full binary tree」除了叶节点之外，其余所有节点都有两个子节点。
平衡二叉树
如图 7-7 所示，「平衡二叉树 balanced binary tree」中任意节点的左子树和右子树的高度之差的绝对值不超过 1 。
二叉树的退化
图 7-8 展示了二叉树的理想与退化状态。当二叉树的每层节点都被填满时，达到“完美二叉树”；而当所有节点都偏向一侧时，二叉树退化为“链表”。
- 完美二叉树是理想情况，可以充分发挥二叉树“分治”的优势。
- 链表则是另一个极端，各项操作都变为线性操作，时间复杂度退化至 O(n) 。
如表 7-1 所示，在最佳和最差结构下，二叉树的叶节点数量、节点总数、高度等达到极大或极小值。
二叉树的遍历
广度优先遍历 breadth-first traversal
/* 层序遍历 */
List<Integer> levelOrder(TreeNode root) {
// 初始化队列，加入根节点
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
// 初始化一个列表，用于保存遍历序列
List<Integer> list = new ArrayList<>();
while (!queue.isEmpty()) {
TreeNode node = queue.poll(); // 队列出队
list.add(node.val); // 保存节点值
if (node.left != null)
queue.offer(node.left); // 左子节点入队
if (node.right != null)
queue.offer(node.right); // 右子节点入队
}
return list;
}
深度优先遍历 depth-first traversal
相应地，前序、中序和后序遍历都属于「深度优先遍历 depth-first traversal」，它体现了一种“先走到尽头，再回溯继续”的遍历方式。
图 7-10 展示了对二叉树进行深度优先遍历的工作原理。深度优先遍历就像是绕着整个二叉树的外围“走”一圈，在每个节点都会遇到三个位置，分别对应前序遍历、中序遍历和后序遍历。
/* 前序遍历 */
void preOrder(TreeNode root) {
if (root == null)
return;
// 访问优先级：根节点 -> 左子树 -> 右子树
list.add(root.val);
preOrder(root.left);
preOrder(root.right);
}
/* 中序遍历 */
void inOrder(TreeNode root) {
if (root == null)
return;
// 访问优先级：左子树 -> 根节点 -> 右子树
inOrder(root.left);
list.add(root.val);
inOrder(root.right);
}
/* 后序遍历 */
void postOrder(TreeNode root) {
if (root == null)
return;
// 访问优先级：左子树 -> 右子树 -> 根节点
postOrder(root.left);
postOrder(root.right);
list.add(root.val);
}
使用数组表示
完全二叉树非常适合使用数组来表示。回顾完全二叉树的定义，None 只出现在最底层且靠右的位置，因此所有 None 一定出现在层序遍历序列的末尾，按层排列
代码
package f_树_tree.BT_二叉树;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
/**
* 二叉树
*
* @author zijian Wang
*/
public class TreeNode {
/**
* 树节点值
*/
int value;
/**
* 左节点
*/
TreeNode left;
/**
* 右节点
*/
TreeNode right;
public TreeNode(int value) {
this.value = value;
}
/**
* 获取二叉树的节点数
*
* @param treeNode
* @return
*/
public static int getNum(TreeNode treeNode) {
if (treeNode.left == null && treeNode.right == null) {
return 1;
}
int leftCount = getNum(treeNode.left);
int rightCount = getNum(treeNode.right);
return leftCount + rightCount + 1;
}
/**
* 广度优先遍历 breadth-first traversal BFS
*/
public static List<Integer> breadthFirstTraversal(TreeNode rootNode) {
/**
* 1
* / \
* 2 3
* / \ / \
* 4 5 6 7
*
* 思路：使用队列存储待遍历的子节点。
* eg:遍历1 时，将2 3 放入queue ，在遍历2 时，将2的子节点放入queue。
*/
Queue<TreeNode> queue = new LinkedList();
queue.add(rootNode);
List<Integer> list = new ArrayList<>();
while (!queue.isEmpty()) {
//每次出队, 知道队列为空
TreeNode treeNode = queue.poll();
list.add(treeNode.value);
if (treeNode.left != null) {
queue.add(treeNode.left);
}
if (treeNode.right != null) {
queue.add(treeNode.right);
}
}
return list;
}
/**
* 「深度优先遍历 depth-first traversal」 - 前序遍历
*
* @param rootNode
*/
public static void preOrder(TreeNode rootNode) {
/**
* 1
* / \
* 2 3
* / \ / \
* 4 5 6 7
*
* 思路：前序记录顺序： 中间节点->左节点->右节点
*/
if (rootNode != null) {
System.out.print("\t" + rootNode.value);
preOrder(rootNode.left);
preOrder(rootNode.right);
}
}
/**
* 「深度优先遍历 depth-first traversal」- 中序遍历
*
* @param rootNode
*/
public static void inOrder(TreeNode rootNode) {
/**
* 思路：前序记录顺序： 左节点->中间节点->右节点
*/
if (rootNode != null) {
inOrder(rootNode.left);
System.out.print("\t" + rootNode.value);
inOrder(rootNode.right);
}
}
/**
* 「深度优先遍历 depth-first traversal」- 后序遍历
*
* @param rootNode
*/
public static void postOrder(TreeNode rootNode) {
/**
* 思路：前序记录顺序： 右节点->中间节点->左节点
*/
if (rootNode != null) {
postOrder(rootNode.left);
postOrder(rootNode.right);
System.out.print("\t" + rootNode.value);
}
}
public static void main(String[] args) {
TreeNode n1 = new TreeNode(1);
TreeNode n2 = new TreeNode(2);
TreeNode n3 = new TreeNode(3);
TreeNode n4 = new TreeNode(4);
TreeNode n5 = new TreeNode(5);
TreeNode n6 = new TreeNode(6);
TreeNode n7 = new TreeNode(7);
// 构建引用指向（即指针）
n1.left = n2;
n1.right = n3;
n2.left = n4;
n2.right = n5;
n3.left = n6;
n3.right = n7;
/**
* 1
* / \
* 2 3
* / \ / \
*4 5 6 7
*/
System.out.println("二叉树节点数：" + getNum(n1));
//广度优先遍历 BFS
System.out.println("BFS:" + breadthFirstTraversal(n1));
//前序遍历
System.out.println("前序遍历");
preOrder(n1);
//中序遍历
System.out.println();
System.out.println("中序遍历");
inOrder(n1);
//后序遍历
System.out.println();
System.out.println("后序遍历");
postOrder(n1);
}
}