На этом шаге мы рассмотрим определение деревьев и основные операции над ними .
Бинарное дерево (binary tree) - это упорядоченное дерево, каждая вершина которого имеет не более двух
поддеревьев, причем для каждого узла выполняется правило: в левом поддереве содержатся только
элементы, имеющие значения, меньшие, чем значение данного узла, а в правом поддереве содержатся
только элементы, имеющие значения, большие, чем значение данного узла.
Узел дерева, не имеющий потомков, называется листом.
Путь - это способ продвинуться от корня дерева к конкретной вершине.
Высотой дерева называется наибольшая длина пути от корня к листу.
Бинарное дерево является рекурсивной структурой, поскольку каждое его поддерево само является бинарным деревом и, следовательно, каждый его узел в свою очередь является корнем дерева.
Существует много способов представления бинарных деревьев на Прологе. Наиболее привычный способ: выбрать специальный символ для обозначения пустого дерева и функтор для построения непустого дерева из трех компонент: корня и двух поддеревьев. Сделаем следующий выбор: пусть атом nil представляет пустое дерево. В качестве функтора примем tr, так что дерево с корнем X, левым поддеревом L и правым поддеревом R будет иметь вид терма tr (L,X,R).
Нам будет удобно использовать следующее рекурсивное определение бинарного дерева: дерево либо пусто, либо состоит из корня, а также левого и правого поддеревьев, которые в свою очередь также являются деревьями.
В вершинах дерева может храниться информация любого типа. Например, в вершинах дерева располагаются целые числа. Соответствующее этому определению описание домена будет выглядеть следующим образом:
domains
tre=tr(tre,integer,tre);nil
/* дерево либо пусто, либо состоит из корня (целого числа), левого и правого
поддеревьев, также являющихся деревьями */
Обычно над деревьями выполняются следующие операции:
- формирование дерева;
- поиск вершины в дереве;
- добавление вершины в дерево;
- удаление вершины из дерева.
Со следующего шага мы начнем рассматривать более подробно операции над деревьями.
