java - 从 arrayList<String> 演示文稿中删除节点

Question

我有一个问题，我需要实现 BST 的删除方法。 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有一些想法:

Deleting a node with two children: call the node to be deleted D. Do not delete D. Instead, choose either its in-order predecessor node or its in-order successor node as replacement node E (s. figure). Copy the user values of E to D.[note 2] If E does not have a child simply remove E from its previous parent G. If E has a child, say F, it is a right child. Replace E with F at E's parent.

附上插图:

首先，实现这个想法需要在树中进行实际导航，正如评论指出的那样，问题显示了列表中的顺序搜索而不是二分搜索。