はじめに: 木構造は「親子関係」を表すデータ構造
前の記事では、クイックソートを通じて、再帰や分割統治の考え方を見ました。今回扱う木構造も、再帰と深く関係するデータ構造です。
配列は、データを横一列に並べるイメージで理解できます。一方、木構造は、データが親子関係を持ちながら枝分かれしていく形です。
たとえば、フォルダの中にフォルダがあり、その中にさらにファイルがある構造を考えると分かりやすいです。会社の組織図、Webサイトのカテゴリ、コメントへの返信、HTMLのDOMも、木構造として見ることができます。
基本情報技術者試験では、木構造の用語や探索順が問われることがあります。実務でも、階層データを扱う場面は多いため、配列とは違う「枝分かれするデータ」の見方を知っておくと役立ちます。
木構造は、データ同士の親子関係や階層を表すための基本的なデータ構造です。
木構造の基本用語: 根・節・葉・親・子
木構造では、1つ1つの要素をノードと呼びます。日本語では節点と呼ばれることもあります。
木の一番上にあるノードをルートと呼びます。ルートは、階層全体の出発点です。フォルダでいえば、一番上のフォルダのようなものです。
あるノードの下につながっているノードを子と呼びます。逆に、子から見た上のノードを親と呼びます。子を持たない末端のノードはリーフと呼ばれます。日本語では葉とも呼ばれます。
会社
├─ 開発部
│ ├─ フロントエンドチーム
│ └─ バックエンドチーム
└─ 営業部この例では、会社 がルートです。開発部 と 営業部 は 会社 の子です。フロントエンドチーム と バックエンドチーム は 開発部 の子であり、末端なのでリーフと考えられます。
用語だけを見ると少し固く感じますが、要するに「どれが上で、どれが下か」「どこで枝分かれしているか」を表す言葉です。
木構造では、ノード同士の上下関係をルート、親、子、リーフといった用語で表します。
JavaScriptのオブジェクトで木を表す
JavaScriptでは、オブジェクトと配列を組み合わせると、木構造を素直に表せます。ここでは、カテゴリ階層を例にします。
const categoryTree = {
name: "プログラミング",
children: [
{
name: "JavaScript",
children: [
{ name: "配列", children: [] },
{ name: "再帰", children: [] },
],
},
{
name: "PHP",
children: [
{ name: "フォーム", children: [] },
{ name: "セッション", children: [] },
],
},
],
};この例では、各ノードが name と children を持っています。name はノードの名前、children は子ノードの配列です。
プログラミング がルートです。その子として JavaScript と PHP があります。さらに JavaScript の子として 配列 と 再帰 があります。
子を持たないノードでは、children が空の配列になっています。この形にしておくと、どのノードでも同じように children を確認できます。
JavaScriptでは、各ノードをオブジェクトで表し、子ノードを children の配列に入れると木構造を表現できます。
再帰で木をたどってみる
木構造は、再帰処理と相性がよいデータ構造です。なぜなら、あるノードを処理したあと、その子ノードにも同じ処理を行えばよいからです。
先ほどのカテゴリ階層に含まれる名前を、すべて表示してみます。
function printTree(node, depth = 0) {
const indent = " ".repeat(depth);
console.log(`${indent}${node.name}`);
for (const child of node.children) {
printTree(child, depth + 1);
}
}
printTree(categoryTree);このコードでは、まず現在のノード名を表示しています。次に、children に入っている子ノードを1つずつ取り出し、同じ printTree() を呼び出しています。
depth は階層の深さを表すために使っています。深い階層ほどインデントを増やすことで、出力結果でも親子関係が分かりやすくなります。
出力イメージは次のようになります。
プログラミング
JavaScript
配列
再帰
PHP
フォーム
セッションここでは明示的な if による停止条件を書いていません。children が空の配列なら、for 文の中身が実行されず、その関数呼び出しは自然に終わります。
木構造を再帰でたどると、現在のノードを処理し、子ノードにも同じ処理を行う流れになります。
深さ優先探索と幅優先探索の違い
木構造をたどる方法には、代表的なものとして深さ優先探索と幅優先探索があります。
深さ優先探索は、できるだけ奥へ進んでから戻る方法です。先ほどの printTree() は、子を見つけたらすぐその子の下へ進むため、深さ優先探索に近い動きです。
一方、幅優先探索は、同じ階層を先に見てから次の階層へ進む方法です。ルートを見たあと、ルートの子をすべて見て、その次に孫の階層を見るイメージです。
幅優先探索は、キューを使うと表しやすくなります。
function printTreeByLevel(root) {
const queue = [root];
while (queue.length > 0) {
const node = queue.shift();
console.log(node.name);
for (const child of node.children) {
queue.push(child);
}
}
}
printTreeByLevel(categoryTree);queue.shift() で先に入れたノードを取り出し、子ノードを後ろに追加しています。これは、キューの先入れ先出しの考え方です。
深さ優先探索は奥へ進む探索、幅優先探索は同じ階層を先に見る探索です。
試験ではどう問われるか
基本情報技術者試験では、木構造の用語や探索順が問われることがあります。
まず押さえたいのは、ルート、ノード、リーフ、親、子といった基本用語です。図を見て、どのノードが親で、どのノードが子かを読み取れることが大切です。
次に、探索順です。深さ優先探索では奥へ進み、幅優先探索では同じ階層を先に見ます。問題では、木の図が示されて「どの順番で訪問するか」を問われることがあります。
再帰、スタック、キューの知識ともつながります。深さ優先探索は再帰やスタックと相性がよく、幅優先探索はキューと相性がよいです。別々の用語として覚えるより、データ構造同士のつながりとして理解すると忘れにくくなります。
試験では、木構造の用語と、深さ優先探索・幅優先探索の訪問順を追えることが重要です。
実務ではどう使われるか
Web開発でも、木構造はよく登場します。代表的なのはHTMLのDOMです。HTMLでは、body の中に header や main があり、その中にさらに要素があります。この親子関係は木構造として見ることができます。
カテゴリ階層やメニューも木構造です。たとえば、商品カテゴリの中にサブカテゴリがあり、その下にさらに細かいカテゴリがある場合、配列だけで横一列に表すより、親子関係を持つデータとして扱うほうが自然です。
コメントへの返信が入れ子になるコメントツリー、ファイル一覧を表示するファイルツリー、管理画面の権限メニューなども、木構造の考え方で整理できます。
木構造を理解していると、階層データを表示する、特定のノードを探す、子要素をまとめて処理する、といった実装を考えやすくなります。
Web開発では、DOM、カテゴリ、メニュー、コメント、ファイル一覧など、階層を持つデータを扱う場面で木構造の考え方が役立ちます。
まとめ: 木構造は階層データを扱うための基本
木構造は、データ同士の親子関係を表すデータ構造です。配列のように横一列に並ぶデータではなく、枝分かれする階層を表したいときに使います。
JavaScriptでは、ノードをオブジェクトで表し、子ノードを children の配列に入れることで木構造を表現できます。さらに、再帰を使うと、現在のノードを処理しながら子ノードにも同じ処理を行えます。
深さ優先探索と幅優先探索は、木をたどる代表的な方法です。再帰、スタック、キューとつながるため、これまで学んだデータ構造を整理する題材にもなります。
木構造を理解すると、階層データを読み取り、表示し、探索する処理を考えやすくなります。
コメント