6

TrieC++ で実装を作成しようとしています。に保存されているすべての単語を印刷する方法がわかりませんTrie。

これが私が実装した方法TrieNodeです。

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

pointer親ノードに a を保存し、すべてのノードを深さ優先検索しisWord==True、それらのノードから各単語を再帰的に出力できることを知っています。

Trieしかし、 a の実装で の各単語を出力する方法があるのだろうかと思っていTrieNodeます。

助けてくれてありがとう。

4

4 に答える 4

12

これは、データが文字であると想定していない、コンラッド・ルドルフのかなり効率的なバージョンです。また、コンラッドのバージョンで割り当てられた O(n^2) の合計メモリを削除しましたが、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 に答える