木構造とは、データ構造の一つで、一つの要素(ノード)が複数の子要素を持ち、一つの子要素が複数の孫要素を持ち、という形で階層が深くなるほど枝分かれしていく構造のことです。
- 木構造の最上位となるノード（節）をルートノード(根)と呼びます。
- ノードには0個以上の子ノードに対するリンクがあります。
- ノードBがノードAの子ノードの時、ノードAはノードBの親ノードとなります。（親子関係）
- ルートノードの親ノードはありません。
- 子ノードがないノードのことを、リーフ(葉)と呼びます。
- リーフノードでないノードのことを、内部ノード(internal node)といいます。
- 親ノードと子ノードとの距離を1とするとき、ルートノードからリーフノードまでの最大の距離を木の高さといいます。下の木の高さは3です。
幅優先探索
上から順に同じ深さのノードをたどって行く方法。しらみつぶしにすべてをたどるのであれば、こちらの方が効率が良いと言えます。
深さ優先探索
上から順に同じ深さのノードをたどって行く方法。しらみつぶしにすべてをたどるのであれば、こちらの方が効率が良いと言えます。
- 前順・先行順・前置順(preorder)
- １、根ノードを調査する。
- ２、もしあれば、左の部分木を前順走査する。
- ３、もしあれば、右の部分木を前順走査する。
- 右図では、1234567の順番で処理
- 間順・中間順(inorder)
- １、もしあれば、左の部分木を間順走査する。
- ２、根ノードを調査する。
- ３、もしあれば、右の部分木を間順走査する。
- 右図では、3241657の順番で処理
- 後順・後行順・後置順(postorder)
- １、もしあれば、左の部分木を後順走査する。
- ２、もしあれば、右の部分木を後順走査する。
- ３、根ノードを走査する。
- 右図では、3426751の順番で処理
【木構造】