树的常见算法及Java实现

一、常见树的类型及应用        

• 需要快速查找、插入、删除（通用）：首选红黑树，它在实践中综合性能最好。

• 海量数据，涉及磁盘存储（如数据库）：选择B+树，它最大限度地减少了磁盘访问次数。

• 处理字符串和前缀相关的问题：选择字典树 (Trie)。

• 需要管理优先级的任务调度：选择堆来实现优先队列。

• 频繁进行区间统计和更新：选择线段树。

• 目标是为了数据压缩：使用哈夫曼树构建编码。

二、树的遍历算法与构建

二叉树的基本节点结构：

class TreeNode {int val;TreeNode left;TreeNode right;TreeNode(int val) {this.val = val;this.left = null;this.right = null;}
}

2.1 树的深度优先遍历（DFS）

2.1.1 前序遍历 (根-左-右)

// 递归实现
public void preorderTraversal(TreeNode root) {if (root == null) return;System.out.print(root.val + " ");preorderTraversal(root.left);preorderTraversal(root.right);
}// 迭代实现
public void preorderTraversalIterative(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.1.2 中序遍历 (左-根-右)

// 递归实现
public void inorderTraversal(TreeNode root) {if (root == null) return;inorderTraversal(root.left);System.out.print(root.val + " ");inorderTraversal(root.right);
}// 迭代实现
public void inorderTraversalIterative(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;}
}

2.1.3 后序遍历 (左-右-根)

// 递归实现
public void postorderTraversal(TreeNode root) {if (root == null) return;postorderTraversal(root.left);postorderTraversal(root.right);System.out.print(root.val + " ");
}// 迭代实现
public void postorderTraversalIterative(TreeNode root) {if (root == null) return;Stack<TreeNode> stack = new Stack<>();Stack<TreeNode> output = new Stack<>();stack.push(root);while (!stack.isEmpty()) {TreeNode node = stack.pop();output.push(node);if (node.left != null) stack.push(node.left);if (node.right != null) stack.push(node.right);}while (!output.isEmpty()) {System.out.print(output.pop().val + " ");}
}

2.2 广度优先遍历 (BFS/层次遍历)

public void levelOrderTraversal(TreeNode root) {if (root == null) return;Queue<TreeNode> queue = new LinkedList<>();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);}
}

2.3 树的构建

2.3.1 从前序和中序遍历构建二叉树

