二叉树详解

二叉树的定义

基本定义

二叉树（Binary Tree）是一种树形数据结构，其中每个节点最多有两个子节点，通常称为左子节点和右子节点。

如上图，图中每个圆圈都是一个节点，最顶层的节点叫做根节点，没有子节点的节点叫叶子节点。

基本术语

• 节点（Node）：树中的基本单位，包含数据和指向子节点的指针

• 根节点（Root）：树的顶层节点，没有父节点

• 叶子节点（Leaf）：没有子节点的节点

• 内部节点（Internal Node）：至少有一个子节点的节点

• 高度（Height）：二叉树的​​高度​是指从根节点到最远叶子节点的最长路径上的​​节点数​​

• 深度（Depth）：节点的深度是指从​​根节点​​到该节点的节点数

• 层级（Level）：根节点为第1层，其他节点的层级是其父节点层级加1

• 度：节点的子节点数

二叉树的类型

1. 满二叉树（Full Binary Tree）

• 定义：除了叶子节点外，每个节点都有两个子节点
• 特点：所有内部节点的度都为2
• 节点数：如果高度为h，则节点数为 2^h - 1

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

2. 完全二叉树（Complete Binary Tree）

• 定义：除了最后一层外，其他层都被完全填满，最后一层从左到右填充
• 特点：适合用数组存储，父子节点关系明确
• 应用：堆（Heap）的底层实现

      1
    /   \
   2     3
  / \   /
 4   5 6

3. 二叉搜索树（Binary Search Tree, BST）

• 定义：对于任意节点，左子树所有节点值 < 根节点值 < 右子树所有节点值
• 特点：中序遍历得到有序序列
• 应用：快速查找、插入、删除

      8
    /   \
   3     10
  / \      \
 1   6     14
    / \   /
   4   7 13

4. 平衡二叉树（Balanced Binary Tree）

• 定义：任意节点的左右子树高度差不超过1
• 目的：保证操作的时间复杂度为O(log n)
• 实现：AVL树、红黑树等

5. 退化二叉树（Degenerate Binary Tree）

• 定义：每个内部节点只有一个子节点
• 特点：类似于链表，失去了树的优势
• 时间复杂度：O(n)

1
 \
  2
   \
    3
     \
      4

二叉树的特征

数学性质

1. 节点数与边数关系：n个节点的二叉树有n-1条边

2. 层级节点数：第i层最多有 2^(i-1) 个节点（i≥1）

3. 高度与节点数关系：

   • 高度为h的二叉树最多有 2^h - 1 个节点
   • n个节点的完全二叉树高度为 log₂(n+1)

4. 叶子节点与度为2的节点关系：

   • 设度为0、1、2的节点数分别为n₀、n₁、n₂
   • 则有：n₀ = n₂ + 1

n₀ 表示叶子节点的数量

n₂ 表示度为 2 的节点的数量

每增加一个度为2的节点，会新增两个子节点，但其中一个子节点会“抵消”内部节点的增加，最终叶子节点始终比度为2的节点多一个。

存储方式

1. 链式存储

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

2. 数组存储（适用于完全二叉树）

• 根节点索引：0
• 节点i的左子节点：2*i + 1
• 节点i的右子节点：2*i + 2
• 节点i的父节点：(i-1)/2

---

二叉树的遍历方式

前序遍历，先遍历中间节点

中序遍历，先遍历左节点，后遍历中间节点

后续遍历，先遍历左节点，后遍历右节点，最后遍历中间节点

为了便于理解和记忆，可以理解成，前中后，是遍历中间节点的顺序

深度优先遍历（DFS）

1. 前序遍历（Pre-order）

• 顺序：根 → 左 → 右
• 应用：复制树、表达式求值

public void preorderTraversal(TreeNode root) {
    if (root != null) {
        visit(root);                    // 访问根节点
        preorderTraversal(root.left);   // 遍历左子树
        preorderTraversal(root.right);  // 遍历右子树
    }
}

