将值插入随机二叉搜索树时出现问题

Question

我想创建一个随机二叉搜索树，但我遇到一条错误消息。

这是我的代码的相关部分：

第 1 类（并不是很重要，但它是主要焦点的 RandomizedBST 类的一部分）：

class LargeDepositor {
    
    private int AFM;
    private String firstName;
    private String lastName;
    private double savings;
    private double taxedIncome;
    
    public LargeDepositor(int AFM, String firstName, String lastName, double savings, double taxedIncome) {
        this.AFM = AFM;
        this.firstName = firstName;
        this.lastName = lastName;
        this.savings = savings;
        this.taxedIncome = taxedIncome;
    }
    
    public LargeDepositor() {
        
    }
    
    int key() {
        return AFM;
    }
    
    public int getAFM() {
        return AFM;
    }
    
    public String getFirstName() {
        return firstName;
    }
    
    public String getLastName() {
        return lastName;
    }
    
    public double getSaving() {
        return savings;
    }
    
    public double getTaxedIncome() {
        return taxedIncome;
    }
    
    public void setAFM(int AFM) {
        this.AFM = AFM;
    }
    
    public void setFirstName(String firstName) {
        this.firstName = firstName;
    }
    
    public void setLastName(String lastName) {
        this.lastName = lastName;
    }
    
    public void setSaving(double savings) {
        this.savings = savings;
    }
    
    public void setTaxedIncome(double taxedIncome) {
        this.taxedIncome = taxedIncome;
    }
    
    public String toString() {
        return ("The AFM of this depositor is: " + getAFM() +
                "\nThe First Name of this depositor is: " + getFirstName() +
                "\nThe Last Name of this depositor is: " + getLastName() +
                "\nThe Total Amount of known deposits of this depositor in other countries is: " + getSaving() +
                "\nThe Total Declared Income in Greece of this depositor in the last 3 years is: " + getTaxedIncome());
    }

}

2类（插入部分）：

import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.util.List;
import java.util.Scanner;
import java.util.StringTokenizer;

public class RandomizedBST{
    
    private class TreeNode {
        
        LargeDepositor item;
        TreeNode left; // pointer to left subtree
        TreeNode right; // pointer to right subtree
        int N; //number of nodes in the subtree rooted at this TreeNode
        
        TreeNode parent;
        
        public TreeNode() {
            
        }
        
        public TreeNode(LargeDepositor item) {
            this.item = item;
        }
        
        public TreeNode(LargeDepositor item,TreeNode left, TreeNode right) {
            this.item = item;
            this.left = left;
            this.right = right;
        }
        
        public LargeDepositor getData() {
            return item;
        }
        
        public void setData(LargeDepositor item) {
            this.item = item;
        }
        
        public TreeNode getLeft() {
            return left;
        }
         
        public void setLeft(TreeNode left) {
            this.left = left;
        }
        
        public TreeNode getRight() {
            return right;
        }
        
        public void setRight(TreeNode right) {
            this.right = right;
        }
        
        public TreeNode getParent() {
            return parent;
        }
        
        public void setParent(TreeNode parent) {
            this.parent = parent;
        }
        
    }
    
    private TreeNode root;
    
    // Insert methods start here
    
    public void insert(LargeDepositor item) {
        if (searchByAFM(item.getAFM()) != null) {
            System.out.println("As you can see there is already a Large Depositor with the same AFM in the tree.");
            System.exit(0);
        } else {
            root = insertAsRoot(item, root);
        }
    }
    
    private TreeNode insertAsRoot(LargeDepositor item, TreeNode h) {
        if (h == null) {
            TreeNode node = new TreeNode(item);
            return node;
        } 
        if (Math.random()*(h.N+1) < 1.0) {
            h = insertT(item, h);
        }
            
        if (item.key() < h.item.key()) {
            h.setLeft(insertAsRoot(item, h.getLeft()));
        } else {
            h.setRight(insertAsRoot(item, h.getRight()));
        }
        h.N++;
        return h;
    }
    
    private TreeNode insertT(LargeDepositor item, TreeNode h) {
        if (item.key() < h.item.key()) {
            h.setLeft(insertT(item, h.getLeft())); //recursively, x becomes the root of h.l
            h = rotR(h);
            } //right rotation to bring it to the root
        else {
            h.setRight(insertT(item, h.getRight()));
            h = rotL(h); 
        }
        return h;
    }
    
