算法详解：二叉树完全指南 - 树形结构的核心基础

前言

二叉树是计算机科学中最重要的数据结构之一，它在算法设计、数据存储、搜索优化等领域都有广泛的应用。从文件系统的目录结构到搜索引擎的索引，从表达式求值到机器学习中的决策树，二叉树无处不在。本文将带你深入理解二叉树的概念、实现和应用，为你的编程技能打下坚实的基础。

1. 二叉树基本概念

1.1 什么是二叉树

二叉树（Binary Tree）是一种树形数据结构，其中每个节点最多有两个子节点，分别称为左子节点和右子节点。这种结构具有天然的递归特性，使得很多操作都可以用递归的方式优雅地实现。

1.2 二叉树的基本术语

根节点（Root）：树的顶部节点，没有父节点
叶子节点（Leaf）：没有子节点的节点
内部节点（Internal Node）：有至少一个子节点的节点
深度（Depth）：从根节点到某个节点的边数
高度（Height）：从某个节点到叶子节点的最长路径的边数
层（Level）：具有相同深度的节点组成一层

1.3 二叉树的视觉表示

1
2
3
4
5
6
7
         1
       /   \
      2     3
     / \   / \
    4   5 6   7
   /
  8

在这个例子中：

节点1是根节点
节点8、5、6、7是叶子节点
树的高度是3
节点4在第3层

2. 现实生活中的二叉树应用

2.1 决策树

想象你在决定今天是否出门：

1
2
3
4
5
6
7
      出门吗？
     /      \
   天气好？   天气不好？
   /    \     /      \
  出门   不出门 有急事？  不出门
                /    \
              出门   不出门

这种决策过程天然地形成了二叉树结构。

2.2 文件系统

计算机的文件系统也是树形结构的典型例子：

1
2
3
4
5
6
7
     根目录
    /      \
  用户     系统
 /   \    /    \
张三  李四 配置  日志
/  \       |
文档 图片   设置

2.3 表达式解析

数学表达式可以用二叉树来表示和计算：

1
2
3
4
5
6
7
表达式：(3 + 5) * 2

    *
   / \
  +   2
 / \
3   5

3. Java中的二叉树实现

3.1 节点类定义

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * 二叉树节点类
 */
public class TreeNode {
    int val;           // 节点值
    TreeNode left;     // 左子节点
    TreeNode right;    // 右子节点

    // 构造函数
    public TreeNode() {}

    public TreeNode(int val) {
        this.val = val;
    }

    public TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

3.2 二叉树类实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
import java.util.*;

/**
 * 二叉树完整实现类
 */
public class BinaryTree {
    private TreeNode root;

    public BinaryTree() {
        this.root = null;
    }

    public BinaryTree(TreeNode root) {
        this.root = root;
    }

    // 获取根节点
    public TreeNode getRoot() {
        return root;
    }

    // 设置根节点
    public void setRoot(TreeNode root) {
        this.root = root;
    }

    // 检查树是否为空
    public boolean isEmpty() {
        return root == null;
    }

    // 获取树的高度
    public int getHeight() {
        return getHeight(root);
    }

    private int getHeight(TreeNode node) {
        if (node == null) {
            return 0;
        }
        return 1 + Math.max(getHeight(node.left), getHeight(node.right));
    }

    // 获取节点数量
    public int getSize() {
        return getSize(root);
    }

    private int getSize(TreeNode node) {
        if (node == null) {
            return 0;
        }
        return 1 + getSize(node.left) + getSize(node.right);
    }

    // 查找节点
    public boolean contains(int val) {
        return contains(root, val);
    }

    private boolean contains(TreeNode node, int val) {
        if (node == null) {
            return false;
        }
        if (node.val == val) {
            return true;
        }
        return contains(node.left, val) || contains(node.right, val);
    }
}

4. 二叉树的遍历方法

遍历是访问树中所有节点的过程。二叉树有四种主要的遍历方式：

4.1 前序遍历（Pre-order）

访问顺序：根节点 → 左子树 → 右子树

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
/**
 * 前序遍历 - 递归实现
 */
public List<Integer> preorderTraversal(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    preorderHelper(root, result);
    return result;
}

private void preorderHelper(TreeNode node, List<Integer> result) {
    if (node == null) {
        return;
    }
    result.add(node.val);           // 访问根节点
    preorderHelper(node.left, result);   // 遍历左子树
    preorderHelper(node.right, result);  // 遍历右子树
}

/**
 * 前序遍历 - 迭代实现
 */
public List<Integer> preorderTraversalIterative(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    if (root == null) {
        return result;
    }

    Stack<TreeNode> stack = new Stack<>();
    stack.push(root);

    while (!stack.isEmpty()) {
        TreeNode current = stack.pop();
        result.add(current.val);

        // 先压入右子节点，再压入左子节点
        if (current.right != null) {
            stack.push(current.right);
        }
        if (current.left != null) {
            stack.push(current.left);
        }
    }

    return result;
}

4.2 中序遍历（In-order）

访问顺序：左子树 → 根节点 → 右子树

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
/**
 * 中序遍历 - 递归实现
 */
public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    inorderHelper(root, result);
    return result;
}

