在cpp中实现一个trie

Question

我想在cpp中实现一个trie。当我试图打印出 trie 中的所有字符串时，什么也没有打印出来。但是代码编译成功。我认为我的插入有问题。我的猜测是我应该在某处通过引用传递，以便实际修改 trie，但我不确定问题出在哪里。

我的结构：

struct Node {
    unordered_map<char, Node*> children;
    bool completeWord;
};

class Trie {
private:
    Node* root;
    void printAll(Node* tmp);
public:
    Trie();
    void insert(string s);
    void printAll();
};

Trie::Trie() {
    root = new Node();
    root->completeWord = false;
}

方法：

void Trie::insert(string s) {
    Node* p = root;
    for(char c : s) {
        auto m = p->children;
        if(!m.count(c)) {
            Node* n = new Node();
            m.insert(pair<char, Node*>(c,n));
        }
        else
            p = m[c];
    }
    p->completeWord = true;
}

用于调试的 printAll：

void Trie::printAll() {
    printAll(root);
}

void Trie::printAll(Node* tmp) {
    Node* t = tmp;
    auto m = t->children;
    if(!m.empty()){
        for(auto p : m) {
            cout << p.first << " ";
            printAll(p.second); 
        }
    }
}

测试用例：


int main() {
    Trie* t = new Trie();
    string arr[] = {"abc", "abcd", "lmn", "edf"};
    for(string s : arr) 
        t->insert(s);
    t->printAll();
    return 0;
}

Answer 1

感谢 @Hitobat 和 @Code-Apprentice 我弄清楚了我做错了什么。在我的 insert 中应该是：

void Trie::insert(string s) {
    Node* p = root;
    for(char c : s) {
        auto &m = p->children; //m -> &m
        if(!m.count(c)) {
            Node* n = new Node();
            m.insert(pair<char, Node*>(c,n));
        }
        p = m[c]; //remove else
    }
    p->completeWord = true;
}

m 之前只是指向映射对的指针，没有 & 它只会更改这些对的副本，而不是这些对本身。所以我需要通过引用传递它们。插入新节点时 p 未更新。

在cpp中实现一个trie

implement a trie in cpp

c++

data-structures

trie