K-fix Learning & Playing

アルゴリズムとプログラミング


木構造

木構造とは、データ構造の一つで、一つの要素(ノード)が複数の子要素を持ち、一つの子要素が複数の孫要素を持ち、という形で階層が深くなるほど枝分かれしていく構造のことです。

木構造
  • 木構造の最上位となるノード()をルートノード()と呼びます。
  • ノードには0個以上の子ノードに対するリンクがあります。
  • ノードBがノードAのノードの時、ノードAはノードBのノードとなります。(親子関係)
  • ルートノードの親ノードはありません。
  • 子ノードがないノードのことを、リーフ()と呼びます。
  • リーフノードでないノードのことを、内部ノード(internal node)といいます。
  • 親ノードと子ノードとの距離を1とするとき、ルートノードからリーフノードまでの最大の距離を木の高さといいます。下の木の高さは3です。
木構造

幅優先探索

上から順に同じ深さのノードをたどって行く方法。しらみつぶしにすべてをたどるのであれば、こちらの方が効率が良いと言えます。

木構造

深さ優先探索

上から順に同じ深さのノードをたどって行く方法。しらみつぶしにすべてをたどるのであれば、こちらの方が効率が良いと言えます。

木構造
前順・先行順・前置順(preorder)
1、根ノードを調査する。
2、もしあれば、左の部分木を前順走査する。
3、もしあれば、右の部分木を前順走査する。
  右図では、1234567の順番で処理
間順・中間順(inorder)
1、もしあれば、左の部分木を間順走査する。
2、根ノードを調査する。
3、もしあれば、右の部分木を間順走査する。
  右図では、3241657の順番で処理
後順・後行順・後置順(postorder)
1、もしあれば、左の部分木を後順走査する。
2、もしあれば、右の部分木を後順走査する。
3、根ノードを走査する。
  右図では、3426751の順番で処理
木構造