java - 删除功能不起作用(java)

Question

我们正在编写一个项目，其中使用链表在 BST 中添加和减去数字。但是，我们可以添加号码但无法删除它们。有人可以看看我们的删除功能，看看出了什么问题吗？

// 2016 Spring Data Structure BST Sample Code at MIU (For the project #2)
// You may add/modify the classes but should maintain the basic structure of the classes.
import java.util.*;
import java.util.*;
class Node { 
    int data; // data
    Node lc; //left child pointer
    Node rc; //right child pointer   
    Node(int data){     // constructor
        this.data=data;
        lc=null;
        rc=null;
    }
}
class BST {
    Node root;
    BST(){
        root=null;
    }
    void insert(int newData){ // This is not the full version
        Node newNode=new Node(newData);
        if(root==null) root=newNode; // root was null
        else { // root was not null, so find the place to attach the new node
            Node ptr=root; // Node pointer
            while(true){
                if(newNode.data==ptr.data) { 
                    System.out.println("The node already exist.");
                    break;
                }
                else if(newNode.data<ptr.data) {
                    if(ptr.lc!=null) ptr=ptr.lc;
                    else {
                        ptr.lc=newNode;
                        System.out.println(newNode.data+" was successfully inserted.");  
                        break;
                    }
                } 
                else if(newNode.data>ptr.data) {
                    if(ptr.rc!=null) ptr=ptr.rc;
                    else {
                        ptr.rc=newNode;
                        System.out.println(newNode.data+" was successfully inserted."); 
                        break;
                    }
                } 
            }
        }             
    }
    Node delete(Node root,int key){     // delete the nodes 
            if (root == null) return null;
            if (root.data > key) {
                root.lc = delete(root.lc, key);
                }
                else if (root.data < key) {
            root.rc = delete(root.rc, key);
        }
        return null;
    }
    boolean search(Node root,int key){ // if the search is successful return the Node or return null

        if(root==null){
            return false;
        }
        if(root.data== key) {
            return true;
        }
            if(root.data!= key){
                return false;
            }
        return true;
    }
    int number_nodes(Node n){ // the counting left child
        if(n == null)
        return 0;
        if(n.lc ==null && n.rc==null) 
        return 1;
        else
            return 1+number_nodes(n.lc);
    }
    int rnumber_nodes(Node n){ // the counting right child
        if(n == null)
        return 0;
        if(n.lc ==null && n.rc==null) 
        return 1;
        else
        return 1+number_nodes(n.rc);
    }
    void inorder(Node n){ // recursive inorder travelsal
        if(n==null) return;
        System.out.print("[");
        inorder(n.lc);
        System.out.print(n.data);
        inorder(n.rc);
        System.out.print("]");
    }
    void preorder(Node n){ // recursive preorder travelsal
        if(n==null) return;
        System.out.print("[");
        System.out.print(n.data);
        preorder(n.lc);        
        preorder(n.rc);
        System.out.print("]");
    }
    void postorder(Node n){ // recursive postorder travelsal
        if(n==null) return;
        System.out.print("[");      
        postorder(n.lc);        
        postorder(n.rc);
        System.out.print(n.data);
        System.out.print("]");
    }
}
public class BST_2015134 { // change the name into your IDs
    public static void main(String[] args) {
        BST bst=new BST();
        Scanner sScan=new Scanner(System.in); // menu
        Scanner iScan=new Scanner(System.in); // data
        while(true){
            System.out.print("\n(q)uit,(i)nsert,(d)elete,(s)earch,i(n)order,(p)reorder,p(o)storder,(h)ow many:");
            String uChoice=sScan.next();
            if(uChoice.equalsIgnoreCase("i")){
                System.out.print("Enter a number to insert:");
                int uData=iScan.nextInt();
                bst.insert(uData);
            }
            else if(uChoice.equalsIgnoreCase("d")){  // deletion
                System.out.print("enter the delete number");
                Scanner s=new Scanner(System.in); // to use new scanner
                int delete_num=s.nextInt(); // 
                bst.delete(bst.root,delete_num);
            }
            else if(uChoice.equalsIgnoreCase("s")){  // search
                System.out.print("enter the search number");
                Scanner s=new Scanner(System.in);
                int search_num=s.nextInt(); 
                    if(bst.search(bst.root,search_num)){
                        while(true){
                        System.out.println(" your number is found"); // to tell you your # is found or not found
                        break;
                        }
                    }
                    else{
                        System.out.println(" your number is not found");
                    }
            }
            else if(uChoice.equalsIgnoreCase("n")){  // in order
                bst.inorder(bst.root);
            }
            else if(uChoice.equalsIgnoreCase("p")){  // pre order
                bst.preorder(bst.root);
            }
            else if(uChoice.equalsIgnoreCase("o")){  // post order
                bst.postorder(bst.root);
            }
            else if(uChoice.equalsIgnoreCase("h")){  // how many
                int x,y;
                x=bst.number_nodes(bst.root);
                y=bst.rnumber_nodes(bst.root);
                int total=x+y;
                System.out.print(total);
            }
            if(uChoice.equalsIgnoreCase("q")) break; // quit
        }
    }
}

Answer 1

简单回顾一下您使用此函数所做的事情:

如果预计该键包含在左子树中，则通过递归从左子树中删除 if 。如果预计该键包含在右子树中，则通过递归从左子树中删除 if 。
到目前为止，一切都很好。但是，您每次都返回 null，因此您所做的所有工作实际上都丢失了。
您还需要处理节点的数据等于给定键的情况。在这种情况下，您需要以某种方式重组树。

只要您要删除的节点不是树的根，下面的代码就应该执行您想要的操作(您应该为此添加一个特殊情况)

Node delete(Node root,int key){     // delete the nodes 
    if (root == null) return null;
    if (root.data > key) {
        root.lc = delete(root.lc, key);
    }
    else if (root.data < key) {
        root.rc = delete(root.rc, key);
    }else{
        if(root.rc == null)
            return root.lc;
        if(root.lc == null)
            return root.rc;
        //if both the left and right child are effective, you need to restructure the tree
        int minData = findMinimum(root.rc);
        Node newNode = new Node(minData);
        newNode.lc = root.lc;
        newNode.rc = delete(root.rc, minData);
        return newNode;
    }
    return root;
}
private int findMinimum(Node root){
    if (root.lc == null)
        return root.data;
    else
        return findMinimum(root.lc);
}

请注意，从 BST 中删除节点并非易事。看看this链接以获取更多信息。

另请注意，这棵树的效率不会很高。平衡树会让我们好很多。