二叉树与哈希表从0到1实现指南：代码、逻辑与避坑技巧

二叉树：从结构定义到核心操作实现

要实现二叉树，第一步得明确“节点”这个基本单元——它是二叉树的“细胞”。无论是Java还是Python，节点的定义逻辑都一致：一个存储值的变量，加上左右两个子节点指针（或引用）。

1. 节点定义：Java vs Python

Java实现：

public class TreeNode {
    int val; // 节点值
    TreeNode left; // 左子节点
    TreeNode right; // 右子节点

    // 构造方法
    public TreeNode(int val) {
        this.val = val;
        this.left = null;
        this.right = null;
    }
}

Python实现：

class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

2. 核心操作：插入、遍历与删除

二叉树的操作中，插入是基础，遍历是高频需求，删除是难点——我们逐个拆解。

插入操作（以二叉搜索树为例）

二叉搜索树（BST）的插入规则是：左子树所有节点值小于根节点，右子树所有节点值大于根节点。插入逻辑可以用递归或迭代实现，递归更易理解：

Java递归插入：

public TreeNode insert(TreeNode root, int val) {
    // 如果根节点为空，直接创建新节点
    if (root == null) {
        return new TreeNode(val);
    }
    // 小于根节点，插入左子树
    if (val < root.val) {
        root.left = insert(root.left, val);
    }
    // 大于等于根节点，插入右子树
    else {
        root.right = insert(root.right, val);
    }
    return root;
}

遍历操作：递归与非递归实现

遍历是访问二叉树所有节点的方式，常见的有前序（根→左→右）、中序（左→根→右）、后序（左→右→根）。递归写法简单，但非递归写法更考察对栈的理解（面试常考）。

前序遍历：非递归实现（Java）：
用栈模拟递归过程，先压根节点，再压右子节点（因为栈是后进先出，要保证左子节点先处理）：

public List<Integer> preorderTraversal(TreeNode root) {
    List<Integer> res = new ArrayList<>();
    Stack<TreeNode> stack = new Stack<>();
    if (root != null) stack.push(root);

    while (!stack.isEmpty()) {
        TreeNode node = stack.pop();
        res.add(node.val); // 处理根节点
        // 先压右子节点，再压左子节点
        if (node.right != null) stack.push(node.right);
        if (node.left != null) stack.push(node.left);
    }
    return res;
}

删除操作：最容易踩坑的环节

删除节点分三种情况，处理逻辑需严谨：
1. 叶子节点：直接删除（无后顾之忧）；
2. 只有一个子节点：用子节点替换当前节点；
3. 有两个子节点：找右子树的最小节点（或左子树的最大节点）替换当前节点，再删除那个最小节点（保持BST有序性）。

Java删除实现：

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; // 左子树为空，返回右子树
        } else if (root.right == null) {
            return root.left; // 右子树为空，返回左子树
        }
        // 有两个子节点：找右子树最小节点
        TreeNode minNode = findMin(root.right);
        root.val = minNode.val; // 替换当前节点值
        root.right = deleteNode(root.right, minNode.val); // 删除最小节点
    }
    return root;
}

// 辅助方法：找树的最小节点（左子树最深处）
private TreeNode findMin(TreeNode node) {
    while (node.left != null) {
        node = node.left;
    }
    return node;
}

哈希表：哈希函数、冲突解决与完整逻辑

哈希表的核心是“键→索引”的映射（哈希函数），以及处理“多个键映射到同一索引”的冲突问题。我们以链地址法（最常用的冲突解决方式）为例实现哈希表。

1. 哈希表的结构设计

哈希表由“数组+链表”组成：数组存储链表头节点，每个链表存储冲突的键值对。

Java哈希表节点定义：

class HashNode<K, V> {
    K key;
    V value;
    HashNode<K, V> next; // 下一个节点（解决冲突）

    public HashNode(K key, V value) {
        this.key = key;
        this.value = value;
        this.next = null;
    }
}

2. 哈希函数：如何把键变成索引？

哈希函数的目标是“均匀分布”，减少冲突。常见的方法是：
– 取键的哈希码（hashCode()）；
– 对数组长度取模（保证索引在数组范围内）。

Java哈希函数实现：

private int hash(K key) {
    if (key == null) return 0;
    int hash = key.hashCode();
    // 用“与运算”代替取模（要求数组长度是2的幂，性能更高）
    return hash & (table.length - 1);
}

3. 核心操作：put、get、remove

