Основные алгоритмы работы с бинарным деревом

В общем случае при работе с такими структурами необходимо уметь:

– построить (создать) дерево;

– вставить новый элемент;

– обойти все элементы дерева, например, для просмотра или выполнения некоторой операции;

– выполнить поиск элемента с указанным значением в узле;

– удалить заданный элемент.

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

 

Формирование дерева

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

Вставка нового элемента

Для того чтобы вставить новый элемент в дерево, необходимо найти для него место. Для этого, начиная с корня, сравниваем значения узлов (Tree-> info) со значением нового элемента (b). Если b < info, то идем по левой ветви, в противном случае – по правой ветви. Когда дойдем до узла, из которого не выходит нужная ветвь для дальнейшего поиска, это означает, что место под новый элемент найдено.

Путь поиска места в построенном дереве для числа 11:

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

Tree* Make(Tree *Root) {

Tree *Prev, *t; // Prev родитель (предыдущий) текущего элемента

int b, find;

if ( Root == NULL ) { // Если дерево не создано

printf(" \n Input Root: " );

scanf(“%d”, & b);

Root = List(b); // Установили указатель на корень

}

//================ Добавление элементов =================

while(1) {

printf(" \n Input Info: " ); scanf(“%d”, & b);

if (b< 0) break; // Признак выхода число < 0

t = Root; // Текущий указатель на корень

find = 0; // Признак поиска

while ( t & & ! find) {

Prev = t;

if( b == t-> info)

find = 1; // Ключи должны быть уникальны

else

if ( b < t -> info ) t = t -> Left;

else t = t -> Right;

}

if (! find) { // Нашли место с адресом Prev

t = List(b); // Создаем новый узел

if ( b < Prev -> info ) // и присоединяем его, либо

Prev -> Left = t; // на левую ветвь,

else Prev -> Right = t; // либо на правую ветвь

}

} // Конец цикла

return Root;

}

Функция List предназначена для создания нового элемента – листа:

Tree* List(int i) {

Tree *t = (Tree*) malloc (sizeof(Tree));

t -> info = i;

t -> Left = t -> Right = NULL;

return t;

}

Участок кода с обращением к функции Create будет иметь следующий вид:

¼

struct Tree { // Декларация шаблона

int info;

Tree *Left, *Right;

};

void main()

