二叉树删除与集合框架

二叉树删除（三种情况）与集合框架：List / Set / Map

本文给出删除操作的完整可运行代码（叶子、单子树、双子树三种情况，含后继替换），并系统梳理 Java 集合框架三大体系 List / Set / Map 的实现类、底层结构与去重原理。配套代码在 demos/bst-collections，已真实编译运行。

一、删除的整体思路

删除前先定位目标节点与它的父节点（parent）。用游标 cur 从 root 出发，沿「左小右大」比较，直到 cur.value == v；同时用 parent 记录 cur 的上一个节点。若 cur == null 说明目标不存在，直接结束。

找到后按子树数量分三种情况处理，其中「根节点无父节点」要单独放进分支讨论，不能漏。

二、情况一 & 情况二：叶子与单子树（合并处理）

叶子节点是单子树的特例（子树为 null）。核心操作都是「调整父节点的指针，让它跳过被删节点」：

• 有父节点：判断目标是父节点的左孩子还是右孩子，把对应的 parent.left 或 parent.right 指向被删节点的唯一子节点（叶子时该子节点为 null，即置空）。

• 无父节点（删的是根）：让 root 直接指向它的唯一子节点；若整棵树只有一个节点，则 root = null。

// 情况一 & 情况二：最多一个子树
Node child = (cur.left != null) ? cur.left : cur.right;
if (parent == null) {
   root = child;                  // 删的是根（含整棵树唯一节点）
} else if (parent.left == cur) {
   parent.left = child;          // 目标是左孩子
} else {
   parent.right = child;         // 目标是右孩子
}

注意：判断「目标是不是父节点的左孩子」时，必须先用短路与 && 确认左子节点非空，再访问其 value，否则对 null 取属性会空指针异常。短路与的特性是：左边为 false 右边直接跳过；短路或 || 是左边为 true 右边跳过。把安全的非空判断放前面，既能提效又能避免 NPE。

三、情况三：两个子树（后继替换）

被删节点左右都不为空时，不能简单丢弃某一侧子树，否则会破坏「左小右大」。做法是找一个树中已有的节点值来替代：

• 用右子树的最小值（直接后继 successor）：从右子树根出发，一路向左走到 left == null；

• 或对称地用左子树的最大值（直接前驱 predecessor）：从左子树根出发，一路向右。

这里实现「右子树最小值」。

// 情况三：左右子树都不为空
if (cur.left != null && cur.right != null) {
   Node succParent = cur;
   Node succ = cur.right;
   while (succ.left != null) {        // 一路向左找右子树最小值
       succParent = succ;
       succ = succ.left;
  }
   cur.value = succ.value;            // 用后继值覆盖当前节点值
   // 删除后继（succ 一定没有左子树）
   if (succParent == cur) {
       succParent.right = succ.right; // 后继就是右孩子本身
  } else {
       succParent.left = succ.right;
  }
   return true;
}

为什么不会死循环：被选中的替换值一定是「极端值」——右子树最小值必是最左侧节点，它自身没有左子节点，所以删除它时只会走到「单子树/叶子」分支，递归或迭代立即终止。因为右子树最小值来自右子树，它必然大于原左子树所有节点；它又是右子树中最小的，所以也小于右子树其余节点，替换后依然维持「左小右大」。

补充：删除前务必先记录后继的值、再删除后继、最后覆盖原节点，顺序反了会导致数据不一致。删完可用层序遍历验证结构是否正常。

四、删除三种情况实测

依然是主树 {10,5,1,15,12,30}，四种删除逐一演示：

============ 二、删除情况一：叶子节点 ============
删除叶子 30 前，层序=10 5 15 1 12 30
删除叶子 30 后，层序=10 5 15 1 12
中序(仍为有序): 1 5 10 12 15
​
============ 三、删除情况二：仅一个子树 ============
删除单子树节点 5 前，层序=10 5 15 1 12 30
删除 5 后，层序=10 1 15 12 30（10 的左孩子变为 1）
中序(仍为有序): 1 10 12 15 30
​
============ 四、删除情况三：两个子树（后继替换） ============
删除双子树节点 15 前，层序=10 5 15 1 12 30
删除 15 后，层序=10 5 30 1 12（15 被右子树最小值 30 替代，原左孩子 12 保留为其左子树）
中序(仍为有序): 1 5 10 12 30
​
============ 五、删除根节点（双子树） ============
删除根 10 前，层序=10 5 15 1 12 30
删除根 10 后，层序=12 5 15 1 30（根变为右子树最小值 12）
中序(仍为有序): 1 5 12 15 30
​
============ 六、删除整棵树唯一节点（根也是叶子） ============
删除前，层序=7
删除后，层序=「」（root 置空，不报错）
​
============ 七、删除不存在的节点 ============
删除不存在的 99，返回=false，树不变，层序=10 5 15 1 12 30

观察结论：

• 删叶子 30：父节点 15 的 right 置空，子树不丢；

• 删单子树 5：父节点 10 的 left 直接接到 5 的唯一孩子 1；

• 删双子树 15：右子树最小值是 30，用 30 覆盖 15，原左孩子 12 保留为 30 的左子树（12 < 30，性质成立）；

• 删根 10：根变为右子树最小值 12，整棵树依旧有序；

