我无法从二进制搜索树中删除节点。我想我还没有理解 Java 对象如何工作的基础知识

Question

节点Class:-

public class Node {
    int data;
    Node left;
    Node right;

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

BST Class:-

public class BST {
    Node root;

    BST(){
        root = null;
    }

    void insertNode(int data){
        root = insertRecursive(data, root);
    }

    private Node insertRecursive(int data , Node root){
        if(root == null) return new Node(data);
        if(data < root.data) root.left = insertRecursive(data,root.left);
        if(data > root.data) root.right = insertRecursive(data,root.right);
        return root;
    }

    Node find(int data,Node root){
        return findRecursive(data,root);
    }

    private Node findRecursive(int data, Node root){
        if(data == root.data) return root;
        if(data < root.data) return findRecursive(data,root.left);
        if(data > root.data) return findRecursive(data, root.right);
        else return null;
    }

    Node delete(int data, Node root){
        Node toBeDeleted = find(data,root); 
        Node parent = parent(data,root);
        if(toBeDeleted.left == null && toBeDeleted.right == null) {
            toBeDeleted = null;
            return root;
        }

        else if(toBeDeleted.left == null || toBeDeleted.right == null){
            if(toBeDeleted.left == null){
                if(parent.left == toBeDeleted) parent.left = toBeDeleted.right;
                if(parent.right == toBeDeleted) parent.right = toBeDeleted.right;
            }
            else if(toBeDeleted.right == null ){
                    if(parent.left == toBeDeleted) parent.left = toBeDeleted.left;
                    if(parent.right == toBeDeleted) parent.right = toBeDeleted.left;
            }
            return root;
        }

        else {
            Node min = findMin(toBeDeleted.right);
            toBeDeleted = min;
            delete(min.data,min);
            return root;
        }
    }

    Node parent(int dataToBeFound,Node root){
        return parentHelper(find(dataToBeFound,root),root);
    }

    private Node parentHelper(Node nodeToBeFound, Node root){
        if(root == null ) return null;
        else {
            if(root.left == nodeToBeFound || root.right == nodeToBeFound) return root;
            else{
                if(nodeToBeFound.data < root.data) return parentHelper(nodeToBeFound,root.left);
                else return parentHelper(nodeToBeFound,root.right);
            }
        }
    }

    void levelOrder(Node root){
        Queue<Node> q = new LinkedList<>();
        q.add(root);
        while(!q.isEmpty()){
            Node node = q.poll();
            System.out.println(node.data);
            if(node.left != null ) q.add(node.left);
            if(node.right != null ) q.add(node.right);
        }
    }

    Node findMin(Node node){
        if(node.left == null) {
            return node;
        }
        else{
            return findMin(node.left);
        }
    }
}

主要功能：-

public class Runner {

    public static void main(String[] args) {
        BST bst = new BST();
        bst.insertNode(15);
        bst.insertNode(10);
        bst.insertNode(9);
        bst.insertNode(11);
        bst.insertNode(20);
        bst.insertNode(18);
        bst.insertNode(25);
        bst.levelOrder(bst.root);
        System.out.println("After deletion");
        bst.levelOrder(bst.delete(9,bst.root));
    }
}

删除后，我得到了与输出相同的 BST。我知道我缺少一些关于对象如何工作或如何引用对象的基础知识。我的问题是我不确定如何解决这个问题。我必须做什么？我应该创建一个新对象吗？或者是什么？我不知道。

Answer 1

我认为这部分有问题：

if(toBeDeleted.left == null && toBeDeleted.right == null) {
        toBeDeleted = null;
        return root;
    }

因为你对 parent 什么都不做。

我无法从二进制搜索树中删除节点。我想我还没有理解 Java 对象如何工作的基础知识

I am having trouble deleting a node from Binary search tree. I guess I have not understood the fundamentals of how Java objects work

java

object

binary-search-tree

data-structures