private void inorderHelper(TreeNode node, List<Integer> result) {
    if (node == null) {
        return;
    }
    inorderHelper(node.left, result);    // 遍历左子树
    result.add(node.val);               // 访问根节点
    inorderHelper(node.right, result);   // 遍历右子树
}

/**
 * 中序遍历 - 迭代实现
 */
public List<Integer> inorderTraversalIterative(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    Stack<TreeNode> stack = new Stack<>();
    TreeNode current = root;

    while (current != null || !stack.isEmpty()) {
        // 一直向左走到底
        while (current != null) {
            stack.push(current);
            current = current.left;
        }

        // 处理栈顶节点
        current = stack.pop();
        result.add(current.val);

        // 转向右子树
        current = current.right;
    }

    return result;
}

4.3 后序遍历（Post-order）

访问顺序：左子树 → 右子树 → 根节点

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
/**
 * 后序遍历 - 递归实现
 */
public List<Integer> postorderTraversal(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    postorderHelper(root, result);
    return result;
}

private void postorderHelper(TreeNode node, List<Integer> result) {
    if (node == null) {
        return;
    }
    postorderHelper(node.left, result);   // 遍历左子树
    postorderHelper(node.right, result);  // 遍历右子树
    result.add(node.val);                // 访问根节点
}

/**
 * 后序遍历 - 迭代实现
 */
public List<Integer> postorderTraversalIterative(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    if (root == null) {
        return result;
    }

    Stack<TreeNode> stack = new Stack<>();
    TreeNode lastVisited = null;
    TreeNode current = root;

    while (current != null || !stack.isEmpty()) {
        if (current != null) {
            stack.push(current);
            current = current.left;
        } else {
            TreeNode peekNode = stack.peek();
            // 右子树存在且未被访问过
            if (peekNode.right != null && lastVisited != peekNode.right) {
                current = peekNode.right;
            } else {
                result.add(peekNode.val);
                lastVisited = stack.pop();
            }
        }
    }

    return result;
}

4.4 层序遍历（Level-order）

逐层从左到右访问节点

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
/**
 * 层序遍历 - 队列实现
 */
public 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 levelSize = queue.size();
        List<Integer> currentLevel = new ArrayList<>();

        for (int i = 0; i < levelSize; i++) {
            TreeNode current = queue.poll();
            currentLevel.add(current.val);

            if (current.left != null) {
                queue.offer(current.left);
            }
            if (current.right != null) {
                queue.offer(current.right);
            }
        }

        result.add(currentLevel);
    }

    return result;
}

/**
 * 层序遍历 - 简单版本
 */
public List<Integer> levelOrderSimple(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    if (root == null) {
        return result;
    }

    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);

    while (!queue.isEmpty()) {
        TreeNode current = queue.poll();
        result.add(current.val);

        if (current.left != null) {
            queue.offer(current.left);
        }
        if (current.right != null) {
            queue.offer(current.right);
        }
    }

    return result;
}

5. 二叉树的类型

5.1 完全二叉树（Complete Binary Tree）

除了最后一层外，其他各层都被完全填满，最后一层从左到右填入。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
完全二叉树示例：
       1
     /   \
    2     3
   / \   /
  4   5 6

特点：
- 节点按层序从左到右编号
- 如果有n个节点，那么节点i的左子节点是2*i+1，右子节点是2*i+2

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/**
 * 检查是否为完全二叉树
 */