2. 中序遍历（In-order）

• 顺序：左 → 根 → 右
• 应用：BST中获取有序序列

public void inorderTraversal(TreeNode root) {
    if (root != null) {
        inorderTraversal(root.left);    // 遍历左子树
        visit(root);                    // 访问根节点
        inorderTraversal(root.right);   // 遍历右子树
    }
}

3. 后序遍历（Post-order）

• 顺序：左 → 右 → 根
• 应用：删除树、计算目录大小

public void postorderTraversal(TreeNode root) {
    if (root != null) {
        postorderTraversal(root.left);  // 遍历左子树
        postorderTraversal(root.right); // 遍历右子树
        visit(root);                    // 访问根节点
    }
}

广度优先遍历（BFS）

层序遍历（Level-order）

• 顺序：逐层从左到右
• 实现：使用队列
• 应用：打印树的层级结构

public void levelOrderTraversal(TreeNode root) {
    if (root == null) return;
    
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    
    while (!queue.isEmpty()) {
        TreeNode node = queue.poll();
        visit(node);
        
        if (node.left != null) queue.offer(node.left);
        if (node.right != null) queue.offer(node.right);
    }
}

非递归实现

前序遍历（栈实现）

public List<Integer> preorderTraversal(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    if (root == null) return result;
    
    Stack<TreeNode> stack = new Stack<>();
    stack.push(root);
    
    while (!stack.isEmpty()) {
        TreeNode node = stack.pop();
        result.add(node.val);
        
        if (node.right != null) stack.push(node.right);
        if (node.left != null) stack.push(node.left);
    }
    
    return result;
}

---

二叉树的变型

1. AVL树

• 特点：严格平衡的二叉搜索树
• 平衡因子：左右子树高度差的绝对值 ≤ 1
• 旋转操作：LL、RR、LR、RL四种旋转
• 时间复杂度：查找、插入、删除均为O(log n)

2. 红黑树

• 特点：近似平衡的二叉搜索树
• 性质：
  1. 节点是红色或黑色
  2. 根节点是黑色
  3. 叶子节点（NIL）是黑色
  4. 红色节点的子节点必须是黑色
  5. 从任一节点到其叶子节点的所有路径包含相同数目的黑色节点
• 应用：Java的TreeMap、C++的map

3. B树和B+树

• B树：多路搜索树，适用于磁盘存储
• B+树：B树的变种，叶子节点包含所有关键字
• 应用：数据库索引、文件系统

4. 堆（Heap）

• 最大堆：父节点值 ≥ 子节点值
• 最小堆：父节点值 ≤ 子节点值
• 应用：优先队列、堆排序

5. 字典树（Trie）

• 特点：用于存储字符串的树形结构
• 应用：自动补全、拼写检查

6. 线段树（Segment Tree）

• 特点：用于区间查询和更新
• 应用：范围求和、区间最值查询

---

常见面试题

基础题目

1. 二叉树的最大深度

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

2. 判断二叉树是否对称

public boolean isSymmetric(TreeNode root) {
    return root == null || isSymmetricHelper(root.left, root.right);
}

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

3. 二叉树的层序遍历

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 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;
}

进阶题目

4. 二叉树的最近公共祖先

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;
}

5. 验证二叉搜索树

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);
}

6. 二叉树中的最大路径和

private int maxSum = Integer.MIN_VALUE;

public int maxPathSum(TreeNode root) {
    maxGain(root);
    return maxSum;
}

private int maxGain(TreeNode node) {
    if (node == null) return 0;
    
    int leftGain = Math.max(maxGain(node.left), 0);
    int rightGain = Math.max(maxGain(node.right), 0);
    
    int pathSum = node.val + leftGain + rightGain;
    maxSum = Math.max(maxSum, pathSum);
    
    return node.val + Math.max(leftGain, rightGain);
}