put操作：插入或更新键值对

逻辑：
1. 计算键的索引；
2. 遍历链表，若键已存在则更新值；
3. 若键不存在，插入链表头部；
4. 检查负载因子（size/数组长度），超过阈值（通常0.75）则扩容（数组翻倍）。

Java put实现：

class HashMap<K, V> {
    private static final int DEFAULT_CAPACITY = 16; // 默认容量（2的幂）
    private static final double LOAD_FACTOR = 0.75; // 负载因子
    private HashNode<K, V>[] table;
    private int size;

    public HashMap() {
        table = new HashNode[DEFAULT_CAPACITY];
        size = 0;
    }

    public void put(K key, V value) {
        int index = hash(key);
        HashNode<K, V> node = table[index];

        // 遍历链表，更新已有键
        while (node != null) {
            if (node.key.equals(key)) {
                node.value = value;
                return;
            }
            node = node.next;
        }

        // 插入新节点到链表头部
        HashNode<K, V> newNode = new HashNode<>(key, value);
        newNode.next = table[index];
        table[index] = newNode;
        size++;

        // 检查扩容
        if (size > LOAD_FACTOR * table.length) {
            resize();
        }
    }

    // 扩容方法：数组翻倍，重新哈希所有节点
    private void resize() {
        HashNode<K, V>[] oldTable = table;
        int newCapacity = oldTable.length * 2;
        table = new HashNode[newCapacity];
        size = 0; // 重置size，重新插入

        for (HashNode<K, V> oldNode : oldTable) {
            while (oldNode != null) {
                put(oldNode.key, oldNode.value); // 重新哈希
                oldNode = oldNode.next;
            }
        }
    }
}

get操作：根据键查找值

逻辑：计算索引→遍历链表→返回对应值（无则返回null）。

Java get实现：

public V get(K key) {
    int index = hash(key);
    HashNode<K, V> node = table[index];

    while (node != null) {
        if (node.key.equals(key)) {
            return node.value;
        }
        node = node.next;
    }
    return null; // 键不存在
}

避坑指南：那些容易踩的实现陷阱

1. 二叉树：删除时忘记处理子节点

坑：删除有两个子节点的节点时，只替换了值，但没删除右子树的最小节点→导致树中存在重复值。
解决：必须递归删除右子树的最小节点（如deleteNode(root.right, minNode.val)）。

2. 哈希表：哈希函数导致的聚类问题

坑：用“取模”哈希时，数组长度不是质数→键的哈希码会集中在某些索引（比如长度为10，哈希码为1、11、21的键都会映射到索引1）。
解决：数组长度用质数，或用“与运算”（要求长度是2的幂，性能更好）。

3. 哈希表：扩容时没有重新哈希

坑：扩容后数组长度变化，旧的索引失效→导致get不到值。
解决：扩容时必须遍历所有旧节点，重新计算索引并插入新数组（如resize()方法中的put(oldNode.key, oldNode.value)）。

4. 二叉树：非递归遍历的栈操作顺序

坑：前序遍历压栈时先压左子节点→导致右子节点先处理（顺序错误）。
解决：先压右子节点，再压左子节点（栈是后进先出，左子节点后压先出）。

5. 哈希表：负载因子设置不合理

坑：负载因子过高（如1.0）→冲突增多，查询时间变长；过低（如0.1）→浪费内存。
解决：保持负载因子在0.7~0.8之间（行业默认值）。

最后：用代码验证你的实现

学完实现逻辑，最好的方法是写一个小例子测试：
– 二叉树：插入10、5、15、3、7，删除10→看是否得到正确的结构；
– 哈希表：put(“name”, “Alice”)、put(“age”, 25)、get(“name”)→验证是否返回”Alice”。

比如Python二叉树测试：

root = TreeNode(10)
root = insert(root, 5)
root = insert(root, 15)
root = insert(root, 3)
root = insert(root, 7)
root = deleteNode(root, 10)
# 遍历结果应为[7,5,3,15]（前序）
print(preorderTraversal(root))

哈希表测试：

HashMap<String, String> map = new HashMap<>();
map.put("name", "Alice");
map.put("age", "25");
System.out.println(map.get("name")); // 输出Alice
System.out.println(map.remove("age")); // 输出25
System.out.println(map.get("age")); // 输出null

原创文章，作者：，如若转载，请注明出处：https://zube.cn/archives/265

二叉树实现代码示例冲突解决哈希表实现数据结构实战