public boolean isCompleteTree(TreeNode root) {
    if (root == null) {
        return true;
    }

    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    boolean nullSeen = false;

    while (!queue.isEmpty()) {
        TreeNode current = queue.poll();

        if (current == null) {
            nullSeen = true;
        } else {
            if (nullSeen) {
                return false; // 在null之后不能再有非null节点
            }
            queue.offer(current.left);
            queue.offer(current.right);
        }
    }

    return true;
}

5.2 满二叉树（Perfect Binary Tree）

所有叶子节点都在同一层，且每个内部节点都有两个子节点。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
满二叉树示例：
       1
     /   \
    2     3
   / \   / \
  4   5 6   7

特点：
- 如果高度为h，则有2^(h+1)-1个节点
- 叶子节点数为2^h

1
2
3
4
5
6
7
8
/**
 * 检查是否为满二叉树
 */
public boolean isPerfectTree(TreeNode root) {
    int height = getHeight(root);
    int nodeCount = getSize(root);
    return nodeCount == Math.pow(2, height) - 1;
}

5.3 平衡二叉树（Balanced Binary Tree）

任何节点的两个子树的高度差不超过1。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * 检查是否为平衡二叉树
 */
public boolean isBalanced(TreeNode root) {
    return checkBalance(root) != -1;
}

private int checkBalance(TreeNode node) {
    if (node == null) {
        return 0;
    }

    int leftHeight = checkBalance(node.left);
    if (leftHeight == -1) return -1;

    int rightHeight = checkBalance(node.right);
    if (rightHeight == -1) return -1;

    if (Math.abs(leftHeight - rightHeight) > 1) {
        return -1;
    }

    return Math.max(leftHeight, rightHeight) + 1;
}

6. 高级操作

6.1 二叉树的重建

根据前序和中序遍历重建二叉树：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/**
 * 根据前序和中序遍历重建二叉树
 */
public TreeNode buildTree(int[] preorder, int[] inorder) {
    Map<Integer, Integer> inorderMap = new HashMap<>();
    for (int i = 0; i < inorder.length; i++) {
        inorderMap.put(inorder[i], i);
    }

    return buildTreeHelper(preorder, 0, preorder.length - 1,
                          inorder, 0, inorder.length - 1, inorderMap);
}

private TreeNode buildTreeHelper(int[] preorder, int preStart, int preEnd,
                               int[] inorder, int inStart, int inEnd,
                               Map<Integer, Integer> inorderMap) {
    if (preStart > preEnd || inStart > inEnd) {
        return null;
    }

    int rootVal = preorder[preStart];
    TreeNode root = new TreeNode(rootVal);

    int rootIndex = inorderMap.get(rootVal);
    int leftTreeSize = rootIndex - inStart;

    root.left = buildTreeHelper(preorder, preStart + 1, preStart + leftTreeSize,
                              inorder, inStart, rootIndex - 1, inorderMap);

    root.right = buildTreeHelper(preorder, preStart + leftTreeSize + 1, preEnd,
                               inorder, rootIndex + 1, inEnd, inorderMap);

    return root;
}

6.2 二叉树的序列化和反序列化

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
/**
 * 序列化二叉树
 */
public String serialize(TreeNode root) {
    StringBuilder sb = new StringBuilder();
    serializeHelper(root, sb);
    return sb.toString();
}

private void serializeHelper(TreeNode node, StringBuilder sb) {
    if (node == null) {
        sb.append("#,");
        return;
    }
    sb.append(node.val).append(",");
    serializeHelper(node.left, sb);
    serializeHelper(node.right, sb);
}

/**
 * 反序列化二叉树
 */
public TreeNode deserialize(String data) {
    String[] nodes = data.split(",");
    Queue<String> queue = new LinkedList<>(Arrays.asList(nodes));
    return deserializeHelper(queue);
}

private TreeNode deserializeHelper(Queue<String> queue) {
    String val = queue.poll();
    if ("#".equals(val)) {
        return null;
    }
    TreeNode node = new TreeNode(Integer.valueOf(val));
    node.left = deserializeHelper(queue);
    node.right = deserializeHelper(queue);
    return node;
}

6.3 线索二叉树（Threaded Binary Tree）

为了提高遍历效率，可以利用空指针域存储遍历序列中的前驱和后继信息。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
/**
 * 线索二叉树节点
 */
class ThreadedNode {
    int val;
    ThreadedNode left, right;
    boolean leftThread, rightThread; // 标记是否为线索

    ThreadedNode(int val) {
        this.val = val;
        this.leftThread = false;
        this.rightThread = false;
    }
}

