ツリー構造の基本
ツリー構造とは
前回まで学習してきたデータ構造である、配列やリスト，スタック，キューは、主に同じような複数のデータを表す場合に有効です。しかし、これらのデータ構造は、階層をもつデータの集まりを表すことはを苦手としています。そこで用いられるのが、これから説明するツリー構造です。
ツリー構造とは、文字通り、木（tree)のような形状をしたデータ構造です。ただ、ただ、通常の木と違うのは、図示した場合、上下が逆転しているてんでしょう。図を見ればわかるとおり、樹木の値にあたる部分から、データが枝分かれして、上下を逆転すれば、あたかも木のような構造になっています。
ツリー構造の仕組み
ツリー構造の実際
では、実際に、ツリー構造が実際にどのような構造になっているのかを詳しく見てみましょう。(図4-1.参照)
図3-1.ツリー構造
ルート
この構造のうち、木の根にあたるものを、ルート(root)と言います。文字通り「根」といういみを表すこの言葉は、すべてのデータの出発点になっています。
ノードとリーフ
さらに、ツリーの枝分かれ部分のことを、ノード(node)、と言います。ノードとは木の節（ふし）を表す言葉で、ノードとノードの接続のことを、ブランチ(brunch)と言います。これは、木の枝を表す言葉であり、このように、ツリー構造の用語は、樹木に由来するものであることが分かります。
ノードの親子関係
また、ブランチで結ばれているノードどうしは、「親子関係」にあるという言い方をします。このうち、ルートに近いほうを、親ノード(parent node)、遠い方を、子ノード(child node)と言います。また、同じ親を持つ子ノードのことを、兄弟ノード(sibling node)と言います。
以上の、ツリー構造に関する用語をまとめると、以下のようになります。
| 用語 | 英語 | 内容 |
|---|---|---|
| ノード | node | ツリー構造のなかのデータ。 |
| ブランチ | brunch | ノードとノードとのつながり。 |
| ルート | root | ツリー構造のノードのうち、最上位のもの |
| 親ノード | parent node | ブランチで結ばれたノード同士のうち、上位のもの |
| 子ノード | child node | ブランチで結ばれたノード同士のうち、下位のもの |
二分木とヒープ構造
探索に用いられる二分木
ツリー構造のうち、特に、子どものノードが最大2つのようなものを二分木（にぶんぎ=binary tree(バイナリ・ツリー)） と言います。二分木は、主に探索アルゴリズムでよく用いられる特殊なツリー構造です。
図3-2.二分木
ヒープ構造
二分木の各節点にデータを保持し、親のデータが2つの子のデータよりも小さくなるように作られたデータ構造のことを、ヒープ構造と言います。この構造は、ソートアルゴリズムの一種である、ヒープソートでよく用いられる構造です。図3-2.の二分木構造は、ヒープ構図になっていることがわかります。
 |  |  |
