Бинарные деревья

Бинарные  деревья

     Бинарное  дерево это конечное множество элементов, которое либо пусто, либо содержит один элемент, называемый корнем дерева, а остальные элементы множества делятся на два непересекающихся подмножества, каждое из которых само является бинарным деревом.. Эти подмножества называются левым и правым поддеревьями исходного дерева. Элементы бинарного дерева называются узлами. Если данный узел имеет ссылки на другие узлы, то они называются сыновьями данного узла, а сам узел является отцом для них. Узлы, имеющие общего отца, называются братьями. Если узел дерева не имеет сыновей, то он называется терминальным узлом или листом.

     Принято изображать деревья “растущими”  сверху вниз от корня. На рис. 1 показано бинарное дерево, образованное из букв, входящих в строку ”дерево букв”. Буквы строки рассматриваются слева направо. Первая буква д помещается в корневой узел. Следующая буква помещается в левое поддерево, если она стоит в алфавите ранее буквы из данного узла, и в правое поддерево, если в алфавите буква расположена после буквы из данного узла. Если рассматриваемая буква совпадает с буквой из данного узла, увеличивается счетчик букв.

 
 
 
 
 
 
 
 
 
 
 
 
 
 

     Одной из задач, которая ставится для бинарных деревьев, является по-

сещение всех узлов дерева. Существуют три возможных варианта посещения всех узлов бинарного дерева [15]:

• Прямой обход (сверху вниз), при котором мы посещаем узел, а затем ле-вое и правое поддеревья;
• Поперечный обход (слева направо), при котором мы посещаем левое под-дерево, затем узел, а затем правое поддерево;
• Обратный обход (снизу вверх), при котором мы посещаем левое и правое поддеревья, а затем узел.

   При обходе дерева можно выполнять какие-то действия с информацией текущего узла. 

Программа 1. Бинарные деревья

     Воспользуемся средой C++ Builder, чтобы применить функции кон-

сольного ввода и вывода, объявленные в conio.h.

     В листинге 1.1 приведен файл BTree.h, в котором объявлены структура Node для моделирования узлов дерева и класс BTree для моделирования би-

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

Node* _Add(Node *r, T s) и три функции, реализующие  три способа обхода дерева. Аргументом функций обхода является указатель на корень дерева и функция void Visit(Node*), которая должна выполняться в узле дерева. Открытые методы класса BTree являются, по сути дела обертками для закрытых методов. 

Листинг 1.1. Класс бинарных деревьев

// Файл BTree.h

#ifndef BTReeH

#define BTReeH

#include <iostream>

#include <locale>

#include <conio.h>

#include <windows.h>

using namespace std;

#pragma hdrstop

typedef int T;  // Тип информации узла

struct Node{  // Класс узлов дерева

T inf; // Информация  в узле

T GetInf( ) { return inf; }

Node* left;    // Левое поддеpево (левый сын)

Node* right;     // Правое поддеpево (правый сын)

Node(T w): inf(w), left(0), right(0) { }     // Конструктор узла

~Node( ) { }     // Деструктор узла

};

class BTree{  // Класс деревьев

Node* root;  // Указатель на корень дерева

Node* _Add(Node *r, T s)    // Добавление элемента s в дерево

{

if(r = = 0) // Если  дерево пустое

r = new Node(s);  // Создание дерева из одного узла

else if(s < r->inf)

r->left = _Add(r->left, s);        // Вставка в левое поддерево

else

r->right = _Add(r->right, s);  // Вставка в правое поддерево

return r;

}

void _PreorderWalk(Node* r, void Visit(Node*))   // Прямой обход дерева

{ // Visit: функция,  выполняемая в узле

if(r = = 0) return;

Visit(r);

_PreorderWalk(r->left, Visit);

_PreorderWalk(r->right, Visit);

}

void _CrossWalk(Node* r, void Visit(Node*))  // Поперечный обход дерева

{ // Visit: функция,  выполняемая в узле

if(r = = 0) return;

_CrossWalk(r->left, Visit);

Visit(r);

_CrossWalk(r->right, Visit);

}

void _PostorderWalk(Node* r, void Visit(Node*))  // Обратный обход дерева

{ // Visit: функция,  выполняемая в узле

if(r = = 0) return;

_PostorderWalk(r->left, Visit);

_PostorderWalk(r->right, Visit);

Visit(r);

}

Node* Copy(Node* source)  // Создание копии дерева с корнем source

{

if(source = = 0) return 0;

Node* tmp = new Node(source->inf);  // Создание корня у копии

tmp->left = Copy(source->left);  // Создание левого поддерева копии

tmp->right = Copy(source->right);  // Создание правого поддерева копии

return tmp;

}

static void Swap_Left_Right(Node *r)       // Обменивает левый и правый

{  // указатели узла r

Node* tmp = r->left;

r->left = r->right;

r->right = tmp;

}

static void DelNode(Node* r){ delete r; }  // Удаление узла r

public:

BTree( ) : root(0) { }  // Конструктор дерева. По умолчанию дерево пусто

void Add(T s)  // Добавление в дерево элемента s

{ root = _Add(root, s); }

void PreorderWalk(void Visit(Node*))  // Прямой обход дерева

{ _PreorderWalk(root, Visit); }

void CrossWalk(void Visit(Node*))   // Поперечный обход дерева

{ _CrossWalk(root, Visit); }

void PostorderWalk(void Visit(Node*))  // Обратный обход дерева

{ _PostorderWalk(root, Visit); }

BTree(BTree& bt)      // Конструктор копирования дерева

{ root = Copy(bt.root); }

~BTree( )      // Деструктор дерева

{ _PostorderWalk(root, DelNode); }

void Mirror( ) // Преобразование дерева в свое зеркальное отражение

{ _PostorderWalk(root, Swap_Left_Right); }

Node* GetRoot( ) { return root; }

};

