===== データ構造の表現法 -木構造と配列- =====


=== データ構造 ===

  * 配列　→　配列、動的配列（new とか使ってとってdeleteでけすやつ）
  * レコード型 → 構造体で表現できそう　
  * スタック　→　配列＋変数　LIFO（Last-in First-out　後入れ先出し）　下から詰めていって上からとる PEZとか、トランプを重ねて上からとる状態
    * トランプをシャッフル（ごちゃまぜ）して、スタックにトランプの構造体を並べて上から配る
  * キュー　→　配列＋変数　FIFO（First-in First-out 先入れ先出し）　待ち行列、並べた順にとる。先に並べたものを先にとる
    * エンキュー：　キューにデータを格納する → 行列の後ろにデータを追加する 　　
    * デキュー：　データを待ち列から取り出す
  * 木・グラフ
    * グラフ：有向グラフと無向グラフがあるよ。　ノード（頂点）とエッジ（辺）で表される。

=== 木構造：根、枝、節、葉をもつ ===


　根：ルートとも呼ばれる。これ以上さかのぼれない一番上位の節（一番親になる節） 　枝：節と節をつなぐエッジの事。 　節：ここにデータが格納されている。枝によって接続されてる。上位に向かってたどると、必ず根にたどり着くはず 　葉：一番下位の節、それ以上の子要素を持たない。
<code>
　 親　　　　　　　　　 　根
　／＼　　　　　　　　／　｜　＼ ← 枝
子　　子　　　　　　節　　節　　節 
　　　　　　　　　 ／＼　／＼　／＼ 　
    　　　　　　　葉　 葉 葉　葉 葉
</code>


=== 二分木 　C++でどうやって表現する？ ===
<code>
　　 　　　 　根　　　
　　　　 　／　 　＼
 　　　　節　　　　 節
   　  ／　＼     ／　＼
  　　節　　節　 節　　 節
   　／＼  ／＼ ／＼   ／＼
    葉　葉葉　葉葉 葉　葉
</code>

== 構造体を使って、まじめに概念通り実装 ==

<code cpp>
struct tree
{
    int node;//格納するデータ
    struct tree *left; //左の子
    struct tree *right; //右の子
}
</code>

== 構造を考慮して、配列で表現 ==


<code>
    　        根　　　　　　　
   　　　　／　　 ＼ 　
   　　　節　　　  　節
   　  ／　＼      ／　＼ 　　
     節　　 節　  節　　 節
    ／＼   ／＼  ／＼   ／＼ 
   葉  葉 葉 葉 葉 葉　葉

   　　 　　　　 0　           　 ← １段目　１個のデータ
  　　　　　 ／　　  ＼
   　　　　1　　　   　2          ← ２段目　2個のデータ
   　  　／　＼      ／　＼
    　　3　　  4    5   　 6　　　← ３段目　4個のデータ
      ／＼   ／＼  ／＼   ／＼ 
     7 　 8 9　10 11 12 13   14　← ４段目　8個のデータ
     
</code>

上の図からわかること：
**n段目には何個の節がある？　2の(n-1)乗個の節（データ）があるよ。**
  * ノード番号：上の図の配列の添え字に対応する番号の事（勝手に読んでるよ）
  * 自分から見た右の子の番号 ＝ 自分ｘ２＋２ 
  * 自分から見た左の子の番号 ＝ 自分ｘ２＋２ー１＝ 自分ｘ２＋1

教科書P１７８（１）の２分木

<code>
[ 0][ 1][ 2][ 3][ 4][ 5][ 6][ 7][ 8][ 9][10][11][12][13][14]
[ 6][ 3][ 7][ 1][ 4][  ][  ][  ][  ][  ][  ][  ][  ][  ][  ]
</code>

(仮) 逆もやってみよう(配列表現→木構造図示)

<code>
[ 0][ 1][ 2][ 3][ 4][ 5][ 6][ 7][ 8][ 9][10][11][12][13][14]
[ 7][ 9][15][22][11][18][27][  ][  ][  ][  ][  ][  ][  ][  ]
</code>

練習問題：これは配列で表すとどうなる？
<code>
　　 　　　　 7　　　　　　　　　　　
　　　　　 ／　　＼
 　　　　9　　　 　15
　　 　／　＼ 　　／　＼ 
　　　22　　11　 18　　 27
</code>