Бинарное дерево поиска (BST) метод поиска строки - PullRequest
Новая
       9

Бинарное дерево поиска (BST) метод поиска строки

1 голос
/ 17 июня 2019

Я создал BST, в котором есть элементы (код страны (строка), код индикатора (строка), имя индикатора (строка) и ArrayList of Years (int) и значения (строка)).

Я пытаюсь выяснить, как предложить пользователю выполнить поиск, введя код индикатора, а затем год, в котором выходным значением будет значение.

было бы очень полезно, если бы вы могли показать, как кодировать метод поиска, потому что я все перепробовал.

Я пробовал это в классе BST.но это не правильно (?) 

public void search(Indicator indicator, String searchTerm){ 

    String str = (String)indicator.getICode();
    int n1 = str.compareTo(searchTerm);
    int n2 = searchTerm.compareTo(str); 

    if (str == null || str.equalsIgnoreCase(searchTerm)){
        return str; 
    }

    if (n1 > n2){
        return search(indicator, searchTerm); 
    }

    else if (n1 < n2){
        return search(indicator, searchTerm);
    }
}

это мой класс приложения: 

public class BigDataBST{
    public static void main (String [] Args) throws IOException {
        try{
            BST bigdata = new BST();
            MyData d1;

            File inFile = new File ("Indicator.txt");
            FileReader fr = new FileReader (inFile);
            BufferedReader br = new BufferedReader(fr);
            String str = br.readLine();

            while(str != null ){
                StringTokenizer st = new StringTokenizer(str,";");
                ArrayList <MyData> data = new ArrayList();  

                String cCode = st.nextToken();
                String iName = st.nextToken();
                String iCode = st.nextToken();

                for (int j = 0; j < 59; j++){ 
                        String v = st.nextToken();
                        int year = 1960 + j;

                        d1 = new MyData (year,v);
                        data.add(d1);
                }
                Indicator idct = new Indicator (cCode,iName,iCode,data);
                bigdata.insertNode(idct);

                str = br.readLine();
            }

класс TreeNode: 

    TreeNode left;
    TreeNode right;
    Indicator idct;

    public TreeNode(Indicator id){
        left = right = null;
        idct = id;
    }

класс индикатора: 

    private String cCode;   //country code
    private String iName;   //indicator Name;
    private String iCode;       //indicator code;
    public ArrayList <MyData> DataList;

    public Indicator(){
        cCode = null;
        iName = null;
        iCode = null;
        DataList = null;
    }

    public Indicator(String cCode, String iName, String iCode,ArrayList <MyData> DataList){
        this.cCode = cCode; 
        this.iName = iName;
        this.iCode = iCode;
        this.DataList = DataList;
    }

    //setter & getter method for attributes iCode,iName and cCode
    //toString method

Класс MyData: 

    private int year;
    private String value;

    public MyData(){
        year = 0;
        value = null;
    }

    public MyData(int year, String value){
        this.year = year;
        this.value = value;
    }

    //setter & getter method for attributes year and value
    //toString method

пример индикатора.txt:
(слева: cCode; iName; iCode; значения)
MYS;Занятость в промышленности (% от общей занятости) (смоделированная оценка МОТ);SL.IND.EMPL.ZS;

29,08600044; 28,56900024; 28,36300087; 28,02300072; 27,51600075; 27,48699951; 27,39800072; 27,30500031

1 Ответ

1 голос
/ 17 июня 2019

Я думаю, вы не знаете, как искать в Binary Search Tree. Вы можете сделать это, перейдя на каждый узел и используя для этого рекурсию.

Но в вашем search() вы принимаете Indicator в качестве параметра, но на самом деле вам нужно принять TreeNode, потому что каждый узел имеет данные типа Indicator, к которым вы можете получить доступ.

В вашем search() вы снова и снова вызываете search() с одинаковыми параметрами , которые никогда не дадут вам результатов. Кроме того, у вас нет базового варианта. Это не так, как рекурсия работает. Вы получите stackoverflowException (ХАХАХА, забавно, что мы на StackOverFlow). Используйте этот код вместо: 

public void search(string key)
{
    searchHelper(key, root);  // root node will be in Tree.java
}

public void searchHelper(string key, TreeNode current)
{
    if(current == null)
    {
        System.out.println("\nCant find !");
        return;
    }
    if(key.compareTo(current.idct.getICode()) < 0 )
        searchHelper(key, current.left);
    else if(key.compareTo(current.idct.getICode()) > 0)
        searchHelper(key,current.right);
    else
        System.out.println("\n"+current.idct + "Found \n");
}
...