Произвольный список определяется адресом одного из узлов. Для двоичного дерева этот узел будет корневым, для циклического списка удобно использовать последний узел. Следовательно, следует, что список можно задать с помощью класса
сlass LIST
{
protected:
NODE *root;
public:
LIST() { root = NULL; }
};
В этом примере структура основного узла имеет статус доступа protected, ибо поля со статусом доступа private для производных классов становятся недоступными.
Здесь учтено, что пустой список, как правило, содержит указатель, равный нулю. Остальные списки можно определить как производные от класса LIST.
Определим класс дерева как производный от класса LIST:
class TREE : LIST
{
public:
void insert (int x);
void show();
}
В этом примере функция insert() – служит для добавления нового элемента к дереву, а подпрограмма show() выводит содержимое дерева в симметричном порядке. Аналогичным образом можно дополнить эти составные функции подпрограммой удаления элемента. Возможность доступа к внешним функциям позволяет определить подпрограмму включения элемента следующим образом:
void TREE :: insert (int x)
{
root = :: insert (root, x);
};
Аналогичным образом определяется подпрограмма вывода элементов в симметричном порядке. При выводе элементы дерева отображаются в неубывающем порядке.
Ниже приведён текст программы, реализующей класс дерева поиска:
#include <stdio.h> //стандартная библиотека ввода-вывода
#include <conio.h> //библиотека консольного ввода-вывода
struct NODE //структура узла дерева
{
int info; //информационное поле
NODE *left, *right; //указатели на левое и правое поддеревья
};
class LIST //базовый класс списка
{
protected:
NODE *root;
public:
LIST() { root = NULL;}
};
class TREE: LIST //класс дерева поиска, производный
//от класса списка
{
public:
void insert(int x); //добавление элемента
void show(); //обход в симметричном порядке
};
NODE* insert(NODE* root, int x)
{
if (!root) //если дерево пусто, то
{
root = new NODE; //создаём новое дерево
root -> info = x; //заполняем информационную часть
root -> left = root -> right = NULL;
}
else
{
//дерево не пусто
//если значение добавляемого элемента меньше чем
//значение информационной части корня, то его следует добавлять
//в левое поддерево
if (x < root -> info) root -> left = insert(root -> left, x);
//в противном случае его следует добавлять в правое поддерево
else root -> right = insert(root -> right, x);
}
return root;
};
void TREE :: insert(int x)
{
root = ::insert(root, x);
};
void display(NODE* p)
{
if(p)
{
display(p -> left); //переходим в левое поддерево
printf("n%d", p -> info); //отображаем содержимое
//информационного поля
display(p -> right); //переходим в правое поддерево
}
};
void TREE :: show()
{
display(root);
};
int main()
{
TREE a; //создадим объект класса дерево
clrscr(); //очистим экран
//добавим в дерево произвольные элементы
a.insert(2);
a.insert(3);
a.insert(1);
a.insert(12);
a.insert(21);
a.insert(14);
a.insert(20);
a.insert(3);
printf ("Обход дерева в симметричном порядке:");
a.show(); //отобразим дерево на экране
getch(); //ожидание нажатия любой клавиши (пауза)
return 0;
}
Результаты работы программы
Обход дерева в симметричном порядке:
1
2
3
3
12
14
20
21