リーフノード【leaf node】葉ノード

概要

リーフノード（leaf node）とは、木のように枝分かれするデータ構造である木構造(ツリー)を構成する要素(ノード)のうち、それ以上先のない末端に位置するノードのこと。親ノードを持つが子ノードを持たない。

木構造とは一つの要素（ノード）が複数の子ノードを持ち、子ノードが複数の孫ノードを持ち…、という具合に階層が深くなるほど枝分かれしていくデータ構造で、これを根から幹や枝が伸びて分かれていき葉に至る木の形になぞらえている。

木の葉となる、末端に存在するノードがリーフノードで、一つの木には複数のリーフノードが存在することができる。木構造を図示する際には木を逆さまにしたように根を一番上に置き、下に向かって枝分かれするように描くため、実際の木の葉は上の方にあるが、リーフノードは木構造の「最下位」と形容されることもある。

木を構成するすべてのノードは、自分の子ノードの子ノードの…と下位に枝をたどっていくと最終的にはリーフノードに到達し、それ以上先にたどることはできない。リーフノード以外のノード群はすべて子ノードを持っており、総称して「内部ノード」（inner node）と呼ぶことがある。リーフノードとは逆に、木の根本（図上では頂点、最上位）にあり親ノードを持たないノードを「ルートノード」（root node）「根ノード」という。