Двоичное дерево - это самый простой вид дерева, у каждой вершины может быть только два потомка. В упорядоченном дереве большее значение располагается справа от вершины, а меньшие значения слева от вершины.
Построим двоичное упорядоченное дерево из чисел 5, 7, 3, 1, 4.
Первый элемент (5) помещается в корень дерева.
Рисунок 1.10.9.
Берем следующий элемент (7). Т. к. 7 больше 5, помещаем его в правую ветвь от 5.
Рисунок 1.10.10.
Берем следующий элемент (3). Т. к. 3 меньше 5, помещаем его в левую ветвь от 5.
Рисунок 1.10.11.
Берем следующий элемент (1). Т. к. 1 меньше 5 и левая ветвь уже существует (элемент 3), будем сравнивать 1 и 3. 1 меньше 3 помещаем 1 в левую ветвь от 3.
Рисунок 1.10.12.
Берем следующий элемент (4). Т. к. 4 меньше 5 и левая ветвь уже существует (элемент 3), будем сравнивать 1 и 3. 4 больше 3 помещаем 1 в правую ветвь от 3. В результате получаем бинарное дерево:
Рисунок 1.10.13.
Пример программы "Бинарное дерево".
Для создания дерева будут использованы рекурсивные функции: dob для добавления элемента, pech для печати элемента дерева.
Элемент дерева будет иметь структуру
Рисунок 1.10.14.
#include <iostream.h>
struct DEREVO
{
int info;
DEREVO * next_l;
DEREVO * next_r;
};
void dob (DEREVO * tek, int znach);
void pech (DEREVO *tek);
void main()
{
int i;
DEREVO *nach, *tek, *new_n;
nach=0;
cout << "\n Вводите значения вершин дерева, 0 - признак окончания ввода ";
do
{
cout << "\nВведите значение вершины";
cin >> i;
if (nach)
{ // Если дерево не пусто, вызывается функци dob
dob(nach, i);
}
else
{ // Если дерево пусто создается корень дерева
new_n=new DEREVO;
new_n-> info=i;
new_n-> next_l=0;
new_n-> next_r=0;
nach=new_n;
}
}
while (i);
pech(nach); // Печать
}
// Рекурсивная функция dob.
tek - указатель на текущую вершину дерева,
znach - значение, которое необходимо добавить в дерево.
Функция dob определяет в какую ветвь нужно добавить новое значение,
если znach меньше текущего значения, то производиться добавление в левую ветвь,
иначе - в правую ветвь.
Если ветвь нельзя добавить (такая ветвь уже существует), то снова вызывается функция dob.
void dob (DEREVO * tek, int znach)
{
int i1;
DEREVO *new_n;
i1=tek-> info;
// Если значение текущего элемента дерева меньше нового элемента
if (znach<i1)
{
if (tek-> next_l)
dob (tek->next_l,znach);
else
{
new_n=new DEREVO;
new_n-> info=znach;
new_n-> next_l=0;
new_n-> next_r=0;
tek-> next_l=new_n;
}
}
if (znach>i1)
{
if (tek-> next_r)
dob (tek-> next_r,znach);
else
{
new_n=new DEREVO;
new_n-> info=znach;
new_n-> next_l=0;
new_n-> next_r=0;
tek-> next_r=new_n;
}
}
}
void pech (DEREVO *tek)
{
if (tek)
{
pech(tek-> next_l);
cout << "\n\t" << tek-> info;
pech(tek-> next_r);
}
}
Вопросы для самоконтроля
1. Перечислите различные виды динамических структур
2. Какие динамические структуры могут быть построены на основе элемента с информационным полем и одним указателем?
3. Чем различается работа очереди, стека и списка?
4. Какие динамические структуры могут быть построены на основе элемента с информационным полем и двумя указателями?
5. Добавьте в программу "Бинарное дерево" функцию, которая находит самое большое значение дерева. Для этого начните двигаться от корня дерева и все время выбирайте правую ветвь дерева.