struct構造を入れ子にして2分木を表現したい

Question

C++で、structを例えば下記のようにして二分木グラフを表現したいのですがこれはC++ではやってはいけないようです。このような表現を別で表すためにはどうすればいいでしょうか？

struct Node {
    int data;
    Node left;  //二分木の左側のノード
    Node right; //右側
};

Answer 1

ポインタまたはスマートポインタにしてください。

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

なぜ、ポインタでは無い入れ子は駄目なのでしょうか？

色々考えかたがありますが、ここではNodeの大きさ(sizeofの値)がどうなるかを考えてみましょう。C++ではstructの大きさはコンパイル時に決定します※。仮にNodeの大きさsizeof(Node)をxとして考えましょう。leftやrightがNodeそのものであれば、leftやrightの大きさもsizeof(Node)、つまりxです。structは各メンバーを入れるための箱ですので、全てのメンバーの大きさを足した物よりも、structは大きくなければなりません。次のような式が成り立つはずです。

x ≧ sizeof(int) + x + x

intのサイズは環境依存ですが、現在のほとんどの環境では4バイトですので、4であると仮定しましょう。

x ≧ 4 + x + x
両辺からx + 4を引いて、左辺と右辺を入れ替えると
x ≦ -4

xは-4以下となりました。しかし、大きさが負になることはあり得ません。つまり、条件を満たすようなxは存在しないということです。ですので、Nodeの大きさをコンパイラは決定できず、コンパイルすることはできません。

では、ポインタにした場合はどうでしょう。leftやrightはsizeof(Node *)です。これはポインタのサイズであり、xとは異なります。

x ≧ sizeof(int) + sizeof(Node *) + sizeof(Node *)

ポインタのサイズも環境依存です。LP64環境であれば、intは4、ポインタは8になるので、

x ≧ 4 + 8 + 8 ＝ 20

xは20以上となります。これは実際にあり得る数字です。アライメントなどがあるので20とは限りませんが、コンパイラはNodeの大きさを決定でき、処理することが可能になります。

※ Cの構造体の場合、最後のメンバーがサイズ未指定の配列が使えますが、C++ではできなかったと思います。(ちょっと、曖昧)

Answer 2

こんにちは。

NodeがNodeを含んでいるということは、Nodeの中にはNodeがあり、その内側のNodeの中にもNodeがあり、更にその内側のNodeの中にもNodeがあり、・・・と無限に続きます。無限大の構造体を記録できるメモリは存在しないのでできません。
left, rightをNode型へのポインタにすると、Nodeに含まれるのはそのポインタまでで、ポインタの指す先は含まれません。従って、上記のように再帰的に確保されませんから、大丈夫なのです。

ちなみに、C#のclassは一見できるように見えますが、C#のclass型のメンバ変数はポインタだからできます。逆にC#のstructはC++のstructに近いので同じようにできない筈です。JavaのclassはC#のclassと同様です。

Answer 3

C＋＋に限りませんが、自分自身を含む構造体は構築不可ですd＾＾；
で、二分技だと左右の子ノードに対するポインタを持たします。
以下参考まで
C言語でのツリー構造
「追記」
raccyさんと別アプローチをw
例えば、

struct A{
    struct A a;
};

という構造体を考えた場合、struct A b;と宣言するとbの中にはAが含まれ、その中にはまたAが含まれ・・・
（鏡を合わせた時の鏡像を考えてみましょう）で、結局大きさが定まらないのです。