コンピュータサイエンスやプログラミングを学んでいると、「木構造（ツリー構造）」という言葉に出会う機会は多いでしょう。
ファイルシステム・データベース・AIの意思決定ロジック・HTMLのDOM構造など、あらゆる場面で木構造が活用されています。
本記事では、木構造の意味とデータ構造としての基本について、階層構造・ノード・親子関係・ルート・リーフといったキーワードを交えながら、わかりやすく丁寧に解説していきます。
プログラミングを学んでいる方、アルゴリズムに興味がある方にとって、必ず役立つ基礎知識をお届けします。
ぜひ最後まで読み進めてください。
目次
木構造とは何か？結論からわかりやすく解説
それではまず、木構造という言葉の基本的な意味について解説していきます。
木構造（ツリー構造、英語：Tree structure）とは、データを階層的に表現するためのデータ構造で、ひとつの「根（ルート）」から始まり、枝のように広がっていく複数のノード（節点）と、それらをつなぐエッジ（辺）で構成された構造のことです。
現実世界の「木（樹木）」をイメージすると理解しやすく、根（ルート）から幹・枝が広がり、最終的に葉（リーフ）に至る、という構造がそのままデータ構造に対応しています。
木構造の最も重要な特性は「階層性」と「ループのなさ」です。階層性とは、データに「上下の関係（親子関係）」があることを意味します。ループのなさとは、ある節点から出発してたどっていったとき、同じ節点に戻ってくるルートが存在しないことを意味します。この2つの特性が、木構造をリスト・グラフといった他のデータ構造と区別する最も本質的な特徴です。
木構造は、コンピュータサイエンスにおける最も重要なデータ構造のひとつとして位置づけられており、多くのアルゴリズムやシステムの基盤として活用されています。
木構造の基本的な用語
木構造を理解するためには、いくつかの基本的な用語を知っておく必要があります。
【木構造の主な用語】
ノード（node） 木構造を構成する各要素（節点）。データを格納する基本単位
エッジ（edge） ノードとノードを結ぶ線（辺）。親子関係を表す
ルート（root） 木構造の最上位にある、唯一の根となるノード
親ノード 特定のノードに直接つながる上位のノード
子ノード 特定のノードに直接つながる下位のノード
リーフ（leaf） 子ノードを持たない末端のノード。葉ノードとも呼ばれる
深さ（depth） ルートからそのノードまでのエッジの数
高さ（height） ルートから最も遠いリーフまでのエッジの数
これらの用語は木構造を説明・プログラミングする際に必須の語彙です。
最初は覚えにくく感じるかもしれませんが、実際の木構造の図と照らし合わせながら確認することで、自然に身についていくでしょう。
木構造の視覚的なイメージ
木構造を視覚的にイメージするための具体例を見てみましょう。
会社の組織図を想像してみてください。
一番上に「社長」（ルートノード）がいて、その下に「各部門の部長」（子ノード）がいます。
各部長の下には「課長」が複数いて（孫ノード）、最終的に個々の「一般社員」（リーフノード）に至ります。
この会社の組織図のような「上位から下位へと広がる階層的な関係」を、データとして表現したものが木構造なのです。
ファイルシステム（フォルダとファイルの階層）、HTMLのDOMツリー（タグの入れ子関係）なども、木構造の典型的な現実例として挙げられます。
木構造の数学的な定義
より厳密には、木構造は以下の条件を満たすグラフとして数学的に定義されます。
| 条件 | 意味 |
|---|---|
| 連結性 | すべてのノードはエッジを通じてつながっている |
| 非循環性 | ループ（閉路）が存在しない |
| n-1本のエッジ | nノードの木構造には、必ずn-1本のエッジが存在する |
これらの数学的条件により、木構造の性質が明確に定義されており、アルゴリズムの設計・証明においても活用されます。
木構造の種類と代表的なバリエーション
続いては、木構造の代表的な種類とバリエーションについて確認していきます。
木構造には、用途に応じてさまざまな種類が存在します。
二分木（バイナリツリー）
最も基本的かつ重要な木構造のバリエーションが「二分木（Binary Tree）」です。
二分木とは、各ノードが最大2つの子ノード（左の子・右の子）しか持てないように制約された木構造のことです。
【二分木の主な種類】
完全二分木 すべてのリーフが同じ深さにある二分木
満二分木 すべてのノードが0個または2個の子ノードを持つ二分木
二分探索木（BST） 左の子が親より小さく、右の子が親より大きいという条件を満たす二分木
二分木は、様々なアルゴリズムの基礎となるデータ構造であり、特に二分探索木はデータの効率的な検索・挿入・削除のために広く使われています。
二分探索木（BST）の特性
二分探索木は、「左の子ノードの値は親ノードの値より小さく、右の子ノードの値は親ノードの値より大きい」という順序条件を常に維持するように構築された二分木です。
この条件があることで、探している値を根から出発して、値の大小を比較しながら左か右かを選択して下りていくだけで、効率的に検索ができます。
二分探索木のバランスが取れている場合、検索・挿入・削除の計算量はいずれも O(log n)（nはノード数）という高い効率性が実現されます。
多分木（N分木・多進木）
各ノードが2つ以上の子ノードを持てる木構造を「多分木（N分木、N-ary Tree）」と呼びます。
ファイルシステムのフォルダ構造・会社の組織図・HTMLのDOM構造など、現実世界の多くの階層構造は、子ノードの数に制限がない多分木として表現されます。
| 種類 | 特徴 | 主な用途 |
|---|---|---|
| 二分木 | 各ノードの子が最大2つ | 探索・ソート・ヒープ |
| 多分木（N分木） | 各ノードの子がN個まで | B木（データベース）・ファイルシステム |
| 一般木（順序なし） | 子の数に制限なし・順序なし | 組織図・カテゴリ構造 |
B木（Bツリー）と呼ばれる多分木は、データベースのインデックス構造として広く採用されており、大量データの効率的な検索・更新を支える重要なデータ構造のひとつとなっています。
木構造の走査（トラバーサル）
続いては、木構造に格納されたすべてのデータを順番に訪問する「走査（トラバーサル）」という操作について確認していきます。
木構造を正しく「読む」ための方法を理解することが、実装の理解につながります。
深さ優先探索（DFS）の3種類
木構造の走査方法として代表的なのが「深さ優先探索（DFS：Depth-First Search）」です。
DFSには訪問する順序によって、「前順（Pre-order）」「中順（In-order）」「後順（Post-order）」の3種類があります。
【DFSの3種類の走査順序（二分木の場合）】
前順（Pre-order） 根 → 左部分木 → 右部分木の順に訪問
中順（In-order） 左部分木 → 根 → 右部分木の順に訪問（二分探索木では昇順に訪問できる）
後順（Post-order） 左部分木 → 右部分木 → 根の順に訪問
特に二分探索木を「中順」で走査すると、格納されているデータが昇順に取り出されるという重要な性質があり、この性質を利用してソートアルゴリズムが実装されることがあるのです。
幅優先探索（BFS）
もう一つの重要な走査方法が「幅優先探索（BFS：Breadth-First Search）」です。
BFSでは、同じ深さのノードをすべて訪問してから、次の深さのノードに進む方式で走査します。
BFSは「レベル順」とも呼ばれ、根（深さ0）→深さ1のすべてのノード→深さ2のすべてのノード→…という順に訪問します。
最短経路の探索や、木全体を層ごとに処理する場面で、BFSは特に有効な走査方法です。
走査の計算量
木構造の走査（DFS・BFS）はどちらも、すべてのノードを1度ずつ訪問するため、計算量はO（n）（nはノードの総数）となります。
これは、どんな形の木であっても、全ノードを訪問するためにかかる時間はノード数に比例するということを意味しています。
木構造の実際の応用例
続いては、木構造が現実のシステム・プログラムでどのように活用されているのかを確認していきます。
理論的な理解と実際の応用を結びつけることで、木構造の重要性がより具体的に実感できます。
ファイルシステム・ディレクトリ構造
私たちが日常的に使うコンピュータのファイルシステムは、木構造の最も身近な例のひとつです。
「Cドライブ」や「ルートディレクトリ（/）」がルートノードであり、その下に「Users」「Windows」などのフォルダ（内部ノード）が続き、最終的に個々のファイル（リーフノード）に至る階層が形成されています。
木構造のデータ構造があるからこそ、フォルダの中にフォルダを入れる・特定のパスからファイルを探す・フォルダごと移動・削除するといった操作が、効率的に実装できるのです。
HTMLのDOMツリー
WebページはHTMLで記述されますが、ブラウザがHTMLを解析して内部的に構築するデータ構造も、木構造（DOMツリー）です。
「html」タグがルートノードとなり、「head」「body」タグが子ノード、さらにその中の「div」「p」「a」などのタグが孫ノード以降として配置された木構造が形成されます。
JavaScriptからDOMツリーを操作することで、Webページのコンテンツを動的に変更することができるのも、木構造がその基盤にあるためです。
機械学習の決定木
機械学習の代表的な手法のひとつ「決定木（Decision Tree）」も、その名の通り木構造を利用したアルゴリズムです。
各内部ノードで「ある特徴量が閾値以上か否か」という条件分岐を行い、リーフノードで最終的な予測結果（クラスや値）を出力するという構造を持っています。
決定木は、その構造が視覚的にわかりやすいため「解釈可能なAI（説明可能なAI）」として注目されており、医療・法務・金融など、判断の根拠を説明する必要がある分野で特に重視されているのです。
まとめ
本記事では、木構造の基本について、定義・主要な用語（ノード・エッジ・ルート・リーフ・深さ・高さ）・数学的な条件、二分木・二分探索木・多分木といった種類とその特性、DFSとBFSによる走査方法とその計算量、ファイルシステム・DOMツリー・決定木といった実際の応用例まで幅広く解説しました。
木構造とは、ルートノードから階層的に広がるノードとエッジの集合であり、親子関係による階層性とループのなさが最も重要な特性です。
二分木・二分探索木・多分木など、用途に応じた様々な種類があり、それぞれ異なる制約と活用場面を持ちます。
DFS・BFSという2つの走査方法により、木構造内のデータを系統的に処理することができます。
ファイルシステム・HTMLのDOM・決定木など、日常的に触れるシステムの多くが木構造を基盤としており、コンピュータサイエンスにおける最も基本的かつ重要なデータ構造のひとつとして、しっかりと理解しておくことをお勧めします。
