9.3. Деревья

Я не увижу никогда, наверное,

Поэму столь прекрасную как дерево.

Джойс Килмер, «Деревья»^[11]

В информатике идея дерева считается интуитивно очевидной (правда, изображаются они обычно с корнем наверху, а листьями снизу). И немудрено, ведь в повседневной жизни мы постоянно сталкиваемся с иерархическими данными: генеалогическое древо, организационная схема компании, структура каталогов на диске.

Терминология, описывающая деревья, богата, но понять ее легко. Элементы дерева называются узлами; верхний или самый первый узел называется корневым или корнем. У узла могут бытьпотомки, расположенные ниже него, а непосредственные потомки называются детьми или дочерними узлами. Узел, не имеющий потомков, называется листовым или просто листом. Поддерево состоит из некоторого узла и всех его потомков. Посещение всех узлов дерева (например, с целью распечатки) называется обходом дерева.

Нас будут интересовать в основном двоичные деревья, хотя в принципе узел может иметь произвольное число детей. Мы покажем, как создавать дерево, добавлять в него узлы и выполнять обход. Рассмотрим также некоторые реальные задачи, при решении которых используются деревья.

Отметим, что во многих языках, например в С или Pascal, деревья реализуются с помощью адресных указателей. Но в Ruby (как и в Java) указателей нет, вместо них используются ссылки на объекты, что ничуть не хуже, а иногда даже лучше.