在 BST 中搜索某个单词时，如何找到它出现了多少次

Question

我有一个从文本文件填充的二叉搜索树

当我显示 BST 时它看起来像这样

                            the                                                              
            in                              was                              
    Minnesota              it              --              --              
--      --      --      stomach      --      --      --      --      
  --  --  --  --  --  --  only  --  --  --  --  --  --  --  --  --

我用这个方法从那个搜索树中的数组中搜索一个单词，如果数组中的单词存在于二叉搜索树中，它会 sysout 它

public boolean contains(String d)
{
            BSTNode p = root;

  // Not contained if specified string is null
  if (d == null)
    return (false);

  // OK if specified string equals our data
  if ((p.data != null) && p.data.equals(d))
    return (true);

  // OK if contained in left tree
  if ((p.left != null) && p.left.contains(d))
    return (true);

  // OK if contained in right tree
  if ((p.right != null) && p.right.contains(d))
    return (true);

  // Otherwise, it's not OK
  return (false);

}

在 BSTNode 中包含方法 class

public boolean contains(String item) {
    int comp = item.compareTo(data);
    if(comp  == 0) return true;
    if(comp < 0 && left != null && left.contains(item)) return true;
    if(comp > 0 && right != null && right.contains(item)) return true;
    // no matching node was found
    return false;
}

我就这样在main中使用它

for (int i = 0; i < len; i++) {

            t = array[i];

            if (btree.contains(array[i]) == true) {
                System.out.println(t);

            }

        }

输出

was
in
it
was
the
only
the
the
was
in
in
the
the
the
was
only
the

我怎么能这样输出

仅：2
是：4
它：1
在：3
: 7

...

所以我对代码的理解是它分别检查搜索节点中的所有单词，而不是在所有节点中搜索一个单词然后移动到下一个单词，这样我得到了这个输出，请纠正我是否我错了

希望有人能帮忙！

Answer 1

不确定您的 BST 是如何设置的，但您可以先创建一个 HashMap 并执行遍历并更新每个事件。

看看这样的方法


HashMap<String, Integer> map = new HashMap<>(); //initialize this in main or shell function

private void wordOccurrenceTree(TreeNode root) {
   
   //inorder traversal
    
    if (root == null) return;
    wordOccurrenceTree(root.left)
    if(map.containsKey(root.value)){ 
         map.put(root.value, map.get(root.value)+1);
    } else {
         map.put(root.value, 1);
    }
   
    wordOccurrenceTree(root.right);

   //HashMap should be populated with each word and occurrence when method is done recursing


}

Answer 2

我认为有几点不对：

根据定义，BST 不能有重复项。每个左节点必须小于根；每个右节点都必须大于根。
首先搜索树的左侧。您有点忽略了 bst 的好处。目前，对于大于根的数据，您的程序将开始搜索左节点。然后，您的程序将搜索该左侧节点的最右侧树。然后才会return到主要的classes包含，从根的右边继续查找

1 的解决方案：将您的字符串包装在 class 中，其中包含一个整数，如果要添加的新字符串是重复的，您可以递增。

2 的解决方案：

  // OK if specified string equals our data
  if ((p.data != null) && p.data.equals(d))
    return (true);

刚刚

return p.contains()

Answer 3

侵入性较小的方法是，收集单词：

    List<String> words = new ArrayList<>();
    for (int i = 0; i < len; i++) {
         t = array[i];
         if (btree.contains(array[i])) {
              words.add(t); // <-- collect the words
         }
    }

打印 word/frequency:

new HashSet<>(words).forEach(s -> System.out.println(s + ":" + Collections.frequency(words,s)));

或者，直接添加到地图：

   Map<String, Integer> word_count = new HashMap<>();
   for (int i = 0; i < len; i++) {
             t = array[i];
             if (btree.contains(array[i])) {
                  word_count.put(s, word_count.getOrDefault(t, 0) + 1);
             }
        } 
   word_count.forEach((key, value) -> System.out.println(key + ":" + value));

一种更有效的方法，如果您知道该字符串已经在 BST 上，则不要再次搜索它。例如：

  Map<String, Integer> word_count = new HashMap<>();
   for (int i = 0; i < len; i++) {
             t = array[i];
             if(word_count.contains(t){
                word_count.put(s, word_count.get(t) + 1);
             }
             else if (btree.contains(t)) {
                  word_count.put(s, 0);
             }
        } 
   word_count.forEach((key, value) -> System.out.println(key + ":" + value));

在 BST 中搜索某个单词时，如何找到它出现了多少次

How can I find how many times a word appear when I search for it in a BST

java

binary-search-tree