6

我正在尝试Trie用 C++ 创建一个实现。我无法弄清楚如何打印存储在Trie.

这就是我实施TrieNode.

struct TrieNode{
  bool isWord;
  int data; //Number of times Word Occured
  TrieNode *Child[ALPHABET_SIZE]; //defined as 26
};

我知道我可以将 a 存储pointer到父节点，深度优先搜索所有节点，isWord==True并递归打印这些节点中的每个单词。

但我想知道有没有办法Trie用我实现的 a打印出每个单词TrieNode。

谢谢你的帮助。

4

4 回答 4

12

这是 Konrad Rudolph 的一个相当有效的版本，没有假设 data 是一个字符。我还以使用std::string&. 这个想法是传递前缀并在每次递归时对其进行修改，将字符推到末尾并随后弹出它，最终比疯狂复制它更有效。

void traverse(std::string& prefix, TrieNode const& node) {
  if (node.isWord)
    print(prefix);

  for (char index = 0; index < ALPHABET_SIZE; ++index) {
    char next = 'a'+index;
    TrieNode const* pChild = node.Child[index];
    if (pChild) {
      prefix.push_back(next);
      traverse(prefix, *pChild);
      prefix.pop_back();
    }
  }
}
于 2012-12-03T15:18:49.697 回答
5

您不需要父节点，您的代码很容易通过递归适应遍历。伪代码：

void traverse(string prefix, TrieNode const& n) {
    prefix += static_cast<char>(n.data);

    if (n.isWord)
        print(prefix);

    for (auto const next : n.Child)
        if (next)
            traverse(prefix, *next);
}

这或多或少是有效的 C++。只要print适当定义。

编辑响应 Yakk 的评论和您的澄清，这是一个不假设data包含当前字符的版本（我的失误！）：

void traverse(string const& prefix, TrieNode const& n) {
    if (n.isWord)
        print(prefix);

    for (std::size_t i = 0; i < ALPHABET_SIZE; ++i)
        if (n.child[i])
            traverse(prefix + ('a' + i), *n.child[i]);
}

我将把更有效的实现留给 Yakk 的回答。

于 2012-12-03T14:57:52.707 回答
0 
void traversePrint(TrieNode* sr,char* out,int index)
{
    if(sr!=NULL)
    {
        for(int i=0;i<SIZE;i++)
        {
            if(sr->child[i]!=NULL)
            {
                out[index] = 'a'+i;
                traversePrint(sr->child[i],out,index+1);
            }
        }
        if(sr->isEnd)
        {
            out[index]='\0';
            cout << out << endl;
        }
    }
}

// 调用

char out[MAX_WORD_SIZE];
traversePrint(root,out,0);
于 2017-10-07T05:02:43.027 回答
-1

我认为这里不需要 isword。指向子节点的指针的存在将足以遍历 trie 中的可用单词。要查找单词，请从根开始，并在任何递归步骤中查找单词中的当前字符。

struct trie {
  trie *children[ALPHABET_SIZE];
};


void traversal(trie *&t, string &str) {
    bool is_seen = false;
    for(int i = 0; i < ALPHABET_SIZE; i++) {
        if(t->children[i]) {
            if(!is_seen) {
               is_seen = true;
            }
            str.push_back(t[i]);
            traversal(t->children[i], str);
            str.pop_back();
        }
    }
    if(!is_seen) {
        cout << str << "\n";
    }

}
于 2017-05-08T15:27:11.990 回答