データ構造について

言語の説明に入る前に、まず木、特に 二分木 と呼ばれるデータ構造について説明します。

木構造

以下の図を見てください。

二分木

このマルのひとつひとつを、節（node）といいます。節同士は、枝（edge）でつながっています。

ひとつの節から下に向けて、いくつかの節がつながっています。この上側の節を親（parent）、下側の節を子（child）といいます。

一番上の節を根（root）、末端のそれぞれの節を葉（leaf）といいます。

このように、ひとつの節（根）からいくつかの子、さらにそれらの子、……とつながっていく構造を木（tree）といいます。（上下逆に見ると木に見えることから）

二分木（binary tree）は、木の中でも、「ひとつの節は子を２つまでしか持てない」という制約のあるものです。

今回は子の左右が重要なので、左側に生えている子を「左の子」、右側に生えている子を「右の子」、と呼ぶことにします。

親と子

木は再帰的な構造を持ちます。

まず、節がただひとつのみある場合でも、木です。

さらに、ある節の左側や右側、あるいは両方に木を子としてつければ、それもまた木になります。

こうして再帰的に木を定義することができます。この性質は木を調べるときにも役立ちます。

根から一番遠い葉までの枝の数を高さ（height）といいます。