木構造とは

木構造はその名の通り 根や葉や枝を持つ 木のようなデータ構造です。 どのような構造なのか 概念的なことを説明してみましょう。 木構造は、ツリー構造とも呼ばれますが、 階層を持ったデータ構造です。 例えば、会社の組織図や 家計図のように段階的に 枝分かれしていくような構造です。 木構造では、親が複数の子を持ち、 子はひとつだけの親を持っています。 いくつかのノード、節と それを結ぶブランチ、 枝から構成されています。 あるノードの上のブランチにつながる ノードを親と呼びます。 各ノードにとって、 親はひとつだけです。 あるノードの下のブランチにつながる ノードを子といいます。 各ノードは何個でも 子を持つことができます。 また、あるノードは、 上位のノードから見れば子ですが、 下位のノードから見れば、 親であることがあります。 共通の親を持つノードは、 兄弟と呼ばれます。 部分的に見て、 親子関係が成り立っている部分を 部分木と呼びます。 また、木の一番はじめのノードを ルート、根、 子を持たないノードをリーフ、 葉と呼びます。 木構造の図を描くときには、 植物の木とは逆向きで、 この図のように、 根を上にして 葉を下に描きます。 ルートから、どれぐらい離れているのかを 示すのがレベルです。 ルートのレベルは０であり、 下へ行くほど、 レベルが上がります。 ルートから最も遠いリーフまでの 距離を高さと呼びます。 この図の木では、 高さは３です。 すべてのノードを 訪れることを 木の探索や操作といい、 幅優先探索と深さ優先探索の 大きく２つの方法があります。 幅、優先探索は、 横型探索ともよばれます。 ルートから開始して 同じレベルにあるノードを、 左から右に辿ります。 それが終わると、 次のレベルを 左から右に辿ります。 深さ優先探索は、 縦型探索とも呼ばれ、 先行順、中間順、後行順の ３種類があります。 先行順は前順、 行きかけ順とも呼ばれます。 ルート、左部分木、 右部分木の順にたどります。 ルートから出発し、 ノードの左側を 順番になぞると、 辿ることができます。 （音声なし） 中間順は間順、 通りがけ順とも呼ばれます。 左部分木、ルート、 右部分木の順に辿ります。 左端のノードから出発し、 ノードの下側を 順番になぞると、 辿ることができます。 （音声なし）…