1

C++ を学習しようとしているときに、非常に基本的なトライを表すクラスを実装しようとしました。私は次のことを思いつきました：

class Trie {
public:
    char data;
    vector<Trie* > children;

    Trie(char data);
    Trie* addChild(Trie* ch);    // adds child node

    (skipped others members/methods)

};

メソッドaddChildは、同じデータを持つ子chがベクターchildrenに存在するかどうかをチェックし、存在しない場合はそこに挿入し、存在する場合は、既存の子へのポインターを返します。

ここで、このコード スニペットを検討します。

Trie t('c');
Trie* firstchild = new Trie('b');
Trie* secondchild = new Trie('a');


firstchild->addChild(secondchild);
t.addChild(firstchild);

secondchildへのポインターしかない場合、何らかの方法でfirstchildまたはtへのポインターを返すことは可能ですか?

私の作業コードのロジックは、現在のオブジェクトの親まで、(下位ノードから上位ノードへ) トライを「上」にトラバースする必要があるため、それが可能かどうかを知りたいです。現在、私は再帰関数を使用して下に移動していますが、他の方法があるかどうか疑問に思っていますか?

上記が不明確であるか、どこかで失敗した場合は申し訳ありませんが、私はかなり経験が浅く、作業コードなしで記憶から書いています。

4

3 に答える 3

4

次のようなものを追加する必要があります

Trie* parent;

また

Trie* previoussibling;
Trie* nextsibling;

クラスに直接移動firstchildしsecondchildたり、その逆を行ったり、子の1人からに移動したりしtます。

この種の関係が必要な場合は、すべてのリンクを正しく保つためにノードを追加および削除するときに、より多くのメンテナンスが必要になることに注意してください。

于 2009-09-23T08:55:20.040 に答える
2

Trie オブジェクトは、親オブジェクトを追跡しません。基本的には単一の連結リストに似ており、親を「知らない」場合を除き、トラバースすることはできません。

class Trie {
public:
    char data;
    vector<Trie* > children;
    Trie* parent;

    Trie(char data):parent(NULL){}
    Trie* addChild(Trie* ch)
    { //set the parent
     ch->parent = this;
    }

    (skipped others members/methods)

};

次に、トラバースは次のようになります。

traverse(Trie* pPtr)
{
Trie* currentPtr = pPtr;
 while(currentPtr)
 {
  currentPtr = currentPtr->parent;
 }

}

于 2009-09-23T08:49:35.230 に答える
1

私はセカンドチャイルドへのポインターしか持っていませんが、どういうわけかファーストチャイルドまたは多分tへのポインターを返すことは可能ですか？

いいえ。firstChildを2番目の子の親として渡すことにより、その関係を自分で確立する必要があります。

于 2009-09-23T08:52:06.223 に答える