Справка Java Recursion & Binary Trees

Question

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

Мои проблемы возникают, когда я добавляю данные и/или когда я ищу данные для строки.

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

public void add(String newWord) { 

    //Change the word case to make comparing easier 
    newWord = newWord.toUpperCase(); 


    root = recursiveAdd(root, newWord); 
} 

/** 
* Takes the root and recurses until the root is null (base case) 
* Frequency is incremented if the data is being added, or if 
* it already exits. If the data is not present, the method recurses 
*/ 
private Node recursiveAdd(Node subTree, String newWord) { 

    //Base case: the root is null 
    //Empty trees have a node created, set, and incr freq 
    if (subTree == null) { 
     subTree = new Node(); 
     subTree.setStoredWord(newWord); 
     subTree.incrFreqCount(); 
     return subTree; 

    } 


    int comparison = newWord.compareTo(subTree.getStoredWord()); 

    //For a word already in tree, increment the frequency 
    if (comparison == 0) { 

     if(newWord.equalsIgnoreCase("translyvania")) 
     System.out.println("Entered same word incrementation"); 

     subTree.incrFreqCount(); 
     return subTree; 

     //The root comes before the new word, then 
     //move on to the right child 
    } else if(comparison < 0) { 

     subTree.setLchild(recursiveAdd(subTree.getLchild(), newWord)); 

    } else { //if(comparison > 0) { 

     subTree.setRchild(recursiveAdd(subTree.getRchild(), newWord)); 

    } 
    return subTree; 
} 

Я не могу сказать, где моя проблема. Для слова, которое я ищу, иногда говорится, что оно происходит 16 раз (что я должен получить), и иногда он говорит 1 раз. Кажется, что это совсем несовместимо, и изменение ценности по-видимому не имеет причины (хотя я знаю, что он должен быть один).

Как только мое дерево построено, я беру строку, которую я ищу, и передаю ее с помощью этих методов.

public void wordSearch(String lookForWord){ 

    lookForWord = lookForWord.toUpperCase(); 
    wordSearchRecur(root, lookForWord); 

} 



private boolean wordSearchRecur(Node subTree, String lookForWord){ 

    //Base case 
    // The root is that same as the string 
    if(subTree == null){ 
     System.out.println("The word \"" + lookForWord + "\" is not " 
       + "found in the text"); 
     return false; 
    } 

    int comparison = lookForWord.compareTo(subTree.getStoredWord()); 

    if(comparison == 0){ 
     System.out.println("The word \"" + lookForWord + "\" is found " + 
       subTree.getFreqCount() + " times in the text"); 
     return true; 


     //Alphabetically before, then move to left branch 
    } else if (comparison < 0){ 

     System.out.println("move to left"); 
     return wordSearchRecur(subTree.getLchild(), lookForWord); 

     //Alphabetically after, then move to right branch 
    } else { // if(comparison > 0){ 
     System.out.println("move to right"); 
     return wordSearchRecur(subTree.getRchild(), lookForWord); 
    } 

} 

Я также не могу понять, почему я добираюсь до конца метода wordSearchRecur(). Разве я не должен возвращаться, прежде чем он дойдет до этого? Мой вывод показывает, что он достигает его несколько раз.

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

Пожалуйста, помогите!

EDIT: Я отредактировал код, чтобы включить то, что я изменил, благодаря помощи @Joop Eggen. Теперь у меня есть частота, вычисленная правильно во время recursiveAdd(), но во время wordSearchRecur() частота не кажется следовать за узлом. Даже при сравнении == 0 частота freqCount остается равной 1.

РЕШЕНИЕ: После помощи @Joop Eggen дальнейшие проблемы были только результатом недосмотра. Спасибо за помощь.

Answer 1

Вы получите выгоду от первого сокращения кода до его простейшей формы.

public void add(String word) { 

    //Change the word case to make comparing easier 
    word = word.toUpperCase(); 

    root = recursiveAdd(root, word); 
} 

/** 
* Takes a sub-tree and recurses until the sub-tree is null (base case) 
* Frequency is incremented if the data is being added, or if 
* it already exists. If the data is not present, the method recurses 
*/ 
private Node recursiveAdd(Node subtree, String word) { 

    // Base case: the subtree is null 
    if (subtree == null) { 
     Node node = new Node(); 
     node.setStoredWord(word); 
     node.incrFreqCount(); 
     return node; 
    } 

    int comparison = word.compareTo(subtree.getStoredWord()); 
    if (comparison == 0) { 
     // For data already in tree, increment the frequency 
     subtree.incrFreqCount(); 
    } else if (comparison < 0) { 
     subtree.setLchild(recursiveAdd(subtree.getLchild(), word); 
    } else /*if (comparison > 0)*/ { 
     subtree.setRchild(recursiveAdd(subtree.getRchild(), word); 
    } 
    return subtree; 
} 

Как также ищу:

public void wordSearch(String lookedForWord){ 
    lookedForWord = lookedForWord.toUpperCase(); 
    wordSearchRecur(root, lookedForWord); 
} 

private boolean wordSearchRecur(Node subtree, String word){ 

    if (subtree == null) { 
     System.out.println("The word \"" + word + "\" is not " 
       + "found in the text"); 
     return false; 
    } 

    int comparison = word.compareTo(root.getStoredWord(); 
    if (comparison == 0){ 
     System.out.println("The word \"" + word + "\" is found " + 
       subtree.getFreqCount() + " times in the text"); 
     return true; 
    } else if (comparison < 0) { 
     return wordSearchRecur(subtree.getLchild(), word); 
    } else /*if (comparison > 0)*/ { 
     wordSearchRecur(subtree.getRchild(), word); 
    } 
} 

Это помогает держать ошибки в страхе, так как есть меньше, чтобы проверить/ошибется.

Как вы делали toUpperCase в обеих случаях, и в переписывании также сравнение сделали то же самое (у Вас были равные, и повернулись вокруг compareTo параметров, все должно работать.

На самом деле код, показанный выглядит довольно хорошо. Сделайте рекурсивный dumpTree(Node subtree, String indentation) и проверьте каждый шаг.

Возможно, вы редактировали код здесь немного, и изначально некоторые брекеты { } были неуместны.

Answer 2

Вы не возвращаются ни в одном из этих случаев:

//Alphabetically before, then move to left branch 
if(lookForWord.compareTo(root.getStoredWord()) < 0){ 
    System.out.println("move to left"); 
    wordSearchRecur(root.getLchild(), lookForWord); 

//Alphabetically after, then move to right branch 
} else if(lookForWord.compareTo(root.getStoredWord()) > 0){ 
    System.out.println("move to right"); 
    wordSearchRecur(root.getRchild(), lookForWord); 
} 

Вы должны return wordSearchRecur, а не просто назвать его и выбросить результат.