    private TreeNode rotR(TreeNode h) {      //right rotation 
        TreeNode x = h.getLeft();
        h.setLeft(x.getRight()); 
        x.setRight(h); 
        return x;
    }
    
    private TreeNode rotL(TreeNode h) {      //left rotation
        TreeNode x = h.getRight();
        h.right = x.left;
        x.left = h;
        return x;
    }
    
    // Insert methods end here

// Search by AFM methods start here
    
    public LargeDepositor searchByAFM(int AFM) {
        return searchByAFMHelper(root, AFM);
        
    }
    
    private LargeDepositor searchByAFMHelper(TreeNode h, int AFM) {
        if (h == null) {
            System.out.println("There is no Depositor with the AFM number that you entered.");
            return null;  
        }

        if (AFM == h.item.key()) {
            return h.item;  // If the AFM number fits the root's key, the depositor is returned.
        } else if (AFM < h.item.key()) {
            return searchByAFMHelper(h.getLeft(), AFM);  // If the AFM number is smaller, we search the left subtree.
        } else {
            return searchByAFMHelper(h.getRight(), AFM);  //If the AFM number is greater, we search the right subtree.
        }
    }
    
    // Search by AFM methods end here

主课部分：

public static void main(String[] args) {
        
        Scanner in = new Scanner(System.in);
        
        System.out.println("Main!");
        
        RandomizedBST rBST = new RandomizedBST();
        rBST.root = null;
        
        boolean exitProgram = false;
        
        String answer;
        
        while (!exitProgram) {
            
            System.out.println("-------------------------------------------------------------------------------");
            System.out.println("1. Insert Depositor");
            System.out.println("2. Load File");
            System.out.println("3. Update Savings");
            System.out.println("4. Search by AFM");
            System.out.println("5. Search by Last Name");
            System.out.println("6. Remove Depositor");
            System.out.println("7. Get mean savings amount, based on registered depositors");
            System.out.println("8. Print the data for the k most suspected tax evasion large depositors");
            System.out.println("9. Print the data of all the depositors sorted in ascending order based on AFM");
            System.out.println("0. Exit program");
            System.out.println("-------------------------------------------------------------------------------");
            System.out.print("> ");
            answer = in.nextLine();
            
            if (answer.equals("1")) { // Insert (Depositor)
                
                System.out.println("--- Insert Depositor ---");
                
                LargeDepositor item;
                
                int AFM;
                String firstName;
                String lastName;
                double savings;
                double taxedIncome;
                
                System.out.println("Please enter the depositor's information as requested below.");
                System.out.print("AFM: ");
                AFM = in.nextInt();
                in.nextLine();
                System.out.print("First Name: ");
                firstName = in.nextLine();
                System.out.print("Last Name: ");
                lastName = in.nextLine();
                System.out.print("Savings (Total amount of known deposits in others Countries): ");
                savings = in.nextDouble();
                in.nextLine();
                System.out.print("Taxed Income (Total declared income in Greece in the last 3 years): ");
                taxedIncome = in.nextDouble();
                in.nextLine();
                
                item = new LargeDepositor(AFM, firstName, lastName, savings, taxedIncome);
                
                rBST.insert(item);

我可以在树中插入第一个节点（成为根节点），但是在尝试插入第二个节点后，会出现此消息：

如果有人能想到这个问题，请告诉我，我被困住了！

Answer 1

错误的直接原因是您的

insertT

函数执行递归而不检查基本情况，即当

h

为

null

时。在这种情况下，您应该实际创建节点并返回它。

    private TreeNode insertT(int item, TreeNode h) {
        if (h == null) { // Base case!
            return new TreeNode(item);  // Must create the node for the item
        }
        if (item.key() < h.item.key()) {
            h.setLeft(insertT(item, h.getLeft()));
            h = rotR(h);
        }
        else {
            h.setRight(insertT(item, h.getRight()));
            h = rotL(h); 
        }
        return h;
    }

与错误无关，但

insertAsRoot

似乎随机选择使用

insertT

算法插入新节点，以便新节点最终位于根，OR插入节点在其他地方，使用

insertAsRoot

的递归调用。但你的代码可能会同时做两者，而这并不是有意的。

所以将第二个选项放在

else

块中：

        if (Math.random()*(h.N+1) < 1.0) {
            h = insertT(item, h);
        } else if (item.key() < h.item.key()) {
//        ^^^^
            h.setLeft(insertAsRoot(item, h.getLeft()));
        } else {
            h.setRight(insertAsRoot(item, h.getRight()));
        }