【基本情報技術者試験】木構造

本記事では基本情報技術者試験にも出題される木構造について解説しています。目次は以下の通りです。

木構造とは

木構造とは木のような階層構造を持つデータ構造を指します。
木構造は、節(ノード)と枝(ブランチ)で構成され、根(ルート)から始まり葉(リーフ)で終わります。
節同士には親子関係があり、上の節を親、下の節を子と呼びます。図で表すと以下のようになります。

上の図の場合、A～Hすべてが節でそれをつないでいる線を枝といいます。Aが根で、D,E,F,G,Hが葉です。また、Bを基準にみると、AはBの親であり、DとEはBの子といえます。
階層的な関係で階層が形成され、効率的なデータ追加や取得が可能です。二分木や探索木など、特定目的の特化した木構造も存在します。

木の構造の例

木の構造の例は以下の2つがあります。
・2分木
・多分木

2分木

2分木は各枝の分岐が2つ以下であり、親が最大2つの子を持つ木の一種です。

多分木

多分木は2分木と異なり、各枝の分岐が3つ以上を持つ木の一種です。図的には以下のようになります。

Cを見ると子がF,G,Hとなることからこれは多分木といえます。

まとめ

本記事のポイントを以下にまとめます。