バイナリ木

みんな、私は、バイナリツリーのために、この構造を参照してください

struct btree { 
    int data; 
    struct btree *left; 
    struct btree *right; 
};

書籍やリファレンスの時間のデータstructures.Mostに新しいですが、上の画像では、それは次のようになり以下のような

struct btree 
{ 
    int data; 
    struct btree *left; 
    struct btree *right; 
    struct btree *parent; 
};

だから私の質問は、それは（また、親へのポインタを含むなどのため）、ツリーのノードの構造を選択することがプログラマに依存し、それがされているか、我々は2つだけPOINを持つことができます1つは左の子に、もう1つは右の子に割り当てます。

上位に移動する必要がない場合は、親ノードを含むポイントはありません。 – dreamlax

親ポインタを含めるかどうかはあなた次第です。メンテナンスにはもっと多くの作業が必要ですが、（親ではなくそのノードだけを削除するなどの）いくつかのツリー操作はずっと簡単になります。

2011-02-04 02:57:57

あなたはまた完全なバイナリtreeを構築する方法を教えてもらえますか？私が解釈できないのは、ノード間のリンクがないのでノード挿入のためにBFSのやり方で移動する方法です。 – Algorithmist

@ yogi15490：どうやって木を回りたいですか？そのために子ポインタを使用します。また、親ポインタを含む場合は親ポインタを使用することもあります。 –

@ yogi15490：挿入するときは、ツリーを*下に移動するだけでよいので、子ポインタだけが必要です。 – caf

これはあなた次第です。一般的に、ほとんどのツリー操作では不要ですが、余分なリンクを格納するために必要なメモリを犠牲にして、それらを高速化できます。私は二度とツリーを書く必要がありましたが、私は親リンクを使ったことは一度もありませんでした。

2011-02-04 02:59:53

特に明記していない限り、バイナリツリーには通常、その図に示すように親へのポインタは含まれていません。 "親へのポインタ"は通常、木を再帰的に横断する際に暗黙的にスタックに格納されます。

"スレッド化バイナリツリー" - この場合、通常のバイナリツリーにNULLポインタを持つリーフノードの代わりに、次のノードへのポインタとその前のノード順番に。これにより、再帰せずに順方向または逆方向にツリーを歩くことができます。

2011-02-04 03:14:21

これらのNULLポインターに_tag_する必要がありますか？ –

@luserdroog：必要があるかもしれませんが、ツリーの使い方によって異なります。 –

親ノードを持たないモデルは、再帰的な分割・征服スタイルのアルゴリズム[例えば、プリオーダーまたはポストオーダートラバーサル]に適しています。より高度な操作を行うには、親ポインタが必要です。

あなたは何をしようとしていますか？

2011-02-04 03:14:57

答えて