木構造

概要

木構造とは木の構造を模したリスト型のデータ構造です。

algorithm_0001
algorithm_0001

ノード

木構造で管理するデータをノードと呼びます。 ノードは自分の親、または子供を保存する領域を持っており、 別のノードとつながり持つことができます。 algorithm_0002 algorithm_0002

ルート

ルートとは木構造の最初のノードのことです。 木構造はこのルートから各ノード間のリンクが始まります。 algorithm_0003 algorithm_0003

親子

親子とはノードとノードがつながっている状態を指します。 ルートに近いノードを親、ルートから遠いノードを子とします。 algorithm_0004 algorithm_0004

兄弟

兄弟とは同じ親をもつノードのことです。 algorithm_0006 algorithm_0006

葉とは木構造の末端にあるノードのことです。 algorithm_0005 algorithm_0005

必要な処理

木構造に必要な処理は「追加」「削除」「検索」の3つです。

追加

追加は指定したノードに対して新しいノードを追加します。 別の木構造のルートをノードとして追加することも可能です。

葉にノード追加

ノードの末端である葉に新しいノードを追加します。 次の画像では「攻撃」ノードに「物理」を追加しています。 algorithm_0008 algorithm_0008

葉に別の木構造追加

ノードの末端の葉に別の木構造をそのまま追加します。 次の画像では「攻撃」ノードに「魔法」をルートとした木構造を そのまま追加しています。 algorithm_0009 algorithm_0009

途中のノードにノード挿入

子供を持っているノードに別のノードを挿入します。 この時に挿入対象となったノードは挿入されたノードが新しい子になり、 挿入時に子だったノードの親が挿入されたノードになります。 次の画像では「魔法」と「回復」の間に「サポート」を挿入します。 その結果「魔法」の子が「サポート」、「回復」の親が「サポート」になります。 algorithm_0010 algorithm_0010

削除

削除は指定したノードをツリーの中から削除します。 木構造の種類にもよりますが、消されたノードの子供のノードもまとめて消すことが多いです。 次の画像では「魔法」のノードを消しますので、「魔法」以下のノードはすべて消去されます。 algorithm_0011 algorithm_0011

検索

指定したノードの情報を元にそのノードがあるかどうかを調べます。 検索は基本的にルートから始めます。 次の画像では「6」という値を木構造の中から検索しています。 algorithm_0012 algorithm_0012

サンプル

以下木構造の簡易的なサンプルです。
ノードの追加、検索方法などは簡単にしています。

	サンプル