1 基本定義
1.1 リーフノードとは
リーフノード（英: leaf node）とは、ツリー構造（木構造）において子ノードを一切持たない末端のノードを指す。どのノードからも子が存在しない状態であり、木の階層構造における最下層に位置する。データ構造やアルゴリズムの文脈では、再帰的な処理の終端条件として頻繁に利用される。例えば二分木の場合、左右の子ポインタがともにNULLであるノードがリーフノードである。
1.2 内部ノードとの違い
内部ノード（internal node）は1つ以上の子ノードを持つノードであり、リーフノードと対比される。内部ノードはデータの分岐や集約を担うのに対し、リーフノードは実際のデータ値や結果を保持する末端として機能する。木の構造上、根（ルート）が内部ノードであることもあれば、木全体が1ノードだけの場合は根自身がリーフノードとなる。この区別は探索やソート、決定木など様々なアルゴリズムで重要な役割を果たす。
1.3 用語の由来（木の葉の比喩）
「リーフ」は英語で「葉」を意味し、実際の植物の木における葉が枝の先端に生える様子に例えられている。木の根から幹、枝と分岐し、最終的に葉に到達するように、ツリー構造でも根から枝分かれを繰り返した末端がリーフノードである。この比喩は親しみやすく、データ構造の教育現場でも直感的な理解を助けるために広く使われている。
2 データ構造におけるリーフノード
2.1 二分探索木
二分探索木（Binary Search Tree, BST）では、各ノードが最大2つの子を持ち、左の子孫は自身より小さな値、右の子孫は大きな値を格納する。リーフノードは子を持たない末端であり、挿入や探索の終点となる。
2.1.1 探索と挿入における役割
探索では、目的の値とノードの値を比較しながら木を下降し、リーフノードに到達しても一致しない場合はその値が木に存在しないと判断する。挿入では、リーフノードの位置を見つけた後、そこに新たなノードを子として追加する。このためリーフノードは探索・挿入の終端条件として不可欠である。
2.2 B木とB+木
B木やB+木は、ディスクI/Oを意識した多分木であり、リーフノードはすべてのデータエントリを保持する。B木ではリーフノードもキーとデータを格納するが、B+木では内部ノードはキーのみを保持し、実際のデータはすべてリーフノードに集約される。
2.2.1 B+木のリーフリンクリスト
B+木のリーフノードは、同じ階層で双方向リンクリスト（または片方向リスト）により連結されることが多い。これにより、範囲検索や順次アクセスが効率的に行える。リーフリンクリストはデータベースのインデックス構造で頻繁に利用され、リーフノード同士のポインタが全データの走査を可能にする。
2.3 ヒープ
ヒープは完全二分木の一種で、優先度キューとして使われる。ヒープではすべてのノードが最大（または最小）ヒープ条件を満たすよう構成される。
2.3.1 ヒープの葉と再構築
ヒープのリーフノードは、配列表現では末尾付近に位置する。要素の挿入や削除（ポップ）の際、ヒープの再構築（ヒープ化）ではリーフから内部へとバブルアップやバブルダウンを行う。特にバブルダウンでは、リーフに達するまで子との比較を繰り返すため、リーフは再構築の終点として機能する。
3 応用分野
3.1 機械学習の決定木
決定木は、特徴量に基づいてデータを分類または回帰する機械学習モデルである。内部ノードで条件分岐を行い、リーフノードで最終的な予測結果を出力する。
3.1.1 分類・回帰リーフ
分類木のリーフノードは、到達したデータの属するクラスを表す。回帰木のリーフノードは、目的変数の平均値などの実数値を保持する。リーフノードの値は学習データから統計的に決定される。
3.1.2 枝刈りとリーフ数調整
決定木が過学習を防ぐために行う枝刈り（pruning）では、リーフノードの数を制限する。リーフ数が多すぎるとモデルが複雑になり過学習しやすいため、交差検証などを用いて最適なリーフ数を調整する。リーフノードはモデルの複雑さを直接反映する指標でもある。
3.2 ファイルシステム
ファイルシステムにおけるディレクトリ構造はツリーとして表現できる。各ディレクトリは内部ノード、ファイルはリーフノードに相当する。
3.2.1 ディレクトリツリーのリーフファイル
ディレクトリツリーでは、ファイルが子を持たない末端であるため、すべてのファイルがリーフノードとなる。ただし、シンボリックリンクやディレクトリ自体が空の場合は例外もあるが、原則としてファイルがリーフである。OSのパス探索では、リーフノードに到達した時点で対象ファイルにアクセスできる。
3.3 構文解析木（AST）
抽象構文木（AST）は、プログラミング言語のソースコードを木構造で表現する。内部ノードは演算子や制御構造、リーフノードは識別子やリテラルなどのトークンに対応する。
3.3.1 トークンとリーフノード
ASTのリーフノードは、プログラム上の最小単位であるトークン（数値、変数名、キーワードなど）を保持する。例えば式「a + 3」では、識別子「a」と数値「3」がリーフノード、加算演算子「+」が内部ノードとなる。コンパイラやインタプリタは、リーフノードから値を取得して計算を進める。
3.4 ゲーム木（将棋・チェスAI）
ゲーム木は、チェスや将棋などの二人零和有限確定完全情報ゲームの探索に用いられる。木の各ノードは盤面の状態を表し、辺は合法手を示す。
3.4.1 評価値とリーフの終端条件
ゲーム木では、リーフノードはゲーム終了状態（チェックメイトや引き分け）または深さ制限に達したノードを指す。AIはリーフノードで評価関数（静的評価）を計算し、その値を内部ノードにミニマックス法などで伝播する。リーフの終端条件の設定は探索効率と精度に直結する。
4 数学的・グラフ理論的性質
4.1 木の定義と次数
グラフ理論において、木は連結で閉路のない無向グラフである。ノードの次数（次数）は接続する辺の数で定義され、リーフノードの次数は1（根がリーフの場合は0）となる。一般に、次数1のノードが葉である。
4.2 葉の個数に関する定理（葉数＝内部ノード数＋1 など）
任意の有限木において、葉の数 L、内部ノード数 I の間に以下の関係が成り立つ（ただし根を含む全ノード数 n = L + I）。辺の数は n - 1 であり、各辺が次数に寄与することから、次数の総和 = 2(n - 1) より、L = I + 1 という公式が導かれる。これは完全二分木でなくとも成立する一般的な定理である。
4.3 完全二分木における葉の数
完全二分木（Full Binary Tree）では、すべての内部ノードがちょうど2つの子を持つ。このとき、葉の数 L と内部ノード数 I の関係は L = I + 1 となる。また、深さ d の完全二分木（根を深さ0とする）では、葉の数は 2^d である。完全二分木はヒープなどで重要な性質を持つ。
5 関連する概念と発展
5.1 リーフノードの計算量（DFS/BFSでの訪問順）
深さ優先探索（DFS）や幅優先探索（BFS）において、リーフノードは探索の到達点となる。DFSでは先にリーフに達した後バックトラックするため、リーフノードの訪問順は木の構造に依存する。BFSではリーフノードは最も遠い層に位置し、キューを用いて順次訪問される。いずれの探索でもリーフノードの処理は探索アルゴリズムの計算量解析の基本となる。
5.2 ネットミーム・比喩的用法
5.2.1 「木の葉のように散る」？
元の植物の比喩とは逆に、インターネット上では「リーフノードは木の葉のように散る」というミームが散見される。これは、システムの末端ノードが負荷分散や障害で頻繁に消えたり追加されたりする様子を、落ち葉に例えたユーモアである。実際のデータ構造ではリーフノードが頻繁に変更される状況（例えばファイルの作成削除）と重なるため、一部で親しまれている。
5.2.2 ユーモア：リーフノードは孤独説
「リーフノードは子を持たず、孤独である」という比喩が、プログラマ間のジョークとして語られることがある。内部的には子を持たないが、親ノードや兄弟ノードとつながっているため厳密には孤独ではないが、末端であるがゆえの寂しさを擬人化したものである。ネット上では「リーフノードに友達を（木構造の操作で）作ってあげよう」といった冗談も見られる。
5.3 逆概念：ルートノード、内部ノード、兄弟ノード
リーフノードと対になる概念として、ルートノード（根）、内部ノード（非葉ノード）、兄弟ノード（同じ親を持つノード）がある。ルートノードは木の頂点であり、内部ノードは子を持つ中間ノード、兄弟ノードは同じ階層で親を共有する。これらはツリー構造の基本用語として、リーフノードの位置づけを明確にする。特に内部ノードとリーフノードの区別は、再帰的アルゴリズムの実装で頻繁に用いられる。