На этом шаге мы рассмотрим добавление вершины в дерево.
Создадим предикат, позволяющий добавить в бинарное дерево новое значение. При этом результирующее дерево должно получиться бинарным деревом. Предикат будет иметь три аргумента. Первым аргументом будет дерево, в которое нужно добавить данное значение, вторым - добавляемое значение, третьим - результат вставки.
Если вставлять любое значение в пустое дерево, то в результате получим дерево, у которого левое и правое поддеревья - пустые, а в корне записано добавляемое значение.
Если вставляемое значение совпадает со значением, находящимся в корневой вершине исходного дерева, то результат не будет отличаться от исходного дерева (в бинарном дереве все элементы различны).
Два правила рекурсии определяют, как нужно действовать, если исходное дерево непустое и его корневое значение отличается от вставляемого значения. В этой ситуации, если добавляемое значение меньше корневого, то его нужно добавить в левое поддерево, иначе - искать ему место в правом поддереве.
Запишем на Прологе реализацию этих рассуждений.
adlist (nil, X, tr (nil, X, nil)). /* вставляем X в пустое дерево, получаем дерево с X в корневой вершине, пустыми левым и правым поддеревьями */ adlist (tr (L, X, R), X, tr (L, X, R)). adlist (tr (L, K, R), X, tr (L1, K, R)):- X<K, adlist (L, X, L1). /* вставляем X в дерево с большим, чем X элементом в корневой вершине, значит, нужно вставить X в левое поддерево исходного дерева */ adlist (tr (L, K, R), X, tr (L, K, R1)):- X>K, adlist (R, X, R1). /* вставляем X в дерево с меньшим, чем X элементом в корневой вершине, значит, нужно вставить X в правое поддерево исходного дерева */
На следующем шаге мы рассмотрим удаление вершины из дерева.
