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

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

Дерево состоит из узлов и связей между ними (они называются дугами). Самый первый узел, расположенный на верхнем уровне (в него не входит ни одна стрелка-дуга), — это корень дерева. Конечные узлы, из которых не выходит ни одна дуга, называются листьями. Все остальные узлы, кроме корня и листьев, — промежуточные.

Из двух связанных узлов тот, который находится на более высоком уровне, называется родителем, а другой — сыном. Корень — это единственный узел, у которого нет родителя; у листьев нет сыновей.

Используются также понятия предок и потомок. Потомок какого-то узла — это узел, в который можно перейти по стрелкам от узла-предка. Соответственно, предок какого-то узла — это узел, из которого можно перейти по стрелкам в данный узел.

В дереве на рисунке ниже родитель узла Е — это узел В, а предки узла Е — это узлы А я В, для которых узел Е — потомок. Потомками узла А (корня) являются все остальные узлы.

Типичный пример иерархии — различные классификации (животных, растений, минералов, химических соединений). Например, отряд Хищные делится на два подотряда: Псообразные и Кошкообразные. В каждом из них выделяют несколько семейств.

Конечно, на рисунке показаны не все семейства, остальные обозначены многоточиями.

В текстах иерархию часто представляют в виде многоуровневого списка. Например, оглавление книги о хищниках может выглядеть так:

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

В современных файловых системах (NTFS, ext3) файл может «принадлежать» нескольким каталогам одновременно. При этом древовидная структура, строго говоря, нарушается.

СТРУКТУРНОЕ ПРЕДСТАВЛЕНИЕ ЧИСЕЛ.

Алгоритм вычисления арифметического выражения тоже может быть представлен в виде дерева.

(а + 3) * 5 - 2 * b

Здесь листья — это числа и переменные, тогда как корень и промежуточные вершины — знаки операций. Вычисления идут «снизу вверх», от листьев — к корню. Показанное дерево можно записать так:

(-(*(+ (а,3),5),*(2,b)))

Самое интересное, что скобки здесь необязательны; если их убрать, то выражение всё равно может быть однозначно вычислено:

- * + а 3 5 * 2 b

Такая запись, которая называется префиксной (операция записывается перед данными), просматривается с конца. Как только встретится знак операции, эта операция выполняется с двумя значениями, записанными справа.

В рассмотренном выражении сначала выполняется умножение:

- * + а 3 5 (2 * b)

затем — сложение:

- * (а + 3) 5 (2 * b)

и ещё одно умножение:

- (а + 3) * 5 (2*b)

и наконец, вычитание:

(а + 3) * 5 - (2 * b)

Для получения префиксной записи мы обходили все узлы дерева в порядке «корень — левое поддерево — правое поддерево». Действительно, сначала записана метка корня («-»), затем все метки левого поддерева, а затем — все метки правого поддерева. Для поддеревьев используется тот же порядок обхода. Если же обойти дерево в порядке «левое поддерево — правое поддерево — корень», получается постфиксная форма (операция после данных). Например, рассмотренное выше выражение может быть записано в виде

а З + 5 * 2 b * -

Для вычисления такого выражения скобки также не нужны, и это очень удобно для автоматических расчётов. Когда программа на языке программирования высокого уровня переводится в машинные коды, часто все выражения записываются в бесскобочной постфиксной форме и именно так и вычисляются. Постфиксная форма для компьютера удобнее, чем префиксная, потому что, когда программа доходит до знака операции, все данные для выполнения этой операции уже готовы.