java二叉搜索树

Question

我有一个关于如何从节点（根）中删除子节点的问题？由于我无法调用remove，如果我将孩子设为空，该孩子的孩子会向上移动吗？就像，我会把它初始化为空吗？或者我会指着孩子的孩子？

Answer 1

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

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

Answer 2

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

如果您刚刚设置的子节点为null，你会失去对孩子的孩子的任何信息。

Answer 3

有一个标准的树类就知道了它的孩子，通常停留在一个数组或集合 - 二叉树的情况下，你只得到了两次直接孩子，所以一个固定大小的数组会工作。正因为如此，他们通常实行某种形式的“removeMe”方法的孩子呼吁摆脱孩子的那个列表中删除。

如上所述，这得到，如果你删除的孩子有孩子复杂。

Answer 4

Tim的答案似乎最好的。但是，是的，你会想这取决于它是什么样的孩子你删除的三件事情一做。如果你让孩子空，它的孩子不会移动，因为你已经失去了它们引用。相反，你要确定您的去除孩子的左或右儿童应被设置为指针指向你删除的孩子。在设置之前的节点指针（左或右）孩子（左或右）你去除该节点的，你不会有一个参考了该节点，所以世界上没有必要将它设置为空（你可以”牛逼访问它了。除非你写某种双向链接BST的，这就是在这种情况下，没有经典的BST）

Answer 5

此代码应该帮助你。

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));
}

Answer 6

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

给定一个树的“根”和节点的根删除或一些数据的“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;

}