/**
 * 中序线索化
 */
public class ThreadedBinaryTree {
    private ThreadedNode prev;

    public void inorderThreading(ThreadedNode root) {
        if (root == null) return;

        inorderThreading(root.left);

        // 处理当前节点
        if (root.left == null) {
            root.left = prev;
            root.leftThread = true;
        }
        if (prev != null && prev.right == null) {
            prev.right = root;
            prev.rightThread = true;
        }

        prev = root;
        inorderThreading(root.right);
    }

    /**
     * 线索二叉树的中序遍历
     */
    public void inorderTraversal(ThreadedNode root) {
        ThreadedNode current = getLeftmost(root);

        while (current != null) {
            System.out.print(current.val + " ");

            if (current.rightThread) {
                current = current.right;
            } else {
                current = getLeftmost(current.right);
            }
        }
    }

    private ThreadedNode getLeftmost(ThreadedNode node) {
        if (node == null) return null;

        while (node.left != null && !node.leftThread) {
            node = node.left;
        }
        return node;
    }
}

7. 二叉树的实际应用

7.1 表达式求值

使用二叉树可以优雅地解析和计算数学表达式：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
/**
 * 表达式树节点
 */
class ExpressionNode {
    String value;
    ExpressionNode left, right;

    ExpressionNode(String value) {
        this.value = value;
    }

    boolean isOperator() {
        return "+".equals(value) || "-".equals(value) ||
               "*".equals(value) || "/".equals(value);
    }
}

/**
 * 表达式树计算器
 */
public class ExpressionTree {
    public double evaluate(ExpressionNode root) {
        if (root == null) return 0;

        if (!root.isOperator()) {
            return Double.parseDouble(root.value);
        }

        double leftVal = evaluate(root.left);
        double rightVal = evaluate(root.right);

        switch (root.value) {
            case "+": return leftVal + rightVal;
            case "-": return leftVal - rightVal;
            case "*": return leftVal * rightVal;
            case "/": return leftVal / rightVal;
            default: throw new IllegalArgumentException("Unknown operator");
        }
    }

    /**
     * 从后缀表达式构建表达式树
     */
    public ExpressionNode buildFromPostfix(String[] postfix) {
        Stack<ExpressionNode> stack = new Stack<>();

        for (String token : postfix) {
            ExpressionNode node = new ExpressionNode(token);

            if (node.isOperator()) {
                node.right = stack.pop();
                node.left = stack.pop();
            }

            stack.push(node);
        }

        return stack.pop();
    }
}

7.2 霍夫曼编码（Huffman Coding）

霍夫曼编码是一种用于数据压缩的贪心算法，使用二叉树来构建最优前缀编码：

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
/**
 * 霍夫曼节点
 */
class HuffmanNode implements Comparable<HuffmanNode> {
    char character;
    int frequency;
    HuffmanNode left, right;

    HuffmanNode(char character, int frequency) {
        this.character = character;
        this.frequency = frequency;
    }

    HuffmanNode(int frequency, HuffmanNode left, HuffmanNode right) {
        this.frequency = frequency;
        this.left = left;
        this.right = right;
    }

    @Override
    public int compareTo(HuffmanNode other) {
        return Integer.compare(this.frequency, other.frequency);
    }

    boolean isLeaf() {
        return left == null && right == null;
    }
}

/**
 * 霍夫曼编码器
 */
public class HuffmanCoding {
    private Map<Character, String> codeTable;

    public HuffmanNode buildHuffmanTree(String text) {
        // 统计字符频率
        Map<Character, Integer> frequency = new HashMap<>();
        for (char c : text.toCharArray()) {
            frequency.put(c, frequency.getOrDefault(c, 0) + 1);
        }

        // 构建优先队列
        PriorityQueue<HuffmanNode> pq = new PriorityQueue<>();
        for (Map.Entry<Character, Integer> entry : frequency.entrySet()) {
            pq.offer(new HuffmanNode(entry.getKey(), entry.getValue()));
        }

        // 构建霍夫曼树
        while (pq.size() > 1) {
            HuffmanNode left = pq.poll();
            HuffmanNode right = pq.poll();
            HuffmanNode parent = new HuffmanNode(
                left.frequency + right.frequency, left, right);
            pq.offer(parent);
        }

        return pq.poll();
    }

    public void generateCodes(HuffmanNode root) {
        codeTable = new HashMap<>();
        if (root != null) {
            generateCodesHelper(root, "");
        }
    }

