木
木構造では、データを格納する部分を接点(ノード)といいます。
構造的にデフォルトされた木を逆さまにした構造になっています。
親: 上位階層にある節点
子: 下位階層にある節点
根: 最上位の節点
葉: 子を持たない節点
二分木と多分木
二分木
一番最初の根で、分かれているのは二つまでの構造
ヒープ
データを並べ替える用途
二分探索木
データを検索する用途
多分木
根の部分で3っ以上に分かれている構造
B木
データを検索する用途に使用
全ての葉が同じ階層にある構造です。
完全二分木とヒープ
上位から順に、かつ、同じ階層で左から詰まっている
構造を完全二分木をいいます。
ヒープは更に完全二分木に置いて
親>子 または 子<親
の条件が全て成立している木です。
ヒープの条件
- 完全二分木であること
- 親子間に一定の大小関係が成立していること
二分探索木の条件
下記の条件を満たしていることが条件です。
- 節点の値< (節点の右についている全ての子の値)
- (節点の左についている全ての子の値)< 節点の値
木の巡回
データを順番に見ていくことを巡回するといいます。
幅優先探索
同じ階層の節点を優先して巡回します。
上から順 かつ 左から順です。
深さ優先探索
下位層の節点を優先して巡回します。
根からすぐ下に下に潜って行って、突き当たったら
一つ上に戻り下に、全て見終わっってたら上に戻って同じく・・・
という方法です。
先行順
行きがけ順に行います。
中間順
一旦一番下を処理してから途中の節点を処理していく
後行順
一番下を優先