Деревья (нелинейные структуры данных)

Дерево состоит из элементов, называемых узлами. Каждый узел имеет оригинальный ключ (как правило, это целое число), данные и поля ссылки. Т.е. каждый узел может ссылаться на другие узлы и если X®Y узел X называется предком (родителем), а Y - потомком (сыном) или дочерним узлом. Одинаковые ключи здесь не допускаются.

Дерево имеет единственный узел, у которого нет предков. Такой узел называют корнем дерева. Любой другой узел имеет ровно одного предка. Узел, не имеющий потомков, называется листом.

Внутренний узел – это узел, не являющийся ни листом ни корнем.

Бинарное дерево - это дерево, состоящее из узлов, ка­ждый из которых содержит не более двух ссылок на различные бинарные поддеревья, т.е. у каждого его узла (предка) может быть не более двух потомков - левый и правый. Таким образом, на каждый узел бинарного дерева имеется ровно одна ссылка.

На рисунке приведен пример бинарного дерева (корень обычно изображается сверху, хотя изображение можно и перевернуть).

Если дерево организовано так, что для каждого узла все ключи его ле­вого поддерева меньше ключа этого узла, а все ключи его правого поддерева - больше, оно называется деревом поиска.

Обычно бинарное дерево строится сразу упорядоченным, т.е. ключ узла левого сына имеет значение меньшее, чем значение ключа у родителя, а узел правого сына - большее.

Например, если приходят числа 17, 18, 6, 5, 9, 23, 12, 7, 8, то построенное по ним дерево будет выглядеть следующим образом (для упрощения приводим только ключи):

Существуют три алгоритма обхода деревьев, которые естественно следуют из самой структуры дерева.

1) Обход слева направо: Left-Root-Right: сначала посещаем левое поддерево, затем - корень и, наконец, правое поддерево.

(Или наоборот, справа налево: Right -Root- Left)

2) Обход сверху вниз: Root-Left-Right: посещаем корень до поддеревьев.

3) Обход снизу вверх: Left-Right-Root: посещаем корень после поддеревьев

Иллюстрация алгоритмов обхода деревьев приведена в теме «Построение обратной польской записи»