    private void generateCodesHelper(HuffmanNode node, String code) {
        if (node.isLeaf()) {
            codeTable.put(node.character, code.isEmpty() ? "0" : code);
            return;
        }

        if (node.left != null) {
            generateCodesHelper(node.left, code + "0");
        }
        if (node.right != null) {
            generateCodesHelper(node.right, code + "1");
        }
    }

    public String encode(String text) {
        StringBuilder encoded = new StringBuilder();
        for (char c : text.toCharArray()) {
            encoded.append(codeTable.get(c));
        }
        return encoded.toString();
    }

    public String decode(String encoded, HuffmanNode root) {
        StringBuilder decoded = new StringBuilder();
        HuffmanNode current = root;

        for (char bit : encoded.toCharArray()) {
            if (bit == '0') {
                current = current.left;
            } else {
                current = current.right;
            }

            if (current.isLeaf()) {
                decoded.append(current.character);
                current = root;
            }
        }

        return decoded.toString();
    }
}

7.3 堆（Heap）

二叉堆是一种特殊的完全二叉树，广泛用于优先队列和排序算法：

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
/**
 * 最大堆实现
 */
public class MaxHeap {
    private List<Integer> heap;

    public MaxHeap() {
        heap = new ArrayList<>();
    }

    public MaxHeap(int[] array) {
        heap = new ArrayList<>();
        for (int num : array) {
            heap.add(num);
        }
        buildHeap();
    }

    // 构建堆
    private void buildHeap() {
        for (int i = (heap.size() / 2) - 1; i >= 0; i--) {
            heapifyDown(i);
        }
    }

    // 插入元素
    public void insert(int value) {
        heap.add(value);
        heapifyUp(heap.size() - 1);
    }

    // 删除最大元素
    public int extractMax() {
        if (heap.isEmpty()) {
            throw new IllegalStateException("Heap is empty");
        }

        int max = heap.get(0);
        int lastElement = heap.remove(heap.size() - 1);

        if (!heap.isEmpty()) {
            heap.set(0, lastElement);
            heapifyDown(0);
        }

        return max;
    }

    // 向上调整
    private void heapifyUp(int index) {
        while (index > 0) {
            int parentIndex = (index - 1) / 2;
            if (heap.get(index) <= heap.get(parentIndex)) {
                break;
            }
            swap(index, parentIndex);
            index = parentIndex;
        }
    }

    // 向下调整
    private void heapifyDown(int index) {
        while (true) {
            int largest = index;
            int leftChild = 2 * index + 1;
            int rightChild = 2 * index + 2;

            if (leftChild < heap.size() &&
                heap.get(leftChild) > heap.get(largest)) {
                largest = leftChild;
            }

            if (rightChild < heap.size() &&
                heap.get(rightChild) > heap.get(largest)) {
                largest = rightChild;
            }

            if (largest == index) {
                break;
            }

            swap(index, largest);
            index = largest;
        }
    }

    private void swap(int i, int j) {
        int temp = heap.get(i);
        heap.set(i, heap.get(j));
        heap.set(j, temp);
    }

    public int peek() {
        if (heap.isEmpty()) {
            throw new IllegalStateException("Heap is empty");
        }
        return heap.get(0);
    }

    public boolean isEmpty() {
        return heap.isEmpty();
    }

    public int size() {
        return heap.size();
    }
}

8. 性能分析和优化

8.1 时间复杂度分析

操作	平均情况	最坏情况	说明
搜索	O(log n)	O(n)	平衡树 vs 退化为链表
插入	O(log n)	O(n)	同上
删除	O(log n)	O(n)	同上
遍历	O(n)	O(n)	必须访问所有节点

8.2 空间复杂度分析

递归遍历：O(h)，其中h是树的高度（递归栈空间）
迭代遍历：O(h)（显式栈空间）
存储空间：O(n)（n个节点）

8.3 优化技巧

路径压缩：在某些应用中可以压缩路径以减少查找时间
节点缓存：缓存频繁访问的节点
平衡维护：使用AVL树或红黑树保持平衡
内存池：预分配节点内存以减少动态分配开销

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
/**
 * 优化的二叉树实现示例
 */
public class OptimizedBinaryTree {
    private TreeNode root;
    private Map<Integer, TreeNode> cache; // 节点缓存
    private final int CACHE_SIZE = 100;

