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

来源：9-6 实现Bellman-Ford算法

慕仰0554757

2021-06-03

// 统计圣经中所有词的词频
// 注: 这个词频统计法相对简陋, 没有考虑很多文本处理中的特殊问题
// 使用圣经作为我们的测试用例
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)++;
    }

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

写回答

1回答

liuyubobobo

2021-06-04

// 在 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 不是二分搜索法。二分搜索法是针对有序数组的一个搜索算法。

继续加油！：）

liuyubobobo

慕仰0554757

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

2021-06-04

共2条回复

算法与数据结构（C++版）面试/评级的算法复习技能包

课程专为：短时间内应对面试、升职测评等艰巨任务打造

11187 学习 · 1614 问题

查看课程