从arrayList 表示形式中删除节点

Question

我有一个需要实现BST的delete方法的问题。 arrayList是按级别顺序遍历的，它包括所有节点，甚至包括null。例如

    toBSTArray = [20,3,2] -> BSTArray<String> = ["20","3","null","2","null","null","null"]

这是我到目前为止所得到的

        public void deleteFromStr(ArrayList<String> arr, String delVal){
        int i = 0;
        int leftChild, rightChild, parent;
        String node,leftChildStr,rightChildStr,parentString;
        while(!(arr.get(i).equals(delVal))){
            i++;
        }
        node = arr.get(i);
        leftChild =(2*i + 1);
        rightChild= (2 * i + 2);
        parent = (i - 1)/2;
        leftChildStr = arr.get(leftChild);
        rightChildStr = arr.get(rightChild);
        parentString = arr.get(parent);
        if(leftChildStr.equals("null") && rightChildStr.equals("null"))
            arr.remove(i);
    }

Answer 1

两件事：

1. 您具有直接索引的表示形式，您实际上不能从列表的中间删除节点，只能将它们设置为"null"（顺便说一下，我宁愿考虑使用null）
2. 在二叉搜索树中（无论其表示如何），节点删除取决于其子节点有多种情况

如果没有子代，则只需删除节点（null它）。这部分在您的代码中，只是不应为remove()：

if(leftChildStr.equals("null") && rightChildStr.equals("null"))
    arr.set(i,"null"); // instead of arr.remove(i);

如果一个孩子是null，则另一个孩子必须将其整个子树向上移动。我可以想象有一个递归的辅助函数：

void moveup(ArrayList<String> arr,int from,int to){
    if(from>=arr.size()){
        arr.set(to,"null");
        return;
    }
    String nodeString=arr.get(from);
    arr.set(to,nodeString);
    if(!nodeString.equals("null")){
        moveup(arr,from*2+1,to*2+1);
        moveup(arr,from*2+2,to*2+2);
    }
}

（是moveup，因为它不会检查to是否太大，并且不会尝试扩展列表）然后是案例（从上方继续if）：

else if(leftChildStr.equals("null"))
    moveup(arr,rightChild,i);
else if(rightChildStr.equals("null"))
    moveup(arr,leftChild,i);

还有一个最终的else用于处理左右两个孩子的存在。这是一个棘手的问题，实际上我不想考虑它，但是Wikipedia有一些想法：

删除具有两个子节点的节点：将要删除的节点称为D。请勿删除D。而是选择其有序前任节点或有序后继节点作为替换节点E（如图）。将E的用户值复制到D。[注2]如果E没有孩子，只需从其先前的父G中删除E。如果E有孩子，例如F，则它是正确的孩子。用E的父代中的F替换E。

加上插图：

首先，实现此想法将需要在树中进行实际导航，并且如现在所指出的那样，该问题在列表中显示了顺序搜索，而不是二进制搜索。