Типовые операции с двоичными деревьями
Для работы с двоичными деревьями используем две структуры:
1)Структура, содержащая собственно сами данные. Она может иметь любое количество полей. Одно из полей (или совокупность из нескольких полей) будет ключевым. Именно по нему будет вестись упорядочивание данных. Для рассматриваемой ниже задачи нам достаточно одного поля, которое будет ключом:
struct Data
{
int a;
};
2)Структура, определяющая узел дерева:
struct Tree
{
Data d;
Tree *left;
Tree *right;
};
Здесь используем два указателя:
• left — указатель на левого наследника;
• right — указатель на правого наследника.
Тексты этих структур необходимо расположить в начале программы (до main() и других функций).
В программе (обычно в функции main()) определяем указатель на корень дерева:
Tree *u = 0;
Первоначально дерево пусто, и указатель равен 0.
Теперь у нас всё готово для того, чтобы приступить к работе с бинарным деревом. Все действия для наглядности рассмотрим на конкретном примере.
Пример. Пусть дана числовая последовательность: 10, 25, 20, 6, 21, 8, 1, 30. Необходимо построить двоичное дерево. Данные упорядочивать по возрастанию.
Решение. Первым числом в последовательности является число 10. Именно оно заносится в корневой узел. Затем идет число 25. Оно меньше ключевого поля в корне, следовательно 25 добавляем к правой ветви корня. Число 20 больше 10, но меньше 25, поэтому оно добавится к левой ветви для узла, содержащего число 25. И так далее. В итоге получим дерево, изображённое на рисунке ниже:
Рассмотрим основные операции по работе с двоичным деревом. Везде u — это указатель на корень дерева.
1. Добавление нового элемента:
void Add(Tree **u, Data &x)
{
Tree *p = *u;
if(p == 0)
{ // Дерево пусто - добавляемый новый элемент станет корнем дерева
p = new Tree;
p->d.a = x.a;
p->left = 0;
p->right = 0;
*u = p;
return;
}
Tree *p1;
bool priznak = false; // признак того, что такой элемент уже имеется
while(p && !priznak)
{
p1 = p;
if(x.a == p->d.a)
priznak = true;
else
if(x.a < p->d.a)
p = p->left;
else
p = p->right;
}
if(priznak) return;
// Создание нового узла
Tree *pnew = new Tree;
pnew->d.a = x.a;
pnew->left = 0;
pnew->right = 0;
if(x.a < p1->d.a) // присоединить к левому поддереву
p1->left = pnew;
else // присоединить к правому поддереву
p1->right = pnew;
}
Возможный вызов функции:
Add(&u, x);
где x — объект типа Data.
Замечание. Многократный вызов в цикле этой функции с новыми x позволяет сформировать первоначальное дерево (как в нашем примере).
2. Обход дерева и вывод значений узлов в упорядоченном виде (по возрастанию) на экран монитора:
void Print(Tree *u)
{
if(u)
{
Print(u->left);
cout << u->d.a << endl;
Print(u->right);
}
}
Возможный вызов функции:
Print(u);
3. Поиск узла, ключ которого равен заданному значению:
Tree* Find(Tree *u, Data &x, Tree **prev)
{
Tree *p = u;
*prev = 0;
// Дерево пусто - искать нечего
if(p == 0)
return 0;
// Поиск искомого элемента
while(p)
{
//cout << "Find : " << p->d.a << endl;
if(p->d.a == x.a) // Решение найдено
return p;
if(p->d.a > x.a) // Перейти на левое поддерево
{
*prev = p;
p = p->left;
}
else// Перейти на правое поддерево
{
*prev = p;
p = p->right;
}
}
// Если попадаем сюда - значит решение не существует
*prev = 0;
return 0;
}
Возможный вызов функции:
Tree *p = Find(u, x, &p0);
Данная функция возвращает адрес найденного узла (если узел не найден, то результат равен 0).
Дополнительно через список параметров возвращается адрес узла-предка p0 для искомого узла. Если решение не найдено или искомый узел — это корень, то p0=0. А x, как обычно — объект типа Data.
4. Удаление элемента из дерева:
void Delete(Tree **u, Data &x)
{
Tree *p0 = 0;
Tree *p = Find(*u, x, &p0);
// Ничего не найдено - удалять не чего
if(p == 0)
return;
// Найденный элемент - корень дерева и надо удалять этот корень
if(p0 == 0 && (p->left == 0 || p->right == 0))
{
if(p->left == 0 && p->right == 0)
*u = 0;
else if(p->left == 0)
*u = p->right;
else
*u = p->left;
delete p;
return;
}
// Найденный элемент - это лист
if(p->left == 0 && p->right == 0)
{
if(p0)
{
if(p0->left == p)
p0->left = 0;
else
p0->right = 0;
}
else// лист оказался корнем!
u = 0;
delete p;
return;
}
// Найденный элемент - промежуточный узел по левой ветви, вырожденной в список
if(p->left != 0 && p->right == 0)
{
if(p0->left == p)
p0->left = p->left;
else
p0->right = p->left;
delete p;
return;
}
// Найденный элемент - промежуточный узел по правой ветви, вырожденной в список
if(p->left == 0 && p->right != 0)
{
if(p0->left == p)
p0->left = p->right;
else
p0->right = p->right;
delete p;
return;
}
// общий случай
if(p->left != 0 && p->right != 0)
{
p0 = p;
Tree *t = p->left;
while(t->right)
{
p0 = t;
t = t->right;
}
p->d.a = t->d.a;
if(p0->left == t)
p0->left = 0;
else
p0->right = 0;
delete t;
}
}
Возможный вызов функции:
Delete(&u, x);
где x — объект типа Data.
Функция Delete() использует функцию Find() для поиска удаляемого объекта. Именно для функции Delete() в списке параметров Find() применён дополнительный параметр p0 — адрес узла, который является предком удаляемого узла.
5. Удаление (очистка) всего дерева
После завершения работы с данными, хранящимися в дереве, необходимо очистить всё дерево. Выполнять это действие желательно сразу же, как дерево стало не нужным. Реализация этой операции может быть такой:
// Очистка всего дерева
void Clear(Tree **u)
{
if(*u == 0) return;
Clear1(u);
cout << "delete (*u)->d.a=" << (*u)->d.a << endl;
delete *u;
*u=0;
}
void Clear1(Tree **u0)
{
Tree *t;
Tree *u = *u0;
if(u->left != 0)
{
if(u->left->left != 0 || u->left->right != 0)
Clear1(&(u->left));
if(u->left->left == 0 && u->left->right == 0)
{
cout << "delete u->left->d.a=" << u->left->d.a << endl;
t = u->left;
delete t;
u->left = 0;
}
}
if(u->right != 0)
{
if(u->right->left != 0 || u->right->right != 0)
Clear1(&(u->right));
if(u->right->left == 0 && u->right->right == 0)
{
cout << "delete u->right->d.a=" << u->right->d.a << endl;
t = u->right;
delete t;
u->right = 0;
}
}
}
Возможный вызов функции:
Clear(&u);
Функция Clear() содержит вызов дополнительной рекурсивной функции Clear1(), в которой делается очистка всего дерева, кроме корня. Корневой узел удаляется затем непосредственно в функции Clear().
Алгоритм функции Clear() предельно прост и не требует каких-то дополнительных пояснений. А вот о работе Clear1() есть смысл поговорить немного подробнее.
Итак, при очередном рекурсивном вызове функции Clear1() делается проверка: имеется ли у текущего узла «левый наследник» u->left ? Если «да», то проверяем, является этот «наследник» листом, или он также имеет хотя бы одного «наследника». Если u->left — это лист, то его удаляем, иначе делаем на него переход, т.е. рекурсивно вызываем Clear1() для текущего «левого наследника». Всё то же самое делается и для правого наследника u->right. Работа продолжается до тех пор, пока в дереве не останется только один корень, который будет удалён в функции Clear().
Для лучшего понимания алгоритма работы очистки всего дерева в функциях Clear() и Clear1() имеется дополнительная печать. Если дерево было заполнено числовой последовательностью: 10, 25, 20, 6, 21, 8, 1, 30, то на экране будет выведено следующее:
delete u->left->d.a=1
delete u->right->d.a=8
delete u->left->d.a=6
delete u->right->d.a=21
delete u->left->d.a=20
delete u->right->d.a=30
delete u->right->d.a=25
delete (*u)->d.a=10
Именно в такой порядке будут удаляться узлы дерева.