构造类题目

7. 从前序与中序遍历序列构造二叉树

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) return null;
    
    int rootVal = preorder[preStart];
    TreeNode root = new TreeNode(rootVal);
    
    int rootIndex = inorderMap.get(rootVal);
    int leftSize = rootIndex - inStart;
    
    root.left = buildTreeHelper(preorder, preStart + 1, preStart + leftSize,
                               inorder, inStart, rootIndex - 1, inorderMap);
    root.right = buildTreeHelper(preorder, preStart + leftSize + 1, preEnd,
                                inorder, rootIndex + 1, inEnd, inorderMap);
    
    return root;
}

---

代码实现

完整的二叉树节点类

public class TreeNode {
    public int val;
    public TreeNode left;
    public 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;
    }
}

二叉搜索树实现

public class BinarySearchTree {
    private TreeNode root;
    
    public void insert(int val) {
        root = insertHelper(root, val);
    }
    
    private TreeNode insertHelper(TreeNode node, int val) {
        if (node == null) return new TreeNode(val);
        
        if (val < node.val) {
            node.left = insertHelper(node.left, val);
        } else if (val > node.val) {
            node.right = insertHelper(node.right, val);
        }
        
        return node;
    }
    
    public boolean search(int val) {
        return searchHelper(root, val);
    }
    
    private boolean searchHelper(TreeNode node, int val) {
        if (node == null) return false;
        if (node.val == val) return true;
        
        return val < node.val ? searchHelper(node.left, val) 
                              : searchHelper(node.right, val);
    }
    
    public void delete(int val) {
        root = deleteHelper(root, val);
    }
    
    private TreeNode deleteHelper(TreeNode node, int val) {
        if (node == null) return null;
        
        if (val < node.val) {
            node.left = deleteHelper(node.left, val);
        } else if (val > node.val) {
            node.right = deleteHelper(node.right, val);
        } else {
            // 找到要删除的节点
            if (node.left == null) return node.right;
            if (node.right == null) return node.left;
            
            // 节点有两个子节点
            TreeNode minNode = findMin(node.right);
            node.val = minNode.val;
            node.right = deleteHelper(node.right, minNode.val);
        }
        
        return node;
    }
    
    private TreeNode findMin(TreeNode node) {
        while (node.left != null) {
            node = node.left;
        }
        return node;
    }
}

---

时间复杂度分析

基本操作复杂度

操作	平衡二叉树	普通二叉树	退化二叉树
查找	O(log n)	O(log n)	O(n)
插入	O(log n)	O(log n)	O(n)
删除	O(log n)	O(log n)	O(n)
遍历	O(n)	O(n)	O(n)

空间复杂度

• 递归遍历：O(h)，其中h为树的高度
• 非递归遍历：O(h)，栈或队列的空间
• 存储空间：O(n)，n为节点数

优化策略

1. 平衡性维护：使用AVL树或红黑树
2. 缓存优化：局部性原理，B树适合磁盘存储
3. 并发控制：读写锁、无锁数据结构

---

总结

二叉树是计算机科学中最重要的数据结构之一，具有以下特点：

优势

• 查找效率高：平衡二叉树的查找时间复杂度为O(log n)
• 插入删除灵活：动态调整结构
• 遍历方式多样：支持多种遍历策略
• 应用广泛：数据库索引、编译器、文件系统等

注意事项

• 平衡性：避免退化为链表
• 空间开销：指针占用额外空间
• 缓存友好性：相比数组，缓存命中率较低

学习建议

1. 掌握基础概念：理解各种类型和性质
2. 熟练遍历算法：递归和非递归实现
3. 练习经典题目：LeetCode相关题目
4. 理解应用场景：数据库、操作系统等实际应用
5. 关注性能优化：平衡性、缓存、并发等

通过系统学习和大量练习，可以深入理解二叉树的精髓，为后续学习更复杂的数据结构和算法打下坚实基础。