一、二叉树（Binary Tree）

1. 核心概念（通俗理解）

二叉树是一种分层树形数据结构，每个节点最多只有两个子节点（左子节点、右子节点），像一棵 “倒着长的树”，核心用于有序数据存储、快速查找 / 插入（如二叉搜索树）。

• 常见类型：
  • 二叉搜索树（BST）：左子树值 <根节点 < 右子树值，查找效率 O (logn)；
  • 平衡二叉树（AVL / 红黑树）：解决 BST 退化成链表的问题，保证查找稳定性；
  • 完全二叉树 / 满二叉树：常用于堆（优先队列）实现。

2. 核心操作（Java 示例）

java

运行

// 二叉树节点定义
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int val) { this.val = val; }
}

// 二叉树遍历（核心操作：前/中/后序、层序）
public class BinaryTreeDemo {
    // 中序遍历（二叉搜索树遍历结果为升序）
    public void inorder(TreeNode root) {
        if (root == null) return;
        inorder(root.left);       // 左
        System.out.print(root.val + " "); // 根
        inorder(root.right);      // 右
    }

    public static void main(String[] args) {
        // 构建简单二叉树
        TreeNode root = new TreeNode(1);
        root.right = new TreeNode(2);
        root.right.left = new TreeNode(3);
        
        BinaryTreeDemo demo = new BinaryTreeDemo();
        demo.inorder(root); // 输出：1 3 2
    }
}

3. 应用场景

• 排序 / 查找：二叉搜索树、TreeSet/TreeMap（底层红黑树）；
• 路径规划：二叉树遍历解决算法题（如求路径和、层序遍历打印）；
• 编译器：表达式树（如计算 1+2*3 的语法树）。

二、哈希表（Hash Table）

1. 核心概念（通俗理解）

哈希表是基于哈希函数将数据映射到数组下标存储的结构，核心是以空间换时间，实现 O (1) 级别的快速查找 / 插入 / 删除（理想情况）。

• 核心原理：
  • 哈希函数：将 key（如字符串、数字）转换成数组下标（如 hashCode() % 数组长度）；
  • 冲突解决：Java 中 HashMap 用 “数组 + 链表 + 红黑树”（JDK1.8+）解决哈希冲突。

2. 核心操作（Java 示例）

java

运行

import java.util.HashMap;

public class HashMapDemo {
    public static void main(String[] args) {
        // 创建哈希表（键值对存储）
        HashMap<String, Integer> map = new HashMap<>();
        
        // 1. 插入
        map.put("Java", 90);
        map.put("Python", 85);
        map.put("C++", 88);
        
        // 2. 查找（O(1)）
        System.out.println(map.get("Java")); // 输出：90
        System.out.println(map.getOrDefault("PHP", 0)); // 无则返回默认值：0
        
        // 3. 遍历
        for (String key : map.keySet()) {
            System.out.println(key + ": " + map.get(key));
        }
        
        // 4. 删除
        map.remove("C++");
        System.out.println(map.containsKey("C++")); // 输出：false
    }
}

3. 应用场景

• 缓存：Redis 底层哈希表结构；
• 数据去重 / 计数：统计字符串字符出现次数、数组中重复元素；
• 快速映射：用户 ID→用户信息、配置项 key→value。

三、二叉树 vs 哈希表（核心区别）

表格

总结

1. 二叉树：核心优势是有序性，适合需要排序、范围查找的场景（如 TreeMap 按 key 升序遍历），时间复杂度稳定在 O (logn)；
2. 哈希表：核心优势是极致的查询效率，适合快速查找 / 映射场景（如缓存、计数），但无序且依赖哈希函数设计；
3. 实际开发中，HashMap（哈希表）是高频选择（查询快），TreeMap（红黑树）仅在需要有序时使用。