时间戳

首页 > 解决方案 > 如何使用二叉搜索树解决索引生成器的这个问题？

c++ - 如何使用二叉搜索树解决索引生成器的这个问题？

问题描述

我有一个任务是编写一个索引构建器应用程序，它获取由行组成的文本并打印文本单词的列表，并且它们出现的行打印在它们旁边。

但是当我尝试处理这个案例时遇到了一个问题，如果这个词已经存在，它总是在向量中添加一个冗余数字

谁能帮帮我？

这是 BSTnode 的定义：

class BSTnode
{
public:
    string data;
    vector<int> linesAppear;
    BSTnode* left;
    BSTnode* right;
    BSTnode()
    {
        left = right = NULL;
    }
};

这是 BSTFCI 的定义：

class BSTFCI
{
public:
    BSTnode* root;
    BSTFCI()
    {
        root = NULL;
    }
    void add(string ToBST,int lineAppear);
    BSTnode* Insert(BSTnode*& node,string ToBST,int lineAppear);
    BSTnode* create_new_node(string ToBST,int lineAppear);   
};

插入函数

BSTnode* BSTFCI::create_new_node(string ToBST,int lineAppear)
{
    BSTnode* Temp = new BSTnode();
    Temp->data = ToBST;
    Temp->left = Temp->right = NULL;
    Temp->linesAppear.push_back(lineAppear);
    return Temp;
}
BSTnode* BSTFCI::Insert(BSTnode*& node,string ToBST,int lineAppear)
{
    if(node == NULL)
    {
        node = create_new_node(ToBST,lineAppear);
    }
    if(ToBST > node->data)
    {
        node->right = Insert(node->right,ToBST,lineAppear);
    }
    if(ToBST < node->data)
    {
        node->left = Insert(node->left,ToBST,lineAppear);
    }
    //cout <<"inside insert"<< ToBST << endl;
    if(node->data == ToBST)
    {
        node->linesAppear.push_back(lineAppear);
     //   cout <<"inside insert condition "<< node->data << endl;
    }
    return node;

}
void BSTFCI::add(string ToBST,int lineAppear)
{
    root = Insert(root,ToBST,lineAppear);
}

主要功能：

int main()
{
    BSTFCI o;
    string input,ToBST;
    int lineAppear = 0;
    while(getline(cin,input))
    {
        if(input == "done")
        {
            break;
        }
        lineAppear++;
        istringstream convert(input);
        while(convert >> ToBST)
        {
            o.add(ToBST,lineAppear);
        }
    }
    o.print_inOrder(o.root);
    return 0;
}

标签： c++binary-search-tree

解决方案

这是因为您在create_new_node（实际上应该是 中的构造函数BSTnode）和之后的 when中都添加了数字if(node->data == ToBST)。

您需要决定是在创建节点时添加它还是之后添加它，但在创建时添加它是最有意义的——为什么要添加一个节点而不给它一个事件呢？

我会这样做：

class BSTnode
{
public:
    string data;
    vector<int> linesAppear;
    BSTnode* left;
    BSTnode* right;
    BSTnode() : left(nullptr), right(nullptr) {}
    BSTnode(const std::string& word, int appearance) 
        : data(word),
          linesAppear(1, appearance),
          left(nullptr),
          right(nullptr)
    {
    }
};


BSTnode* BSTFCI::Insert(BSTnode* node, string ToBST,int lineAppear)
{
    if(node == nullptr)
    {
        return new BSTnode(ToBST, lineAppear);
    }
    if(ToBST > node->data)
    {
        node->right = Insert(node->right, ToBST, lineAppear);
    }
    else if(ToBST < node->data)
    {
        node->left = Insert(node->left, ToBST, lineAppear);
    }
    else
    {
        node->linesAppear.push_back(lineAppear);
    }
    return node;
}

注意，node通过引用传递和返回都没有意义，所以我保留了返回并删除了引用。
你也可以做相反的事情。

推荐阅读