public class PreInOrderBuilder {private Map<Integer, Integer> inOrderMap;private int preIndex;public TreeNode buildTree(int[] preorder, int[] inorder) {if (preorder == null || inorder == null || preorder.length != inorder.length) {return null;}// 创建中序遍历值到索引的映射inOrderMap = new HashMap<>();for (int i = 0; i < inorder.length; i++) {inOrderMap.put(inorder[i], i);}preIndex = 0;return buildTreeHelper(preorder, 0, inorder.length - 1);}private TreeNode buildTreeHelper(int[] preorder, int inStart, int inEnd) {if (inStart > inEnd) {return null;}// 前序遍历的第一个元素是根节点int rootVal = preorder[preIndex++];TreeNode root = new TreeNode(rootVal);// 在中序遍历中找到根节点的位置int inIndex = inOrderMap.get(rootVal);// 递归构建左子树和右子树root.left = buildTreeHelper(preorder, inStart, inIndex - 1);root.right = buildTreeHelper(preorder, inIndex + 1, inEnd);return root;}
}

2.3.2 从中序和后序遍历构建二叉树

public class InPostOrderBuilder {private Map<Integer, Integer> inOrderMap;private int postIndex;public TreeNode buildTree(int[] inorder, int[] postorder) {if (inorder == null || postorder == null || inorder.length != postorder.length) {return null;}// 创建中序遍历值到索引的映射inOrderMap = new HashMap<>();for (int i = 0; i < inorder.length; i++) {inOrderMap.put(inorder[i], i);}postIndex = postorder.length - 1;return buildTreeHelper(postorder, 0, inorder.length - 1);}private TreeNode buildTreeHelper(int[] postorder, int inStart, int inEnd) {if (inStart > inEnd) {return null;}// 后序遍历的最后一个元素是根节点int rootVal = postorder[postIndex--];TreeNode root = new TreeNode(rootVal);// 在中序遍历中找到根节点的位置int inIndex = inOrderMap.get(rootVal);// 注意：需要先构建右子树，再构建左子树root.right = buildTreeHelper(postorder, inIndex + 1, inEnd);root.left = buildTreeHelper(postorder, inStart, inIndex - 1);return root;}
}

2.3.3 从前序和后序遍历构建二叉树（不唯一，需附加条件）

public class PrePostOrderBuilder {private Map<Integer, Integer> postOrderMap;private int preIndex;// 注意：前序+后序不能唯一确定二叉树，需要附加条件// 这里假设树是真二叉树（每个节点有0或2个子节点）public TreeNode buildTree(int[] preorder, int[] postorder) {if (preorder == null || postorder == null || preorder.length != postorder.length) {return null;}// 创建后序遍历值到索引的映射postOrderMap = new HashMap<>();for (int i = 0; i < postorder.length; i++) {postOrderMap.put(postorder[i], i);}preIndex = 0;return buildTreeHelper(preorder, 0, postorder.length - 1);}private TreeNode buildTreeHelper(int[] preorder, int postStart, int postEnd) {if (postStart > postEnd) {return null;}if (preIndex >= preorder.length) {return null;}// 前序遍历的第一个元素是根节点int rootVal = preorder[preIndex++];TreeNode root = new TreeNode(rootVal);if (postStart == postEnd) {return root;}// 找到左子树的根节点在后序遍历中的位置int leftRootVal = preorder[preIndex];int leftRootIndex = postOrderMap.get(leftRootVal);// 递归构建左子树和右子树if (leftRootIndex <= postEnd - 1) {root.left = buildTreeHelper(preorder, postStart, leftRootIndex);root.right = buildTreeHelper(preorder, leftRootIndex + 1, postEnd - 1);}return root;}
}

2.3.4 从层次和中序遍历构建二叉树

public class LevelInOrderBuilder {private Map<Integer, Integer> inOrderMap;public TreeNode buildTree(int[] levelOrder, int[] inOrder) {if (levelOrder == null || inOrder == null || levelOrder.length != inOrder.length) {return null;}// 创建中序遍历值到索引的映射inOrderMap = new HashMap<>();for (int i = 0; i < inOrder.length; i++) {inOrderMap.put(inOrder[i], i);}return buildTreeHelper(levelOrder, 0, inOrder.length - 1);}private TreeNode buildTreeHelper(int[] levelOrder, int inStart, int inEnd) {if (inStart > inEnd) {return null;}if (levelOrder.length == 0) {return null;}// 找到当前层次遍历中第一个出现在中序遍历区间[inStart, inEnd]中的元素TreeNode root = null;int rootIndexInLevel = -1;for (int i = 0; i < levelOrder.length; i++) {int val = levelOrder[i];if (inOrderMap.get(val) >= inStart && inOrderMap.get(val) <= inEnd) {root = new TreeNode(val);rootIndexInLevel = i;break;}}if (root == null) {return null;}int rootIndexInInorder = inOrderMap.get(root.val);// 提取左子树和右子树的层次遍历序列int[] leftLevel = extractLevelOrder(levelOrder, rootIndexInLevel, inStart, rootIndexInInorder - 1);int[] rightLevel = extractLevelOrder(levelOrder, rootIndexInLevel, rootIndexInInorder + 1, inEnd);// 递归构建左子树和右子树root.left = buildTreeHelper(leftLevel, inStart, rootIndexInInorder - 1);root.right = buildTreeHelper(rightLevel, rootIndexInInorder + 1, inEnd);return root;}private int[] extractLevelOrder(int[] levelOrder, int rootIndex, int inStart, int inEnd) {if (inStart > inEnd) {return new int[0];}List<Integer> result = new ArrayList<>();for (int i = 0; i < levelOrder.length; i++) {if (i == rootIndex) continue; // 跳过根节点int val = levelOrder[i];int indexInInorder = inOrderMap.get(val);if (indexInInorder >= inStart && indexInInorder <= inEnd) {result.add(val);}}// 转换为数组int[] arr = new int[result.size()];for (int i = 0; i < result.size(); i++) {arr[i] = result.get(i);}return arr;}
}

三、常见树算法

3.1 计算树的高度/深度

public int maxDepth(TreeNode root) {if (root == null) return 0;return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}

3.2 判断对称二叉树

public boolean isSymmetric(TreeNode root) {if (root == null) return true;return 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.2 判断平衡二叉树

public boolean isBalanced(TreeNode root) {return checkHeight(root) != -1;
}private int checkHeight(TreeNode root) {if (root == null) return 0;int leftHeight = checkHeight(root.left);if (leftHeight == -1) return -1;int rightHeight = checkHeight(root.right);if (rightHeight == -1) return -1;if (Math.abs(leftHeight - rightHeight) > 1) return -1;return 1 + Math.max(leftHeight, rightHeight);
}

3.3 二叉搜索树验证

public boolean isValidBST(TreeNode root) {return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);
}private boolean isValidBST(TreeNode node, long min, long max) {if (node == null) return true;if (node.val <= min || node.val >= max) return false;return isValidBST(node.left, min, node.val) && isValidBST(node.right, node.val, max);
}

3.4 最近公共祖先 (LCA)

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {if (root == null || root == p || root == q) return root;TreeNode left = lowestCommonAncestor(root.left, p, q);TreeNode right = lowestCommonAncestor(root.right, p, q);if (left != null && right != null) return root;return left != null ? left : right;
}

四、二叉搜索树操作

注意：二叉搜索树的中序遍历为升序

4.1 查找节点

public TreeNode searchBST(TreeNode root, int val) {if (root == null || root.val == val) return root;return val < root.val ? searchBST(root.left, val) : searchBST(root.right, val);
}

4.2 插入节点

public TreeNode insertIntoBST(TreeNode root, int val) {if (root == null) return new TreeNode(val);if (val < root.val) {root.left = insertIntoBST(root.left, val);} else {root.right = insertIntoBST(root.right, val);}return root;
}

4.3 删除节点

public 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 minNode = findMin(root.right);root.val = minNode.val;root.right = deleteNode(root.right, root.val);}return root;
}private TreeNode findMin(TreeNode node) {while (node.left != null) {node = node.left;}return node;
}

五、堆

5.1 大根堆（Max Heap）

import java.util.Arrays;public class MaxHeap {private int[] heap;private int size;private int capacity;public MaxHeap(int capacity) {this.capacity = capacity;this.size = 0;this.heap = new int[capacity];}// 获取父节点索引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) {int temp = heap[i];heap[i] = heap[j];heap[j] = temp;}// 插入元素public void insert(int value) {if (size >= capacity) {System.out.println("Heap is full");return;}// 将新元素添加到堆的末尾heap[size] = value;int current = size;size++;// 向上调整堆while (current > 0 && heap[current] > heap[parent(current)]) {swap(current, parent(current));current = parent(current);}}// 删除并返回最大元素public int extractMax() {if (size <= 0) {System.out.println("Heap is empty");return Integer.MIN_VALUE;}if (size == 1) {size--;return heap[0];}// 保存最大值int max = heap[0];// 将最后一个元素移到根节点heap[0] = heap[size - 1];size--;// 向下调整堆maxHeapify(0);return max;}// 向下调整堆private void maxHeapify(int i) {int left = leftChild(i);int right = rightChild(i);int largest = i;if (left < size && heap[left] > heap[largest]) {largest = left;}if (right < size && heap[right] > heap[largest]) {largest = right;}if (largest != i) {swap(i, largest);maxHeapify(largest);}}// 构建最大堆public void buildMaxHeap(int[] arr) {if (arr.length > capacity) {System.out.println("Array size exceeds heap capacity");return;}System.arraycopy(arr, 0, heap, 0, arr.length);size = arr.length;// 从最后一个非叶子节点开始调整for (int i = (size / 2) - 1; i >= 0; i--) {maxHeapify(i);}}// 堆排序（升序）public void heapSort(int[] arr) {buildMaxHeap(arr);for (int i = size - 1; i > 0; i--) {swap(0, i);size--;maxHeapify(0);}// 恢复原始大小size = arr.length;}// 打印堆public void printHeap() {System.out.print("Heap: ");for (int i = 0; i < size; i++) {System.out.print(heap[i] + " ");}System.out.println();}// 测试代码public static void main(String[] args) {MaxHeap maxHeap = new MaxHeap(10);// 插入元素maxHeap.insert(10);maxHeap.insert(5);maxHeap.insert(20);maxHeap.insert(15);maxHeap.insert(30);maxHeap.printHeap();// 提取最大值System.out.println("Extracted max: " + maxHeap.extractMax());maxHeap.printHeap();// 堆排序int[] arr = {12, 11, 13, 5, 6, 7};maxHeap.heapSort(arr);System.out.println("Sorted array: " + Arrays.toString(arr));}
}

5.2 小根堆（Min Heap）

import java.util.Arrays;public class MinHeap {private int[] heap;private int size;private int capacity;public MinHeap(int capacity) {this.capacity = capacity;this.size = 0;this.heap = new int[capacity];}// 获取父节点索引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) {int temp = heap[i];heap[i] = heap[j];heap[j] = temp;}// 插入元素public void insert(int value) {if (size >= capacity) {System.out.println("Heap is full");return;}// 将新元素添加到堆的末尾heap[size] = value;int current = size;size++;// 向上调整堆while (current > 0 && heap[current] < heap[parent(current)]) {swap(current, parent(current));current = parent(current);}}// 删除并返回最小元素public int extractMin() {if (size <= 0) {System.out.println("Heap is empty");return Integer.MAX_VALUE;}if (size == 1) {size--;return heap[0];}// 保存最小值int min = heap[0];// 将最后一个元素移到根节点heap[0] = heap[size - 1];size--;// 向下调整堆minHeapify(0);return min;}// 向下调整堆private void minHeapify(int i) {int left = leftChild(i);int right = rightChild(i);int smallest = i;if (left < size && heap[left] < heap[smallest]) {smallest = left;}if (right < size && heap[right] < heap[smallest]) {smallest = right;}if (smallest != i) {swap(i, smallest);minHeapify(smallest);}}// 构建最小堆public void buildMinHeap(int[] arr) {if (arr.length > capacity) {System.out.println("Array size exceeds heap capacity");return;}System.arraycopy(arr, 0, heap, 0, arr.length);size = arr.length;// 从最后一个非叶子节点开始调整for (int i = (size / 2) - 1; i >= 0; i--) {minHeapify(i);}}// 堆排序（降序）public void heapSort(int[] arr) {buildMinHeap(arr);for (int i = size - 1; i > 0; i--) {swap(0, i);size--;minHeapify(0);}// 恢复原始大小size = arr.length;}// 打印堆public void printHeap() {System.out.print("Heap: ");for (int i = 0; i < size; i++) {System.out.print(heap[i] + " ");}System.out.println();}// 测试代码public static void main(String[] args) {MinHeap minHeap = new MinHeap(10);// 插入元素minHeap.insert(10);minHeap.insert(5);minHeap.insert(20);minHeap.insert(15);minHeap.insert(30);minHeap.printHeap();// 提取最小值System.out.println("Extracted min: " + minHeap.extractMin());minHeap.printHeap();// 堆排序int[] arr = {12, 11, 13, 5, 6, 7};minHeap.heapSort(arr);System.out.println("Sorted array: " + Arrays.toString(arr));}
}

5.3 Java内置的PriorityQueue可以用作堆

import java.util.PriorityQueue;
import java.util.Collections;public class HeapWithPriorityQueue {public static void main(String[] args) {// 小根堆（默认）PriorityQueue<Integer> minHeap = new PriorityQueue<>();minHeap.add(10);minHeap.add(5);minHeap.add(20);System.out.println("Min heap: " + minHeap);System.out.println("Min element: " + minHeap.peek());System.out.println("Extracted min: " + minHeap.poll());System.out.println("Min heap after extraction: " + minHeap);// 大根堆（使用Comparator.reverseOrder()）PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());maxHeap.add(10);maxHeap.add(5);maxHeap.add(20);System.out.println("\nMax heap: " + maxHeap);System.out.println("Max element: " + maxHeap.peek());System.out.println("Extracted max: " + maxHeap.poll());System.out.println("Max heap after extraction: " + maxHeap);}
}