int ShowTree(Node* r, int x, int y, int width);  // Показ дерева

#endif

     В конструкторе копирования вызывается функция Copy, которая созда-

ет копию  существующего дерева bt. Эта копия  становится новым объектом класса BTree.

     В деструкторе выполняется обратный обход дерева, в узлах вызывается статическая функция DelNode( ) , удаляющая текущий узел. То есть деструк-тор сначала удаляет левое поддерево, затем правое поддерево и, наконец, те-кущий узел. Благодаря тому, что функция обхода рекурсивная, корень дерева удаляется в последнюю очередь.

     Метод Mirror( ) преобразует дерево в свое зеркальное отражение. Для реализации вызывается функция обратного обхода, которой в качестве аргу-мента передается статическая функция Swap_Left_Right( ) , меняющая места-ми значения указателей на левое и правое поддеревья.

     Сначала выполняется зеркальное преобразование левого поддерева, за-

тем правого  и, наконец, меняются местами левое и правое поддеревья корня.

     В листинге 1.2 приведена функция ShowTree( ) , выводящая на экран

бинарное дерево в наглядном виде, похожем на рис. 1. 

Листинг 1.2. Вывод бинарного  дерева

// Файл BTree.cpp

#include "BTree.h"

// ShowTree: Вывод дерева. x, y координаты экрана для корня, width – отступ

// Возвращает  наибольший номер строки экрана, на которой выводились узлы

int ShowTree(Node* r, int x, int y, int width)

{

if(r = = 0) return y;  // Пустое дерево

gotoxy(x, y);  // Перевод курсора в позицию x, y экрана

cout << r->inf;  // Вывод информацию из корня дерева

int w = width / 2 ? width / 2 : 1;  // Новый отступ не меньше 1

int yl = ShowTree(r->left, x - w, y + 1, w);  // Вывод левого поддерева

int yr = ShowTree(r->right, x + w, y + 1, w);   // Вывод правого поддерева

return yl > yr ? yl : yr;  // Возвращение максимального номера строки

}

     В листинге 1.3 приведена программа  тестирования класса бинарных

деревьев.

     Вспомогательная функция PrnInf( ) , выводящая информацию узла

дерева, передается функциям обхода, для вывода дерева.

     В дерево bt вставляются целые числа из массива x. Это дерево выво-дится в наглядном виде и в порядке трех обходов: прямом, поперечном и обратном. Для проверки конструктора копирования создается копия cbt дерева bt. Наконец дерево bt `преобразуется в свое зеркальное отражение. 

Листинг 1.3. Тестирование бинарного  дерева

// Файл TestBinaryTree.cpp

#include "BTree.h"

void PrnInf(Node* r)

{ cout << r->GetInf( ) << " "; }

int main( )

{

SetConsoleOutputCP(1251);

int x[] = {14, 15, 18, 4, 9, 7, 18, 3, 5, 16, 4, 20, 17, 9, 4, 5};

const int WIDTH = 32;  // Начальный отступ

int n = sizeof(x) / sizeof(int);  // Размер массива

BTree bt; // Дерево

for(int i = 0; i < n; i++)  // Заполнение дерева

bt.Add(x[i]);

cout << "Дерево bt";  // Вывод дерева

int y = ShowTree(bt.GetRoot( ) , WIDTH, wherey( ) + 1, WIDTH);

gotoxy(1, y); // Перевод  курсора на строку ниже дерева

cout << "Прямой  порядок обхода дерева bt\n";

bt.PreorderWalk(PrnInf);

cout << "\nПоперечный  порядок обхода дерева bt\n";

bt.CrossWalk(PrnInf);

cout << "\nОбратный  порядок обхода дерева bt\n";

bt.PostorderWalk(PrnInf);

BTree cbt = bt;  // cbt - копия дерева bt

cout << "\nДерево cbt - копия bt";

y = ShowTree(cbt.GetRoot( ) , WIDTH, wherey( ) + 1, WIDTH);

gotoxy(1, y);

cout << "Поперечный  порядок обхода дерева cbt\n";

cbt.CrossWalk(PrnInf);

cout << endl;

bt.Mirror( ) ;  // Зеркальное отражение bt

cout << "Дерево bt после зеркального отражения";

ShowTree(bt.GetRoot( ) , WIDTH, wherey( ) + 1, WIDTH);

getch( ) ;

return 0;

} 

     Далее приведены результаты работы программы. Элементы дерева

выводятся в  упорядоченном виде при поперечном обходе.

Дерево bt 

 
 
 
 
 
 
 

Прямой порядок  обхода дерева bt

14 4 3 9 7 5 4 4 5 9 15 18 16 17 18 20

Поперечный порядок  обхода дерева bt

3 4 4 4 5 5 7 9 9 14 15 16 17 18 18 20

Обратный порядок  обхода дерева bt

3 4 4 5 5 7 9 9 4 17 16 20 18 18 15 14

Дерево cbt - копия bt 

 

Поперечный порядок  обхода дерева cbt

3 4 4 4 5 5 7 9 9 14 15 16 17 18 18 20

Дерево bt после  зеркального отражения