java - Bst树delete()方法不起作用

Question

我目前正在实现一个二叉搜索树，我想知道为什么我的delete()方法不起作用......我的 findMin() 方法确实有效，到目前为止我已经对其进行了测试。我输入一个键，它在三个中不存在，并且得到正确的异常，但是每当我输入一个存在的键时，它只是不会从三个中删除节点......这是到目前为止我的代码:

import java.util.NoSuchElementException;

public class Bst {

Node root;
Node head;
Node tail;


public Bst(){
    root = null;
}

public void insert (Node root, int key){
    Node newNode=new Node(key);

    if(root==null){
        root=newNode;
    }

    if(key<=root.getKey()){
        if (root.getLeft()!=null){
            insert(root.getLeft(), key);
        }
        else{
            root.setLeft(newNode);
        }
    }

    if (key>=root.getKey()){
        if (root.getRight()!=null){
            insert(root.getRight(),key);
        }

        else{
            root.setRight(newNode);
        }

    }


    }

public void printTree(Node root){
    if (root==null) return;
    printTree(root.getLeft());
    System.out.print(root.getKey() + " ");
    printTree(root.getRight());
}

public Node treeToCDLL(Node root){
    if (root == null){
        return null;
    }

    Node leftTree=treeToCDLL(root.getLeft());
    Node rightTree=treeToCDLL(root.getRight());


    if (leftTree == null){
        head=root;
    }

    else {
        head=leftTree;
        leftTree.getLeft().setRight(root);
        root.setLeft(leftTree.getLeft());
    }

    if (rightTree==null){
        head.setLeft(root);
        root.setRight(head);
        tail=root;
    }

    else{
        tail=rightTree.getLeft();
        head.setLeft(tail);
        tail.setRight(head);
        root.setRight(rightTree);
        rightTree.setLeft(root);
    }

    return head;
}

public boolean find(Node root, int key){
    Node current=root;

    while(current!=null){

        if(current.getKey()==key){
            return true;
        }
        else if(current.getKey()>key){
            current=current.getLeft();
        }

        else
            current=current.getRight();
        }
    return false;
}

public void printList(Node head){
    Node current = head;

    while(current!=null){
        System.out.print(current.getKey() + " ");
        current=current.getRight();
        if(current==head) break;
    }
}

public Node findMin(Node root){
    Node current=root;
    if(root==null) return null;
    else{
    if(current.getLeft()!=null){
        return findMin(current.getLeft());
    }
    }
    return current;

}

public void delete(Node root, int key){
    Node current=root;

    if(root==null){
        throw new NoSuchElementException("baum ist leer");
    }

    else{
        if(current.getKey()>key){
            delete(current.getLeft(), key);
        }

        else if(current.getKey()<key){
            delete(current.getRight(),key);
        }

        else{
            if(current.getLeft()==null && root.getRight()==null){
                current=null;
            }

            else if(current.getLeft()==null){
                Node tmp=current;
                current=current.getRight();
                tmp=null;
            }

            else if(current.getRight()==null){
                Node tmp=current;
                current=current.getLeft();
                tmp=null;
            }

            else {
                Node min=findMin(current.getRight());
                Node tmp=current;
                current=min;
                tmp=null;

            }
        }
    }
}
public static void main (String[]args){

    Bst bst=new Bst();

    Node root=new Node(4);
    bst.insert(root, 2);
    bst.insert(root, 10);
    bst.insert(root, 3);
    bst.insert(root, 5);
    bst.insert(root, 6);
    bst.insert(root, 0);

    bst.delete(root, 2);

    System.out.print("in-order traversal: ");
    bst.printTree(root);
    System.out.println();
    System.out.print("Der gesuchte Knoten : " + bst.find(root,7));
    System.out.println();
    System.out.print("der kleinste Knoten : " + bst.findMin(root));
    System.out.println();



    System.out.print("circular doubly linked list: ");
    Node head= bst.treeToCDLL(root);
    bst.printList(head);







}

}

节点类:

public class Node {

    private Node left;
    private Node right;
    private int key;

    public Node(int key){
        this.key=key;
        left = null;
        right = null;
    }

    public void setLeft(Node left){
        this.left=left;
    }

    public Node getLeft(){
        return left;
    }

    public void setRight(Node right){
        this.right=right;
    }

    public Node getRight(){
        return right;
    }

    public int getKey(){
        return key;
    }

}

如果有人能帮助我，我会很高兴...我一整天都在尝试寻找解决方案，但似乎我自己找不到它

Answer 1

在这里，通过执行 current=min 您不会更改树中的节点，而只是替换本地指针(当前)。要么通过 setter 重写该节点的值，要么在该节点的父节点上获取更新 getLeft。

 else {
     Node min=findMin(current.getRight());
     Node tmp=current;
     current=min;
     tmp=null;
 }