{

Tree *Root = NULL; // Указатель корня

¼

Root = Make(Root);

¼

Удаление узла

При удалении узла из дерева возможны три ситуации в зависимости от того, сколько сыновей (потомков) имеет удаляемый узел.

1. Удаляемый узел является листом – просто удаляем ссылку на него. Приведем пример схемы удаления листа с ключом key:

2. Удаляемый узел имеет только одного потомка, т.е. из удаляемого узла выходит ровно одна ветвь. Пример схемы удаления узла key, имеющего одного сына:

3. Удаление узла, имеющего двух сыновей, значительно сложнее рассмотренных выше. Если key – удаляемый узел, то его следует заменить узлом w, который содержит либо наибольший ключ (самый правый, у которого указатель Right равен NULL) в левом поддереве, либо наименьший ключ (самый левый, у которого указатель Left равен NULL) в правом поддереве.

Используя первое условие, находим узел w, который является самым правым узлом поддерева key, у него имеется только левый сын:

В построенном ранее дереве удалим узел key (6). Используем второе условие, т.е. ищем самый левый узел в правом поддереве – это узел w (указатель Left равен NULL):

 

Функция удаления узла по заданному ключу key может иметь вид

Tree* Del(Tree *Root, int key) {

Tree *Del, *Prev_Del, *R, *Prev_R;

// Del, Prev_Del – удаляемый элемент и его предыдущий (родитель);

// R, Prev_R – элемент, на который заменяется удаленный, и его родитель;

Del = Root;

Prev_Del = NULL;

// ===== Поиск удаляемого элемента и его родителя по ключу key =====

while (Del! = NULL & & Del -> info! = key) {

Prev_Del = Del;

if (Del-> info > key) Del = Del-> Left;

else Del = Del-> Right;

}

if (Del == NULL) { // Элемент не найден

puts(" \n NO Key! " );

return Root;

}

// ============ Поиск элемента R для замены =================

if (Del -> Right == NULL) R = Del-> Left;

else

if (Del -> Left == NULL) R = Del-> Right;

else {

// Ищем самый правый узел в левом поддереве

Prev_R = Del;

R = Del-> Left;

while (R-> Right! = NULL) {

Prev_R = R;

R = R-> Right;

}

// Нашли элемент для замены R и его родителя Prev_R

if( Prev_R == Del)

R-> Right = Del-> Right;

else {

R-> Right = Del-> Right;

Prev_R-> Right = R-> Left;

R-> Left = Prev_R;

}

}

if (Del== Root) Root = R; // Удаляя корень, заменяем его на R

else

// Поддерево R присоединяем к родителю удаляемого узла

if (Del-> info < Prev_Del-> info) Prev_Del-> Left = R; // на левую ветвь

else Prev_Del-> Right = R; // на правую ветвь

printf(" \n Delete element %d \n", Del-> info);

free(Del);

return Root;

}

Участок программы с обращением к данной функции будет иметь вид

¼

printf(" \n Input Del Info: " );

scanf(“%d”, & key);

Root = Del(Root, key);

¼

 

Алгоритмы обхода дерева

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

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

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

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

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

Пусть для операндов А и В выполня­ется операция сложения. Привычная форма записи в виде А+В называется ин­фиксной. Форма записи, в которой знак операции следует перед операндами +АВ, называется префиксной, если же операция записывается после операндов АВ+ – постфиксной.

Рассмотрим небольшой пример, пусть задано выражение А+В*С. Так как умножение имеет более высокий приоритет, то данное выражение можно переписать в виде А+(В*С). Для записи выражения в постфиксной форме сначала преобразуем ту часть выражения, которая вычисляется первой, в результате получим: А+(ВС*).

Теперь запишем в постфиксной форме операцию сложения между операндами А и (ВС*): АВС*+.

Таким образом, выражение А+В*С в постфиксном виде АВС*+, префиксная форма записи будет иметь вид +*АВС.

Рассмотрим различные обходы дерева на примере формулы: ((a+b/c)*(d–e*f )). Дерево формируется по принципу:

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

– далее узлы-операции, операнды – листья дерева.

Обход 1 (Left-Root-Right) дает обычную инфиксную запись выражения (без скобок):

a + b / c * d – e * f.

Обход 2 (Root-Left-Right) – префиксную запись выражения (без скобок):

* + a / b c – d * e f.

Обход 3 (Left-Right-Root) – постфиксную запись выражения:

a b c / + d e f * – *.

Функция просмотра

Приведем простой пример функции вывода элементов (ключей) дерева, использующий правила обхода 2.

void View ( Tree *t, int level ) {

if ( t ) {

View ( t -> Right, level+1); // Вывод правого поддерева

for ( int i=0; i< level; i++) printf(" " );

printf(“ %d\n”, t -> info);

View( t -> Left, level+1); // Вывод левого поддерева

}

}

Обращение к функции View будет иметь вид View(Root, 0);

Функция View рекурсивная, вторым ее параметром является переменная, определяющая, на каком уровне (level) находится узел. Корень находится на уровне «0». Значения узлов выводятся по горизонтали так, что корень находится слева. Перед значением узла для имитации структуры дерева выводится количество пробелов, пропорциональное уровню узла. Если закомментировать цикл печати пробелов, значения ключей будут выведены просто в столбик.

Для последовательно введенных ключей 10 (корень), 25, 20, 6, 21, 8, 1, 30, будет построено дерево, вывод которого на экран с помощью функции View будет иметь следующий вид:

 

Освобождение памяти

Функция освобождения памяти, занятой элементами дерева, может быть реализована аналогично рекурсивной функции View

void Del_All(Tree *t) {

if ( t! = NULL) {

Del_All ( t -> Left);

Del_All ( t -> Right);

free(t);

}

}

 

⇐ Предыдущая12131415161718192021Следующая ⇒

Поделиться:

Популярное:

1. I. Основные решения по рекламе
2. I.2. Структура педагогической науки и её основные отрасли
3. II Основные общие и обзорные представления, понятия, положения психологии
4. II. ЭКЗАМЕН ПО ОБЩЕСТВОЗНАНИЮ: ОСНОВНЫЕ ЭЛЕМЕНТЫ ПРОВЕРКИ
5. А. Основные клинические формы
6. Авторское право: понятие, объекты, признаки и основные разновидности
7. Алгоритмы записи произвольной функции, заданной в таблице в виде с помощью элементарных функций.
8. Алгоритмы и модели компоновки
9. Алгоритмы многокритериальной оптимизации.
10. Алгоритмы обновления содержимого заполненных строк, снуппинг
11. Алгоритмы проведения парентеральных манипуляций
12. Алгоритмы синхронизации памяти и кэша