java - 使用字符串并在添加节点时遇到问题的二叉树

Question

我需要为我的 Java 数据结构类创建一个二叉树。我还很新，所以请原谅任何新手错误。我的 Btree 需要包含 String 类型的节点。我的问题是我可以添加一个名字，但是当我去添加第二个名字时，我的程序崩溃了并且出现了以下错误。

Exception in thread "main" java.lang.StackOverflowError
at java.lang.Character.toUpperCase(Unknown Source)
at java.lang.Character.toUpperCase(Unknown Source)
at java.lang.String$CaseInsensitiveComparator.compare(Unknown Source)
at java.lang.String$CaseInsensitiveComparator.compare(Unknown Source)
at java.lang.String.compareToIgnoreCase(Unknown Source)

这是我的代码:

BTNode

public class BTNode {

private String word;
private BTNode rPoint, lPoint;

public BTNode(String pWord){
    word = pWord;
    rPoint = null;
    lPoint = null;
}

public void setWord(String pWord){
    word = pWord;
}

public String getWord(){
    return word;
}

public void setRight(BTNode pRight){
    rPoint = pRight;
}

public BTNode getRight(){
    return rPoint;
}

public void setLeft(BTNode pLeft){
    lPoint = pLeft;
}

public BTNode getLeft(){
    return lPoint;
    }
}

B树

public class BTree {

private BTNode root;

    public void setRoot(BTNode pRoot){
        root = pRoot;
    }

    public BTNode getRoot(){
        return root;
    }

    public BTNode addOne(BTNode pRoot, String pName){
        if(pRoot == null){
            BTNode temp = new BTNode(pName);
            pRoot = temp;
            temp.setWord(pName);
        }else if(pName.compareToIgnoreCase(pRoot.getWord()) > 0){
            pRoot.setLeft(addOne(pRoot, pName));
        }else if(pName.compareToIgnoreCase(root.getWord()) < 0){
            pRoot.setRight(addOne(pRoot, pName));
        }
        return pRoot;
    }

    public void displayAll(BTNode current){
        if(current != null){
            displayAll(current.getLeft());
            System.out.println(current.getWord());
            displayAll(current.getRight());
        }
    }

    public BTNode BTSearch(BTNode pRoot, String pName){
        BTNode found = null;
        if(pRoot == null){
            found = null;
        }else{
            if(pName.equalsIgnoreCase(pRoot.getWord())){
                found = pRoot;
            }
            else if(pName.compareToIgnoreCase(root.getWord()) < 0){
                found = BTSearch(root.getLeft(), pName);
            }else{
                found = BTSearch(root.getRight(), pName);
            }
        }return found;
    }
}

BTreeUser

import java.util.Scanner;

public class BTreeUser {

public static void main(String []args){

    int select = 0;
    BTree tree = new BTree();

    do{
        dispMenu();
        select = getSelection();
        proChoice(select, tree);
    }while(select != 0);

}


    public static void dispMenu(){
        System.out.println("\n|*******************************|");
        System.out.println("|-------------------------------|");
        System.out.println("|************Welcome************|");
        System.out.println("|                               |");
        System.out.println("|  Press [1] to add an entry    |");
        System.out.println("|                               |");
        System.out.println("|  Press [2]|to search          |");
        System.out.println("|                               |");
        System.out.println("|  Press [3] to display all     |");
        System.out.println("|                               |");
        System.out.println("|  Press [0] to exit            |");
        System.out.println("|                               |");
        System.out.println("|Make selection and press[ENTER]|");
        System.out.println("|-------------------------------|");
        System.out.println("|*******************************|\n");
    }

    public static int getSelection(){
        Scanner input = new Scanner(System.in);
        int selection = input.nextInt();
        return selection;
    }

    public static String inputWord(int select){
        Scanner input = new Scanner(System.in);
        String lName = null;
        if(select == 1){
        System.out.println("Please input word now: ");
        lName = input.nextLine();
    }else if(select == 2){
        System.out.println("Please input word to search for now: ");
        lName = input.nextLine();

        }
        return lName;
    }

    public static  void proChoice(int select, BTree tree){
        String pName;
        switch(select){
        case 1: pName = inputWord(select);
                tree.setRoot(tree.addOne(tree.getRoot(), pName));
                break;
        case 2: pName = inputWord(select);
                tree.BTSearch(tree.getRoot(), pName);
                break;
        case 3: tree.displayAll(tree.getRoot());
                break;
        case 0: System.out.println("Thank you, come again...");
                break;
        }

    }
}

我知道错误发生在我的 addOne 方法是 BTree。我不确定我是否正确使用了 compareToIgnoreCase。请就如何解决此问题或我需要进行的任何更改提供任何帮助或建议，我们将不胜感激。

Answer 1

该方法使用接收到的完全相同的参数调用自身:

 pRoot.setLeft(addOne(pRoot, pName));

因为输入没有任何变化，所以没有任何变化，递归是无限的。

修复:

pRoot.setLeft(addOne(pRoot.getLeft(), pName));

右分支也是如此。