木構造とは

木構造とは、データ構造の一つで階層を持った構造のものです。親子関係の階層で、1つの親から1つまたは複数の子をがある構造です。子から見た親は1つだけです。家系図のようなイメージをするといいですね（婚姻関係とかはないですが）。

1つの親から子の階層へと枝分かれを繰り返していく構造で、それをひっくり返してみてみると葉が生い茂る木のような見た目になるため木構造と呼ばれています。

木構造の要素

木構造は本物の木と同じ名前の構成要素で構成されています。

• 節（node(ノード)）：構成する要素
• 葉（leaf(リーフ)）：末端の節（葉ノード）
• 根（root(ルート)）：先頭の節（根ノード）
• 枝（branch(ブランチ)）：要素と要素のつながり
• 末端でも先頭でもない節：部分ノード
• 部分木：全体の木構造から抜き出した節とその下の要素

2分木、多分木

1つの親から子の階層へと枝分かれするときに、その数により呼び方が変わります。

• 2分木：1つの親から子が2つにわかれること
• 多分木：1つの親から子が3つ以上にわかれること

階層をほとんど同じにするようにしたものを「平衡木 （バランス木）」といいます。

探索方法の種類

深さ優先探索、幅優先探索の2種類があります。

深さ優先探索

前順（先行順）・間順（中間順）・後順（後行順）の3つに分けられる順で探索していきます。

前順

根から左の下の階層を探索しさらにその左の下の階層を探索します。つまり左にある部分木を探索するということです。それが終わったら1階層上の右に向かいます。そこからも同様に部分木の探索をすることを繰り返していき、右に向かっていく順番です。前世代から後世代に向かっていくというイメージですね。

間順

一番左側のノードから右に向かっていきます。右に向かうときに複数存在する場合は上から順に探索します。子ノードがあるときは下に下った後に上に戻り、1つ上の別の階層に向かうようにしていきます。この順だけ縦に探索しています。

後順

左側の部分木の一番下の階層から右に向かって部分木内を探索します。その階層が終わったら一つ上の階層に移ってまた左から右に向かって探索します。前順の逆の順番です。後世代から前世代に向かっていくというイメージですね。

幅優先探索

根から開始し、下の階層を左から右に向かって探索していきます。1つの階層が探索し終えたらその下の階層に移ってまた左から右に向かってた探索をします。繰り返し行って最後の階層まで向かいます。