• 删唯一节点 7：root 置空，不抛异常；删不存在的 99：返回 false，树不变。

• 每次删除后中序遍历始终是升序，证明 BST 性质未被破坏。

五、集合框架总览：List / Map / Set

数组和链表是线性结构，删除简单；但日常开发直接用 Java 提供的集合类更高效。集合体系分两大支：

• Collection：存「数据本身」，典型接口 List、Set、Queue；

• Map：存「键值对（key-value）」。

集合封装了底层结构（数组或链表），我们只需调现成方法，不必自己造轮子——但理解底层才能选对结构。注意：集合长度可变，且只能存引用类型（如 Integer 而非 int）；所谓「有序/无序」指输入输出顺序是否一致，不是指数值大小排序。

六、List：有序、可重复

实现类与底层：

List<String> arr = new ArrayList<>();
arr.add("A"); arr.add("B"); arr.add("B");   // 可重复
arr.add(1, "X");                            // 指定下标插入
System.out.println(arr);                    // [A, X, B, B]
​
LinkedList<String> link = new LinkedList<>();
link.add("A"); link.add("B");
link.addFirst("H"); link.addLast("T");      // 头插、尾插
link.removeFirst();                          // 头删

ArrayList 底层是数组，查询快、增删慢，和原生数组特性一致，只是 Java 帮我们封装了「判容量→不够就扩容→有空间就插入」；LinkedList 底层是双向链表，增删快、查询慢。刷题按需求选：要快速查找用 ArrayList，要频繁插入删除用 LinkedList。

七、Set：无序、不可重复

Set<String> hashSet = new HashSet<>();
hashSet.add("B"); hashSet.add("A"); hashSet.add("C"); hashSet.add("A"); // 重复丢弃
System.out.println(hashSet);             // [A, B, C]（顺序≠插入顺序）
​
Set<String> treeSet = new TreeSet<>();
treeSet.add("B"); treeSet.add("A"); treeSet.add("C"); treeSet.add("A");
System.out.println(treeSet);             // [A, B, C]（自动升序）

八、Map：键值对，键不可重复

HashMap 的底层本质是「数组套链表」：外层数组每个槽位挂一条链表（JDK 8 后链表过长自动转红黑树）。数据存放位置由键的哈希值决定，因此存取顺序不可控——插入 17 再插 65，遍历时可能 57 先出来。它最实用的特性是自动去重：把数据往里塞，相同键只会留一份。

Map<String, Integer> hashMap = new HashMap<>();
hashMap.put("Tom", 18);
hashMap.put("Lucy", 20);
hashMap.put("Tom", 21);                  // 同键，后值覆盖前值
System.out.println(hashMap);             // {Tom=21, Lucy=20}
System.out.println(hashMap.get("Tom"));  // 21
​
Map<String, Integer> treeMap = new TreeMap<>();
treeMap.put("Tom", 18); treeMap.put("Lucy", 20); treeMap.put("Ann", 16);
System.out.println(treeMap);             // {Ann=16, Lucy=20, Tom=18}（按键升序）

九、去重原理：equals + hashCode

HashSet/HashMap 去重不是「比较内容」这么简单，而是两步：

所以一个自定义类要能正确去重，必须同时重写 equals 和 hashCode。只重写一个会出 bug。

// 未重写 equals/hashCode：两个内容相同的对象也算不同
Set<Student> bad = new HashSet<>();
bad.add(new Student("001", "张三"));
bad.add(new Student("001", "张三"));
System.out.println(bad.size());          // 2（去重失败）
​
// 按 id 重写后：内容相同视为同一元素
Set<GoodStudent> good = new HashSet<>();
good.add(new GoodStudent("001", "张三"));
good.add(new GoodStudent("001", "张三"));
System.out.println(good.size());         // 1（去重成功）

实测输出：

============ 四、去重原理：equals + hashCode ============
未重写 equals/hashCode，HashSet 元素数=2（内容相同仍算两个，去重失败）
重写 equals/hashCode(按 id)，HashSet 元素数=1（去重成功）
HashSet/HashMap 先算 hashCode 定位桶，再用 equals 在桶内比对。

十、动手建议

封装数据结构本身不难，但实战直接调 Java 标准集合类即可，重点是把 add/get/remove/put/isEmpty/clear 等常用方法练熟，按「List → Map → Set」的顺序逐个掌握。刷题时 HashMap 去重、TreeSet 排序、ArrayList 随机访问都是高频用法。链表、哈希表（数组+链表）、数组遍历删除、BST 处理，是力扣高频基本功，建议把课堂代码都亲手写一遍。

附：关键命令 / 注解 / 关键字速查

附：本文实测代码

工程 csdn-blog/demos/bst-collections/：

• BST.java：含 delete（三种情况 + 后继替换）、search、四种遍历；

• BSTTest.java：二~七段为删除实测；

• CollectionsDemo.java：一~四段为 List/Set/Map 与去重实测。

export PATH="/usr/bin:/bin:/c/Windows/System32:$PATH"
cd csdn-blog/demos/bst-collections
javac -encoding UTF-8 -d out src/cn/ts/ds/*.java
java -Dfile.encoding=UTF-8 -cp out cn.ts.ds.BSTTest
java -Dfile.encoding=UTF-8 -cp out cn.ts.ds.CollectionsDemo