0

我有一个关于如何从节点（根）中删除子节点的问题？由于我不能调用remove，如果我让孩子为空，那个孩子的孩子会向上移动吗？就像，我会把它初始化为空吗？还是我会指向孩子的孩子？

4

6 回答 6

2

在传统的二叉搜索树中，删除一个节点可能会产生不同的结果，具体取决于该节点有多少个子节点：

  • 可以简单地删除没有子节点的节点
  • 可以删除具有一个子节点的节点，并且该节点将被其唯一的子节点替换。无论孩子是左孩子还是右孩子，这都适用。
  • 有两个孩子的节点有一个稍微复杂一点的规则：你必须找到要移除的节点的有序后继或有序前驱，将当前节点的值替换为其后继或前驱的值，然后删除后继或前驱（根据这些规则）。
于 2009-10-31T19:49:47.890 回答
0

这是作业吗？这没什么错……我们只是想帮助人们学习而不是告诉他们答案。

如果您只是将子节点设置为 null，您将丢失有关子节点的任何信息。

于 2009-10-31T19:51:11.733 回答
0

蒂姆的回答似乎是最好的。但是，是的，您需要做三件事中的一件，具体取决于您要移除的孩子类型。如果你让一个孩子为空，它的孩子将不会向上移动，因为你已经失去了对它们的引用。相反，您需要确定要删除的子项的左子项还是右子项应设置为指向要删除的子项的指针。在将前一个节点指针（左或右）设置为要删除的节点的子节点（左或右）后，您将不再对该节点的引用，因此无需将其设置为 null（您可以不再访问它。除非您编写了某种双向链接的 BST，在这种情况下，这不是经典的 BST）

于 2009-10-31T23:20:04.590 回答
0

这段代码应该可以帮助你

public Node<T> getParentOf(Node<T> child){
    findParentOf(this.root, child);
    return temp;
}

private void findParentOf(Node<T> ROOT, Node<T> child){
    if(ROOT.hasLeft()){
        findParentOf(ROOT.left, child);
    }

    if(ROOT.left == child || root.right == child){
        temp = ROOT;
    }

    if(ROOT.hasRight()){
        findParentOf(ROOT.right, child);
    }
}


private void replaceNode(Node<T> original, Node<T> newNode){
    Node<T> tempParent = getParentOf(original);
    if(original == tempParent.left){
        tempParent.left = newNode;
    }else if(original == tempParent.right){
        tempParent.right = newNode;
    }
}

private void traverseChildrenAndAdd(Node<T> newParent, Node<T> oldParent){
    newParent.insert(oldParent.data);
    if(oldParent.hasLeft()){
        traverseChildrenAndAdd(newParent,oldParent.left);
    }



    if(oldParent.hasRight()){
        traverseChildrenAndAdd(newParent,oldParent.right);
    }
}
private void deleteNode(Node<T> ROOT, Node<T> d){
    if(d.data.compareTo(ROOT.data) < 0){
        deleteNode(ROOT.left, d);
    }else if(d.data.compareTo(ROOT.data) > 0){
        deleteNode(ROOT.right, d);
    }else if(d == this.root){
        if(this.root.hasLeft()){
            traverseChildrenAndAdd(root.left, root.right);
            root = root.left;
        }else if(root.hasRight()){
            root = root.right;
        }else{
            root = null;
        }
    }else{
        if(ROOT.hasLeft()&&ROOT.hasRight()){
            Node<T> successor = getMinNode(ROOT);
            replaceNode(successor, successor.right);
        }else if(ROOT.hasLeft() || ROOT.hasRight()){
            if(ROOT.hasLeft()){
                replaceNode(ROOT, ROOT.left);
            }else{
                replaceNode(ROOT, ROOT.right);
            }
        }else{
            replaceNode(ROOT, null);
        }
    }
}

public void remove(T data){
    deleteNode(this.root, new Node<T>(data));
}
于 2011-02-13T09:14:15.463 回答
0

一个标准的树类会知道它的孩子，通常卡在一个数组或集合中——在二叉树的情况下，你只有两个直接的孩子，所以一个固定大小的数组可以工作。正因为如此，他们通常实现某种“removeMe”方法，孩子调用该方法以从该孩子列表中删除。

如上所述，如果您要移除的孩子有孩子，这会变得复杂。

于 2009-10-31T20:33:04.903 回答
0

你可以做这样的事情（伪代码）：

给定树的根“root”和要删除的节点或一些数据“x”，请执行以下操作

 if x < root
      recurse to left child
 if x > root
      recurse to right child
 else //node found
      find the min item of the node right child //min item should be left most leaf node node
      replace the value of the node you want to delete with min nodes value
      now delete the min node
 return root;

代码：

delete(Node root, Object x){
    if(root == null){
        return null;
    }

    if(data < root.data){
        root = delete(root.left);
    }else if(root.data < data){
        root = delete(root.right);
    }else{
        if(root.left != null && root.right != null){
            Object tmp = findMin(root.right);
            root.data = tmp;
            root.right = delete(root.right, tmp);
        }else{
            return (root.left != null) ? root.left : root.right;    
        }
    }
return root;

}

于 2014-09-09T19:33:58.293 回答