「分かりそう」で「分からない」でも「分かった」気になれるIT用語辞典

順番に見ていきましょう。
まずは予備知識として「ツリー構造（木構造）」について簡単に説明します。
「そんなの説明されなくても知ってるよ！」な人は適当に読み飛ばしてください。

ツリー構造（木構造）は「1つの親に対して複数の子を持つ、枝分かれして広がっていく構造」です。
上から下に広がっていく形で図を書くと、木を上下逆さまに見たような形になります。



それを踏まえて

ツリー構造のうち、枝分かれが最大2つのもの

が「2分木」です。
「最大2つに分かれる木構造」だから「2分木」なんでしょうかね。



2分木を構成する要素は

１．入ってくるのがなくて、出ていくのが2つ



２．入ってくるのが1つで、出ていくのが2つ



３．入ってくるのが1つで、出ていくのが1つ



４．入ってくるのが1つで、出ていくのがない



の4つです。



１が枝分かれのスタートです。
２と３が枝分かれの途中です。
４が枝分かれの最後になります。

また、2分木の中でも、特に

１．すべての枝分かれが2つ
２．すべての枝分かれの先っぽが最初の地点から同じ距離

ものを「完全2分木」と言います。



先ほど、2分木の要素は

１．入ってくるのがなくて、出ていくのが2つ
２．入ってくるのが1つで、出ていくのが2つ
３．入ってくるのが1つで、出ていくのが1つ
４．入ってくるのが1つで、出ていくのがない

の4つだと説明しました。



この2分木の要素のうち

（１）３の要素がない



（２）１から４に到着するまでの２の数が全部同じ



になっている2分木が完全2分木です。

気が向いたら、一緒に覚えてあげてください。