二叉树 通过合并递归实现删除

Question

我已经通过合并实现了删除的迭代版本，但我正在努力递归实现。

这是我的迭代版本：

public void deleteByMerging(T el) {
BSTNode<T> tmp, node, p = root, prev = null;
while (p != null && !p.el.equals(el)) {  
prev = p;                           
if (el.compareTo(p.el) < 0)
p = p.right;
else p = p.left;
}
node = p;
if (p != null && p.el.equals(el)) {
if (node.right == null) 
node = node.left;  
else if (node.left == null) 
node = node.right; 
else {                  
tmp = node.left;   
while (tmp.right != null) 
tmp = tmp.right;      
tmp.right =        
node.right;    
node = node.left;  
}
if (p == root)
root = node;
else if (prev.left == p)
prev.left = node;
else prev.right = node; // 5.
}
else if (root != null)
System.out.println("el " + el + " is not in the tree");
else System.out.println("the tree is empty");
}

现在我需要以这种方式实现递归函数：

public void delete(T info) {
root = delete(root, info);
}
public TreeNode<T> delete(TreeNode<T> node, T info) 
{
}

我对递归很陌生，我不知道从哪里开始。

Answer 1

("你的"迭代版本，你当然是指亚当·德罗兹德克的。

这应该有效：

public void delete(T info) {
root = delete (root.info);
}
public TreeNode<T> delete(TreeNode<T> node, T info) {
// if this node is null, we have reached the end of the tree
// so the node is not in the tree.
if (node == null) {
return node; // or handle as required
// if this is not the node to delete;
// recursively call this on the node's correct child
else if (info.compareTo(node.info) <0) {
node.left = delete(node.left, info);
return node;
} else {
node.right = delete(node.right, info);
return node;
}
// if this is the node to delete:
else if (node.info.equals(info)) {
// to delete it, we must return a sub-tree without it.
if (node.left == null) 
// this node is a leaf node, or
// node.right contains only child.
// either way, return node.right
return node.right;
if (node.right == null) 
// node.left contains only child
return node.left;
// else node has 2 children, so delete by merging:
// first, find its direct predecessor:
TreeNode<T> tmp = node.left;
while (tmp.right != null)
tmp = tmp.right;
// then append the node's right sub-tree
// to its direct predecessor:
tmp.right = node.right;
// lastly, replace the node by its left sub-tree:
return node.left;
}
}

首先，我们检查node是否为空。如果是，这意味着我们要删除的元素不在树中，因为我们已经遍历了，直到我们用完了它可能存在的所有节点。

接下来，我们检查元素是否大于或大于当前节点中的元素。如果是，我们需要继续遍历树，根据元素的比较方式向左或向右移动。请注意，在递归步骤中，我们将删除操作的结果分配给node的一个子项。我们从第一个函数中得到了这个提示，其中root被分配了root上的删除操作的结果。这将递归遍历树，直到node引用要删除的节点。我们也在这里返回node，这样如果没有发生任何更改， 对node.right = delete(node.right, info)的调用 ，例如，不会更改当前节点。

当我们找到节点时，可能有 4 种情况：节点可以是叶节点(没有子节点)，也可以有 1 个左子节点或 1 个右子节点，或者它可以有 2 个子节点。前 3 种情况由这些行覆盖

if (node.left == null)
return node.right;
if (node.right == null)
return node.left;

请注意，如果node没有子节点，则第一个if检查将为 true，因此将返回node的右子项(为 null)，删除节点。

为什么返回 null 会删除节点？因为，在上面讨论的遍历步骤中，我们将删除操作的结果分配给node的子项。请注意，上一个递归步骤中的node是此步骤中node的父节点，因为 delete 是在该节点的子节点上递归调用的。因此，在此处返回 null 将导致上一个调用将 null 分配给父项的子项，从而删除子项。基本上，每当我们返回除node以外的任何内容时，我们都会用我们在树中返回的任何内容替换当前节点。

在第四种情况下，我们需要通过合并进行简单的删除。您可以通过将node的右侧子树附加到其左侧子树的最右侧节点来执行此操作。首先，我们在左子树中找到最右边的节点，它是node的直接前身：

TreeNode<T> tmp = node.left;
while (tmp.right != null)
tmp = tmp.right;

所以tmp现在是node的直接前身。接下来，我们将node的右子树锁定在tmp上：

tmp.right = node.right;

最后，为了用它的左子树替换node，我们只需返回node.left，因为这会将node替换为node.left作为上一个递归调用中node父级的子级。

如果我的解释让你感到困惑，你可以试试这个。用纸上的图片解释要容易得多，这就是为什么你应该在实践课程中问我(是的，我设置了这个练习)而不是在SO:)希望你在截止日期之前弄清楚！