⚡ 二叉树:Java算法体系的核心基石
在Java开发的进阶之路上,二叉树(Binary Tree)作为最基础却最具扩展性的非线性数据结构,不仅是算法面试中的高频考点,更是理解更复杂树形结构(如AVL树、红黑树、B+树)的理论根基。本文将从零基础出发,系统梳理Java中二叉树的定义、特性、遍历方式、典型操作、自平衡机制及实际应用场景,辅以大量可运行的代码示例与深度解析,助您构建完整的树形结构知识体系。
与线性结构(数组、链表)不同,二叉树具有天然的层次性与分支性,其每个节点最多拥有两个子节点(左子节点与右子节点),这种结构天然适配“分治思想”,在查找、排序、表达式求值、文件系统路径管理等场景中展现出卓越性能。尤其在JDK源码中,如TreeMap、TreeSet、ConcurrentSkipListMap等核心集合类,其底层实现均深度依赖二叉搜索树(BST)及其变种——自平衡二叉搜索树(如红黑树),因此深入掌握二叉树,是理解Java高级特性的必经之路。
值得注意的是,二叉树本身并非Java原生类库的一部分,开发者需通过自定义类(Node/TreeNode)或使用第三方库(如Apache Commons Collections、JGraphT)构建。本文将采用纯Java原生代码实现所有数据结构,确保逻辑清晰、易于迁移与调试。
⚙️ 二叉树基础:定义、类型与核心属性
1. 定义与基本构成
二叉树是n(n≥0)个节点的有限集合,该集合或为空树(n=0),或由一个根节点及两棵互不相交的、分别称为左子树与右子树的二叉树组成。其递归定义强调了“左/右子树”的独立性与有序性——即左子树与右子树不可交换,这是与普通树的本质区别。
Java中典型节点类定义如下:
class TreeNode {
int val; // 节点存储的值
TreeNode left; // 左子节点引用
TreeNode right; // 右子节点引用
TreeNode(int val) {
this.val = val;
this.left = null;
this.right = null;
}
}
2. 关键术语与图示说明
- 根节点(Root):无父节点的节点,一棵树仅有一个根节点
- 叶子节点(Leaf):无子节点的节点
- 内部节点:至少有一个子节点的节点
- 深度(Depth):从根节点到某节点的路径长度(边数)
- 高度(Height):从某节点到最深叶子节点的最长路径长度;整棵树高度 = 根节点高度
- 度:节点拥有的子节点数;二叉树中节点度 ≤ 2
3. 二叉树的五种基本形态
- 空树
- 仅含根节点
- 根节点 + 左子树
- 根节点 + 右子树
- 根节点 + 左子树 + 右子树
4. 特殊二叉树类型
⑴ 满二叉树(Full Binary Tree)
所有分支节点均存在左右子树,且所有叶子节点位于同一层。高度为h的满二叉树共有2h - 1个节点。其节点编号具有严格规律:第i层有2i-1个节点(i从1开始)。
⑵ 完全二叉树(Complete Binary Tree)
除最后一层外,其余层均被填满;最后一层节点从左到右连续填充。完全二叉树可用数组高效存储(索引i的左子为2i+1,右子为2i+2),堆结构即基于此。JDK中PriorityQueue底层即为最小堆的数组实现。
⑶ 二叉搜索树(Binary Search Tree, BST)
满足如下性质的二叉树:对任一节点,其左子树所有节点值 < 当前节点值 < 右子树所有节点值。BST支持O(log n)时间复杂度的查找、插入、删除操作(最坏退化为O(n))。TreeMap与TreeSet即基于红黑树(一种自平衡BST)实现。
⑷ 平衡二叉树(Balanced Binary Tree)
任意节点左右子树高度差不超过1。典型代表为AVL树与红黑树,二者通过旋转操作维持平衡,确保操作复杂度稳定在O(log n)。
⚡ 二叉树遍历:递归与迭代的完整实现
遍历是二叉树操作的基础,指按某种策略访问所有节点且不重复。Java中常见遍历方式包括前序、中序、后序、层序四种,每种又可分为递归与非递归(迭代)实现,后者常需借助栈或队列模拟系统调用栈。
1. 前序遍历(Preorder:根 → 左 → 右)
应用场景:复制二叉树、表达式树求值(前缀表达式)
// 递归实现
public static void preorderRecursive(TreeNode root) {
if (root == null) return;
System.out.print(root.val + " ");
preorderRecursive(root.left);
preorderRecursive(root.right);
}
// 迭代实现(用栈)
public static void preorderIterative(TreeNode root) {
if (root == null) return;
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()) {
TreeNode node = stack.pop();
System.out.print(node.val + " ");
if (node.right != null) stack.push(node.right); // 先压右,后压左
if (node.left != null) stack.push(node.left);
}
}
2. 中序遍历(Inorder:左 → 根 → 右)
对二叉搜索树(BST)进行中序遍历,结果必为递增序列。常用于验证BST合法性或获取有序数据。
// 递归实现
public static void inorderRecursive(TreeNode root) {
if (root == null) return;
inorderRecursive(root.left);
System.out.print(root.val + " ");
inorderRecursive(root.right);
}
// 迭代实现(用栈模拟递归)
public static void inorderIterative(TreeNode root) {
Stack<TreeNode> stack = new Stack<>();
TreeNode curr = root;
while (curr != null || !stack.isEmpty()) {
while (curr != null) { // 一直向左走到底
stack.push(curr);
curr = curr.left;
}
curr = stack.pop();
System.out.print(curr.val + " ");
curr = curr.right;
}
}
3. 后序遍历(Postorder:左 → 右 → 根)
应用场景:释放树内存(先释放子节点再释放父节点)、计算目录大小
// 递归实现
public static void postorderRecursive(TreeNode root) {
if (root == null) return;
postorderRecursive(root.left);
postorderRecursive(root.right);
System.out.print(root.val + " ");
}
// 迭代实现(双栈法)
public static void postorderIterative(TreeNode root) {
if (root == null) return;
Stack<TreeNode> s1 = new Stack<>(), s2 = new Stack<>();
s1.push(root);
while (!s1.isEmpty()) {
TreeNode node = s1.pop();
s2.push(node);
if (node.left != null) s1.push(node.left);
if (node.right != null) s1.push(node.right);
}
while (!s2.isEmpty()) {
System.out.print(s2.pop().val + " ");
}
}
4. 层序遍历(Level Order:逐层从左到右)
本质是广度优先搜索(BFS),使用队列实现。常用于求树的最大深度、按层打印节点。
public static List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> result = new ArrayList<>();
if (root == null) return result;
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
int size = queue.size();
List<Integer> level = new ArrayList<>();
for (int i = 0; i < size; i++) {
TreeNode node = queue.poll();
level.add(node.val);
if (node.left != null) queue.offer(node.left);
if (node.right != null) queue.offer(node.right);
}
result.add(level);
}
return result;
}
⚡ 二叉搜索树(BST):高效动态查找表
1. BST核心操作详解
在BST中,查找、插入、删除操作的时间复杂度均为O(h),其中h为树高。平均情况下h≈log n,最坏(退化为链表)为O(n)。以下为标准实现:
// 查找目标值
public static TreeNode searchBST(TreeNode root, int target) {
if (root == null || root.val == target) return root;
return target < root.val ? searchBST(root.left, target) : searchBST(root.right, target);
}
// 插入新值(保持BST性质)
public static TreeNode insertBST(TreeNode root, int val) {
if (root == null) return new TreeNode(val);
if (val < root.val) root.left = insertBST(root.left, val);
else if (val > root.val) root.right = insertBST(root.right, val);
return root;
}
// 删除值为key的节点
public static TreeNode deleteNode(TreeNode root, int key) {
if (root == null) return null;
if (key < root.val) root.left = deleteNode(root.left, key);
else if (key > root.val) root.right = deleteNode(root.right, key);
else { // 找到目标节点
if (root.left == null) return root.right;
if (root.right == null) return root.left;
// 两子树均存在:找右子树最小值(或左子树最大值)替换
TreeNode minRight = findMin(root.right);
root.val = minRight.val;
root.right = deleteNode(root.right, minRight.val);
}
return root;
}
private static TreeNode findMin(TreeNode node) {
while (node.left != null) node = node.left;
return node;
}
2. BST的局限性与自平衡必要性
若插入序列有序(如1→2→3→4→5),BST将退化为单链表,查找效率降至O(n)。例如:连续插入升序整数后,树结构如下:
1
\
2
\
3
\
4
\
5
此问题催生了自平衡二叉搜索树家族——通过旋转操作(左旋、右旋)动态维持平衡,确保任意节点左右子树高度差≤1(AVL)或高度比≤2(红黑树)。
⚙️ AVL树:严格的自平衡二叉搜索树
1. 平衡因子与旋转原理
AVL树要求每个节点的平衡因子(左子树高度 - 右子树高度)∈ {-1, 0, 1}。插入/删除后若失衡,需通过旋转调整:
- LL型(左子树过高):右旋
- RR型(右子树过高):左旋
- LR型(左子树的右子树过高):先左旋再右旋
- RL型(右子树的左子树过高):先右旋再左旋
2. AVL树核心操作(伪代码级说明)
// 右旋(LL型调整)
TreeNode rotateRight(TreeNode y) {
TreeNode x = y.left;
TreeNode T2 = x.right;
x.right = y;
y.left = T2;
// 更新高度
y.height = max(height(y.left), height(y.right)) + 1;
x.height = max(height(x.left), height(x.right)) + 1;
return x; // 新根节点
}
// 左旋(RR型调整)
TreeNode rotateLeft(TreeNode x) {
TreeNode y = x.right;
TreeNode T2 = y.left;
y.left = x;
x.right = T2;
x.height = max(height(x.left), height(x.right)) + 1;
y.height = max(height(y.left), height(y.right)) + 1;
return y;
}
3. AVL树 vs 红黑树:性能对比
| 特性 | AVL树 | 红黑树 |
|---|---|---|
| 平衡条件 | 高度差 ≤ 1 | 任意路径黑高相等;无双红节点 |
| 插入/删除调整 | 最多O(log n)次旋转 | 最多2次旋转 + O(log n)次变色 |
| 查找效率 | 更优(高度更低) | 略逊于AVL |
| 更新效率 | 较慢(旋转频繁) | 更快(调整开销小) |
| 典型应用 | 读多写少场景(如数据库索引) | Java集合(TreeMap/TreeSet)、Linux进程调度 |
⚡ 红黑树:Java集合框架的基石
1. 红黑树五条基本性质
- 节点非红即黑
- 根节点为黑
- 叶子节点(null)为黑
- 红节点的子节点必为黑
- 任一节点到其子孙叶子的简单路径上,黑节点数相同(黑高一致)
由性质4、5可推得:红黑树高度 ≤ 2log(n+1),确保O(log n)时间复杂度。
2. Java中TreeMap的红黑树实现要点
JDK 1.8中,TreeMap的Entry类定义如下:
static final class Entry<K,V> implements Map.Entry<K,V> {
K key;
V value;
Entry<K,V> left;
Entry<K,V> right;
Entry<K,V> parent;
boolean color = BLACK; // 默认黑色
}
插入/删除操作后通过fixAfterInsertion与fixAfterDeletion方法进行旋转与变色调整,核心策略包括:
- 插入调整:分6种情况(父为左/右子 + 父为红 + 叔为黑/红),优先变色,其次旋转
- 删除调整:分4种情况(兄弟节点存在性 + 兄弟子树颜色),通过移动黑高至根路径实现平衡
3. 红黑树 vs AVL树:实际选型建议
在读写均衡的通用场景下,红黑树因更新性能更优而被广泛采用。例如:
- Java:TreeMap、TreeSet(JDK 1.8+)
- C++ STL:std::map、std::set
- Linux:CFS调度器的task_struct管理
- 数据库:InnoDB索引(B+树更主流,但部分实现用红黑树)
而AVL树适用于读多写少场景,如:
- 数据库静态索引(如MyISAM)
- 编译器符号表(标识符不常变动)
⚡ 堆结构:优先队列的高效实现
1. 堆的定义与性质
堆是满足以下性质的完全二叉树:
- 最大堆(Max Heap):任一节点值 ≥ 子节点值;根节点为最大值
- 最小堆(Min Heap):任一节点值 ≤ 子节点值;根节点为最小值
堆通常用数组存储,索引i的父节点为(i-1)/2,左右子为2i+1与2i+2。
2. 堆操作实现(以最小堆为例)
class MinHeap {
private List<Integer> heap = new ArrayList<>();
// 插入:尾部添加 + 上浮
public void insert(int val) {
heap.add(val);
siftUp(heap.size() - 1);
}
// 弹出最小值:首元素替换为尾元素 + 下沉
public int poll() {
if (heap.isEmpty()) throw new IllegalStateException();
int min = heap.get(0);
heap.set(0, heap.remove(heap.size() - 1));
if (!heap.isEmpty()) siftDown(0);
return min;
}
private void siftUp(int i) {
while (i > 0 && heap.get(parent(i)) > heap.get(i)) {
swap(parent(i), i);
i = parent(i);
}
}
private void siftDown(int i) {
int minIndex = i;
int left = leftChild(i);
int right = rightChild(i);
if (left < heap.size() && heap.get(left) < heap.get(minIndex))
minIndex = left;
if (right < heap.size() && heap.get(right) < heap.get(minIndex))
minIndex = right;
if (i != minIndex) {
swap(i, minIndex);
siftDown(minIndex);
}
}
private int parent(int i) { return (i - 1) / 2; }
private int leftChild(int i) { return 2 * i + 1; }
private int rightChild(int i) { return 2 * i + 2; }
private void swap(int i, int j) {
Integer temp = heap.get(i);
heap.set(i, heap.get(j));
heap.set(j, temp);
}
}
3. 堆在Java中的典型应用
- PriorityQueue:非线程安全的优先队列,底层为最小堆
- Thread.sleep()与定时任务:DelayQueue使用PriorityQueue实现延迟元素排序
- Top K问题:维护大小为K的最小堆,遍历数组时堆顶即第K大元素
⚡ 二叉树算法实战:高频场景与典型题目
1. 二叉树最大深度
递归解法:maxDepth(root) = 1 + max(maxDepth(left), maxDepth(right))
public int maxDepth(TreeNode root) {
if (root == null) return 0;
return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}
2. 对称二叉树判断
递归比较左右子树是否镜像:左子树左孩子 = 右子树右孩子,左子树右孩子 = 右子树左孩子
public boolean isSymmetric(TreeNode root) {
return root == null || isMirror(root.left, root.right);
}
private boolean isMirror(TreeNode t1, TreeNode t2) {
if (t1 == null && t2 == null) return true;
if (t1 == null || t2 == null) return false;
return (t1.val == t2.val) && isMirror(t1.left, t2.right) && isMirror(t1.right, t2.left);
}
3. 二叉树路径总和
判断是否存在从根到叶子节点路径上节点值之和等于目标值targetSum
public boolean hasPathSum(TreeNode root, int targetSum) {
if (root == null) return false;
if (root.left == null && root.right == null) return root.val == targetSum;
return hasPathSum(root.left, targetSum - root.val) ||
hasPathSum(root.right, targetSum - root.val);
}
4. 重建二叉树(前序+中序)
前序遍历首元素为根节点,在中序遍历中定位根节点后,左侧为左子树,右侧为右子树,递归构建
public TreeNode buildTree(int[] preorder, int[] inorder) {
Map<Integer, Integer> inMap = new HashMap<>();
for (int i = 0; i < inorder.length; i++) inMap.put(inorder[i], i);
return build(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1, inMap);
}
private TreeNode build(int[] pre, int preL, int preR, int[] in, int inL, int inR, Map<Integer, Integer> inMap) {
if (preL > preR || inL > inR) return null;
TreeNode root = new TreeNode(pre[preL]);
int rootIdx = inMap.get(pre[preL]);
int leftSize = rootIdx - inL;
root.left = build(pre, preL + 1, preL + leftSize, in, inL, rootIdx - 1, inMap);
root.right = build(pre, preL + leftSize + 1, preR, in, rootIdx + 1, inR, inMap);
return root;
}