Java 帮助递归和二叉树

Question

我对 Java 有点陌生，对递归和二叉树也很陌生。我正在构建一个程序，该程序从文档中获取文本并将其存储在二叉树中。然后我需要取一个字符串并找出它在文本中出现了多少次。

我的问题是在添加数据时 and/or 在搜索字符串数据时。

我决定在构建时将字符串和频率存储在每个节点中。所以我的添加方法如下：

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

您不会 return 在以下任一情况下：

//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，而不是调用它然后丢弃结果。

Answer 2

您将从首先将代码简化为最简单的形式中获益。

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);
    }   
}

这有助于避免错误，因为 check/go 错误较少。

正如您在这两种情况下所做的那样 toUpperCase，并且在重写中也进行了相同的比较（您有等于并转向 compareTo 参数，一切都应该有效。

事实上，显示的代码看起来还不错。进行递归 dumpTree(Node subtree, String indentation)。并检查每一步。

可能你在这里稍微编辑了代码，原来一些大括号 { } 放错了地方。

Java 帮助递归和二叉树

Java Help Recursion & Binary Trees

java

recursion

binary-tree