Шаг 13.
Динамические структуры данных в языке Prolog.
Деревья (общие сведения)

    На этом шаге мы рассмотрим определение деревьев и основные операции над ними .

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

    Узел дерева, не имеющий потомков, называется листом.

    Путь - это способ продвинуться от корня дерева к конкретной вершине.

    Высотой дерева называется наибольшая длина пути от корня к листу.

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

    Существует много способов представления бинарных деревьев на Прологе. Наиболее привычный способ: выбрать специальный символ для обозначения пустого дерева и функтор для построения непустого дерева из трех компонент: корня и двух поддеревьев. Сделаем следующий выбор: пусть атом nil представляет пустое дерево. В качестве функтора примем tr, так что дерево с корнем X, левым поддеревом L и правым поддеревом R будет иметь вид терма tr (L,X,R).

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

    В вершинах дерева может храниться информация любого типа. Например, в вершинах дерева располагаются целые числа. Соответствующее этому определению описание домена будет выглядеть следующим образом:

domains
     tre=tr(tre,integer,tre);nil
     /* дерево либо пусто, либо состоит из корня (целого числа), левого и правого
     поддеревьев, также являющихся деревьями */

    Обычно над деревьями выполняются следующие операции:

    Со следующего шага мы начнем рассматривать более подробно операции над деревьями.




Предыдущий шаг Содержание Следующий шаг