关于bst<二分搜索树的问题>

Question

// 统计圣经中所有词的词频
// 注: 这个词频统计法相对简陋, 没有考虑很多文本处理中的特殊问题
// 使用圣经作为我们的测试用例
string filename = “bible.txt”;
vector words;

    for (vector<string>::iterator iter = words.begin(); iter != words.end(); iter++) {
        int *res = sst.search(*iter);
        if (res == NULL)
            sst.insert(*iter, 1);
        else
            (*res)++;
    }

老师好，我想问的是，是不是这段代码，把无序的圣经中的单词和频次，逐个插入到单词树中，这个单词树是二分的、有序的、然后进行二分搜索？

Answer 1

liuyubobobo 2021-06-04 04:06:34

// 在 sst 中寻找 *iter
int *res = sst.search(*iter);

// 如果 sst 中没有 *iter 这个词，则在 sst 中添加这个词，且对应的值（频率）为 1
if (res == NULL) sst.insert(*iter, 1);

// 否则，sst 中有这个词，则频率值 *res ++        
else  (*res)++;

如果 sst 是一棵 BST 的话，是的，这棵树是有序的；

BST 不是二分搜索法。二分搜索法是针对有序数组的一个搜索算法。

继续加油！：）

• 提问者 慕仰0554757 #1

  for (vector<string>::iterator iter = words.begin(); iter != words.end(); iter++) {
          int *res = bst.search(*iter);
          if (res == NULL)
              sst.insert(*iter, 1);
          else
              (*res)++;
      }
  //我搞错了bst，在这题中，是用单词建立一棵bst吗？然后统计词频?
  第二：老师您说的“BST 不是二分搜索法”不太理解。BST不是二分搜索法，它是二分搜索树？

• liuyubobobo 回复 提问者 慕仰0554757 #2

  对，二分搜索树和二分搜索法是两个东西。二分搜索树是一个数据结构，二分搜索法是一个算法。