Java帮助递归和二叉树

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上寻找答案，更不用说所有其他网站了。

请帮忙！

编辑： 我编辑了代码，以包括我已经改变了@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，不只是把它扔掉的结果。