Java树结构详解：二叉树遍历与BST实现-平芜编程栈

1. 树结构基础概念解析

树（Tree）是计算机科学中最基础且重要的非线性数据结构之一，它模拟了自然界中树木的层次结构。在Java开发中，树结构被广泛应用于文件系统、数据库索引、游戏AI等领域。与线性结构的数组和链表不同，树结构具有以下核心特性：

节点关系：每个节点有零个或多个子节点，除根节点外，每个节点有且仅有一个父节点
层级关系：节点间存在明确的父子层级，没有循环引用
术语体系：
- 根节点（Root）：没有父节点的顶层节点
- 叶子节点（Leaf）：没有子节点的末端节点
- 度（Degree）：节点拥有的子树数量
- 深度（Depth）：根节点到该节点的路径长度
- 高度（Height）：节点到最远叶子节点的路径长度

提示：在实际编码面试中，面试官常会要求候选人手写树结构的遍历算法，这是检验基础数据结构掌握程度的经典考题。

2. 二叉树与Java实现

2.1 二叉树基本结构

二叉树是每个节点最多有两个子节点（左子节点和右子节点）的树结构。以下是Java中的典型节点类定义：

class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int x) { val = x; } }

2.2 二叉树遍历方式

二叉树有三种基础遍历方式，每种方式又分为递归和迭代两种实现：

前序遍历（Pre-order）
- 访问顺序：根 → 左 → 右
- 应用场景：复制树结构
中序遍历（In-order）
- 访问顺序：左 → 根 → 右
- 重要特性：对二叉搜索树会得到有序序列
后序遍历（Post-order）
- 访问顺序：左 → 右 → 根
- 应用场景：计算子树特征值

// 递归版前序遍历示例 void preOrder(TreeNode root) { if (root == null) return; System.out.print(root.val + " "); preOrder(root.left); preOrder(root.right); }

2.3 层序遍历实现

层序遍历（Level-order）使用队列实现，按层级输出节点：

void levelOrder(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); } }

3. 二叉搜索树实战

3.1 BST特性与实现

二叉搜索树（BST）是具有以下特性的二叉树：

左子树所有节点值小于根节点值
右子树所有节点值大于根节点值
左右子树也分别是BST

class BST { private TreeNode root; // 插入操作 public void insert(int val) { root = insertRec(root, val); } private TreeNode insertRec(TreeNode root, int val) { if (root == null) return new TreeNode(val); if (val < root.val) { root.left = insertRec(root.left, val); } else if (val > root.val) { root.right = insertRec(root.right, val); } return root; } }

3.2 平衡优化策略

基础BST在极端情况下会退化为链表，因此需要平衡策略：

AVL树：通过旋转保持左右子树高度差≤1
红黑树：通过颜色标记和旋转规则维持平衡
B/B+树：多路平衡树，常用于数据库系统

4. 高级树结构应用

4.1 字典树（Trie）

用于高效存储和检索字符串集合：

class TrieNode { TrieNode[] children = new TrieNode[26]; boolean isEnd; } class Trie { private TrieNode root; public void insert(String word) { TrieNode node = root; for (char c : word.toCharArray()) { int index = c - 'a'; if (node.children[index] == null) { node.children[index] = new TrieNode(); } node = node.children[index]; } node.isEnd = true; } }

4.2 堆结构实现

堆是一种特殊的完全二叉树，常用于优先队列：

class MaxHeap { private int[] heap; private int size; public void insert(int item) { heap[++size] = item; swim(size); } private void swim(int k) { while (k > 1 && heap[k/2] < heap[k]) { swap(k, k/2); k = k/2; } } }

5. 树结构算法实战技巧

5.1 递归解题模板

解决树问题常用递归框架：

返回值类型 traversal(TreeNode root) { // 1. 终止条件 if (root == null) return ...; // 2. 处理当前层 ... // 3. 递归调用 返回值类型 left = traversal(root.left); 返回值类型 right = traversal(root.right); // 4. 合并结果 return ...; }

5.2 常见问题解决方案

求树的最大深度

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

判断对称二叉树

boolean isSymmetric(TreeNode root) { return root == null || check(root.left, root.right); } boolean check(TreeNode left, TreeNode right) { if (left == null && right == null) return true; if (left == null || right == null) return false; return left.val == right.val && check(left.left, right.right) && check(left.right, right.left); }