47517
C++で自己参照構造体というものがあると思います。（後述の二分探索木の例を参照）

この場合、p,l,rの型はNodeではなくてNode*です。  
これはNodeではいけないのでしょうか？

ネットで自己参照構造体をぐぐってみると、みんなポインタを使ってはいるものの、  
ポインタである必要性を説明している記事が見当たらなかったので不思議に思ってます。

```

    struct Node {
      int key;
      Node *p, *l, *r;
    }
    
```
CC BY-SA 4.0
2018-08-14T13:55:23.770
47515
2018-08-14T15:16:14.213
29267
question
c++ アルゴリズム データ構造
C++での自己参照構造体におけるポインタにおいて
すでにあるコメントだけで十分だと言う気もしますが。

```

    struct MyStruct {
        int a;
        int b;
    }
    
```

なんて宣言があると、コンパイラは`MyStruct`型に「`int`2個分」の領域を割り当てます。

```

    struct AnotherStruct {
        int key;
        MyStruct subStruct;
    }
    
```

だと、`AnotherStruct`の大きさは、`key`の「`int`1個分」と`subStruct`の「`int`2個分」を合わせて「`int`3個分」なります。

もし、こんな宣言が可能だとしたら、`LinkedList`の大きさはどうなりますか?  
(二分木ではなく、単方向リストにして単純化しておきます。)

```

    struct LinkedList {
        int key;
        LinkedList next;
    }
    
```

このように直接の自己言及(再帰)を許してしまうと、コンパイラは`LinkedList`のサイズも内部表現も決定できなくなってしまいます。

(x = 1 + x の解を探すようなもので、無限大を許す算術をこしらえないと、解無しになってしまいます。)

このようなことを防ぐために、構造体等の宣言では直接の自己言及を禁止して、再帰的な構造はポインタ(ポインタのサイズは、ポイント先の大きさにかかわらず一定)を使用して表現します。

```

    struct LinkedList {
        int key;
        LinkedList *next;
    }
    
```

`LinkedList`のサイズは「`int`1個分とポインタ1個分」(どちらも8バイトのシステムなら16バイト)とすぐに決定できます。

* * *

「structがコンピュータのメモリの中でどう表現されているのか」、を少し想像してもらうとすぐ分かりそうに思うのですが、ユーザが定義できるのは全て参照型であるJavaなんかの経験があるとかえってわかりにくいかもしれません。

ちなみに、今回はstructで説明しましたが、C++の場合structとclassの差異はあまりないので、以上の議論はclassでも成り立ちます。
CC BY-SA 4.0
2018-08-14T15:02:44.827
47517
2018-08-14T15:16:14.213
2018-08-14T15:16:14.213
13972
13972
47515
answer