基本的なプレフィックスツリー実装の質問

StackOverflow https://stackoverflow.com/questions/6348391

質問

基本的なプレフィックスツリーまたは「Trie」を実装しました。 Trieは次のようなノードで構成されています。

// pseudo-code
struct node {
    char c;
    collection<node> childnodes;
};

トライに次の言葉を追加してください：「Apple」、「Ark」、「Cat」。 「AP」や「CA」などの接頭辞をルックアップすると、Trieの「Bool ContainsPrefix（String Prefix）」メソッドが正しく返されます。

今、私は「cat」と「ark」にtrueを返すメソッド「bool cantableswholeword（string word）」を実装していますが、「アプリ」にはfalse（上記の例では）を実装しています。

Trieのノードが何らかの「endofword」フラグを持つことは一般的ですか？ これは、見た目である文字列が実際には、単なる接頭辞ではなく、trieに入った単語全体であるかどうかを判断するのに役立ちます。

乾杯！

役に立ちましたか？

解決

「アプリ」と「Apple」の両方を保存する必要があるが、「Appl」ではなく保存する必要がある場合、はい、あなたはのようなものが必要です endOfWord 国旗。

または、同じ文字を持つ2つのノードを持つことで、（時には）デザインに適合させることができます。したがって、「AP」には子育て：葉のノード「P」と内部ノード「P」が子の「L」が必要です。

他のヒント

キーの端は通常、リーフノードを介して示されます。また：

  • 子ノードは空です。また
  • キーの1つの接頭辞を備えたブランチがあり、一部の子供ノードがあります。

デザインにはリーフ/空のノードがありません。たとえばnullでそれを示してみてください。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top