Dart二叉树删除方法失效问题求助

问题根源 #

你的delete方法核心问题是只修改了局部变量的引用，没改动树的实际结构：

• find(targetData)返回的是目标节点的引用副本，你修改target这个局部变量的指向（比如target = null），不会影响父节点中存储的子节点引用，所以树看起来没变化。
• 双孩子节点的处理逻辑也有问题，复制节点的方式无法正确替换原节点，递归删除最小节点时同样因为上述局部变量问题无效。

修复思路 #

要修改树的结构，必须从根节点开始递归处理，让每个递归函数返回修改后的子树根节点，这样上层节点才能更新自己的left/right指针。同时处理三种删除场景：

• 叶子节点：直接返回null，让父节点的对应指针变为null
• 单孩子节点：返回该孩子节点，替换原节点
• 双孩子节点：找到右子树的最小节点，用它的值替换原节点的值，然后递归删除右子树中的那个最小节点

修正后的代码 #

首先，实现递归删除的核心方法（作为BinarySearchTree类的方法）：

BinarySearchTreeNode? delete(BinarySearchTreeNode? node, int targetData) {
  if (node == null) return null;

  // 递归查找目标节点
  if (targetData < node.nodeData) {
    node.left = delete(node.left, targetData);
    return node;
  } else if (targetData > node.nodeData) {
    node.right = delete(node.right, targetData);
    return node;
  }

  // 找到目标节点，开始处理删除逻辑
  // 情况1：叶子节点，直接返回null
  if (node.left == null && node.right == null) {
    return null;
  }

  // 情况2：只有一个子节点，返回该子节点替换原节点
  if (node.left == null) {
    return node.right;
  } else if (node.right == null) {
    return node.left;
  }

  // 情况3：有两个子节点，找右子树的最小节点
  BinarySearchTreeNode minNode = findMin(node.right!);
  // 用最小节点的值替换当前节点的值
  node.nodeData = minNode.nodeData;
  // 递归删除右子树中的最小节点
  node.right = delete(node.right, minNode.nodeData);
  return node;
}

// 辅助函数：查找子树的最小节点
BinarySearchTreeNode findMin(BinarySearchTreeNode node) {
  while (node.left != null) {
    node = node.left!;
  }
  return node;
}

再封装一个对外调用的方法：

void remove(int targetData) {
  root = delete(root, targetData);
}

代码解释 #

• 递归遍历树时，上层节点会接收下层返回的修改后的子树根节点，更新自己的left/right指针，这才真正改变了树的结构。
• 双孩子节点的处理采用标准方案：不创建新节点，直接替换值再删除冗余节点，逻辑更简洁可靠。
• findMin辅助函数负责定位右子树的最小节点，保证二叉搜索树的性质不变。

内容的提问来源于stack exchange，提问作者saadman