二分木 【binary tree】 バイナリツリー / 2分木

概要

解説 木構造はグラフ構造のうち要素に親子関係があり、親が複数の子を持つことができるようなものを意味し、根ノード（root node）を頂点として階層的に枝分かれしていく構造となる。

二分木はこのうち、どの親ノードも子ノードを一つか二つしか持たないという制限が課せられたものを指し、図示したときに左側にあるものを左ノード、右にあるものを右ノードという。子は一つのみの場合もあり、子がないノードは末端の葉ノード（leaf node）となる。

全二分木/完全二分木 (full binary tree/perfect binary tree)

二分木のうち、（子のない葉ノードを除く）子を持つノードの子の数がすべて二個ずつであるようなものを「全二分木」（full binary tree）、全二分木のうちすべての葉ノードの深さが揃っているものを「完全二分木」（perfect binary tree）という。

また、最下層を除いてすべての深さがノードで満たされ、最下層の葉ノードが可能な限り左に寄せられているような木を “complete N-ary tree” と呼び、これを完全二分木とすることもある。