    public OptimizedBinaryTree() {
        this.cache = new LRUCache<>(CACHE_SIZE);
    }

    // LRU缓存实现
    private static class LRUCache<K, V> extends LinkedHashMap<K, V> {
        private final int maxSize;

        public LRUCache(int maxSize) {
            super(16, 0.75f, true);
            this.maxSize = maxSize;
        }

        @Override
        protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
            return size() > maxSize;
        }
    }

    // 带缓存的查找
    public TreeNode findWithCache(int val) {
        if (cache.containsKey(val)) {
            return cache.get(val);
        }

        TreeNode node = find(root, val);
        if (node != null) {
            cache.put(val, node);
        }
        return node;
    }

    private TreeNode find(TreeNode node, int val) {
        if (node == null || node.val == val) {
            return node;
        }

        TreeNode leftResult = find(node.left, val);
        if (leftResult != null) {
            return leftResult;
        }

        return find(node.right, val);
    }
}

9. 常见面试题目

9.1 判断两棵树是否相同

1
2
3
4
5
6
7
public boolean isSameTree(TreeNode p, TreeNode q) {
    if (p == null && q == null) return true;
    if (p == null || q == null) return false;
    if (p.val != q.val) return false;

    return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}

9.2 二叉树的最大深度

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

9.3 翻转二叉树

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
public TreeNode invertTree(TreeNode root) {
    if (root == null) return null;

    TreeNode temp = root.left;
    root.left = root.right;
    root.right = temp;

    invertTree(root.left);
    invertTree(root.right);

    return root;
}

9.4 二叉树的直径

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
private int diameter = 0;

public int diameterOfBinaryTree(TreeNode root) {
    maxDepth(root);
    return diameter;
}

private int maxDepth(TreeNode root) {
    if (root == null) return 0;

    int left = maxDepth(root.left);
    int right = maxDepth(root.right);

    diameter = Math.max(diameter, left + right);

    return Math.max(left, right) + 1;
}

10. 总结

二叉树是计算机科学中的基础数据结构，掌握二叉树对于理解更复杂的数据结构和算法至关重要。通过本文的学习，你应该掌握了：

基本概念：理解二叉树的定义、术语和特性
实现技巧：掌握节点类和树类的设计
遍历方法：熟练运用四种遍历方式
树的分类：了解不同类型二叉树的特点
高级操作：掌握重建、序列化、线索化等技术
实际应用：理解二叉树在表达式求值、编码、堆等方面的应用
性能优化：了解时空复杂度分析和优化方法

二叉树的学习是一个循序渐进的过程，建议多做练习，通过实际编程来加深理解。在掌握了基本二叉树后，可以进一步学习二叉搜索树、AVL树、红黑树等更高级的树结构。

记住，理论学习只是第一步，只有通过大量的编程实践，才能真正掌握二叉树的精髓。继续努力，你将在算法和数据结构的道路上走得更远！

算法详解：二叉树完全指南 - 树形结构的核心基础#

前言#

1. 二叉树基本概念#

1.1 什么是二叉树#

1.2 二叉树的基本术语#

1.3 二叉树的视觉表示#

2. 现实生活中的二叉树应用#

2.1 决策树#

2.2 文件系统#

2.3 表达式解析#

3. Java中的二叉树实现#

3.1 节点类定义#

3.2 二叉树类实现#

4. 二叉树的遍历方法#

4.1 前序遍历（Pre-order）#

4.2 中序遍历（In-order）#

4.3 后序遍历（Post-order）#

4.4 层序遍历（Level-order）#

5. 二叉树的类型#

5.1 完全二叉树（Complete Binary Tree）#

5.2 满二叉树（Perfect Binary Tree）#

5.3 平衡二叉树（Balanced Binary Tree）#

6. 高级操作#

6.1 二叉树的重建#

6.2 二叉树的序列化和反序列化#

6.3 线索二叉树（Threaded Binary Tree）#

7. 二叉树的实际应用#

7.1 表达式求值#

7.2 霍夫曼编码（Huffman Coding）#

7.3 堆（Heap）#

8. 性能分析和优化#

8.1 时间复杂度分析#

8.2 空间复杂度分析#

8.3 优化技巧#

9. 常见面试题目#

9.1 判断两棵树是否相同#

9.2 二叉树的最大深度#

9.3 翻转二叉树#

9.4 二叉树的直径#

10. 总结#