Упорядоченность двоичного дерева, Алгоритм - Исследование и программная реализация алгоритмов теории графов

Если x - это произвольная вершина в двоичном дереве поиска, а вершина y находится в левом поддереве вершины x, то y. key<= x. key. Если x - это произвольная вершина ДДП, а вершина y находится в правом поддереве вершины x, то y. key>= x. key. Из свойства следует, что если y. key == x. key, то вершина y может находиться как в левом, так и в правом поддереве относительно вершины x.

Алгоритм

Построение двоичного дерева поиска на основе исходного неотсортированного списка a1, a2, ..., aNРеализуется на основе следующего алгоритма:

    1 Для множества, состоящего лишь из одного элемента aI (n=1), a1 просто представляет собой корень, в свою очередь деревоT1 представляет собой дерево сортировки с одним единственным элементом a1, который является вершиной этого дерева; увеличиваем nдо n+1. 2 Если n>N, где, тогда процедура заканчивается. В противном случае сравниваем aNС корнем.

Если aN?корня, то переходим к левому поддереву.

Если левое поддерево пусто, то добавляем aNВ качестве левого потомка корня, чтобы формировать следующее дерево сортировки TN; увеличиваем nдо n+1 и повторяем шаг 2;

В противном случае повторяем шаг 2, использую левое поддерево.

В противном случае переходим к правому поддереву.

Если правое поддерево пусто, тогда добавляем aN в качестве правого потомка корня, чтобы образовать следующее дерево сортировки TN; увеличиваем n до n+1 и повторяем шаг 2;

В противном случае повторяем шаг 2, используя правое поддерево.

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

    1 Обрабатываем левое поддерево; 2 Вносим в список корень; 3 Обрабатываем правое поддерево.

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

2. Решение задачи

Похожие статьи




Упорядоченность двоичного дерева, Алгоритм - Исследование и программная реализация алгоритмов теории графов

Предыдущая | Следующая