Деревья

Дерево в общем случае — это связный граф без циклов, абстрактная структура данных, представляющая собой множество вершин, или узлов, на которых определены попарные связи — рёбра. Будем рассматривать частный случай — корневые упорядоченные деревья. У таких деревьев рёбра становятся ориентированными, поскольку у любой последовательности попарно связанных вершин — пути, включающем корень, появляется направление от корня или к корню. Для некоторого узла v все вершины дерева на пути в корень, находящиеся ближе к корню, называется предками, а дальше от корня — потомками. Из пары узлов, связанных ребром, узел ближе к корню — отец, дальше от корня — сын. У каждого узла может быть несколько сыновей, которые называются братьями, но только один отец. Корень — это единственный в дереве узел, у которого нет отца. Узлы, у которых нет сыновей, называются листьями.

Количество рёбер на пути из корня в узел дерева называется глубиной узла, количество рёбер на самом длинном пути в лист — высотой. Высота дерева — это высота его корня. Разность между высотой дерева и глубиной узла — это уровень узла.

Дерево упорядочено, если упорядочены сыновья любого его узла. Из корневых упорядоченных деревьев наиболее часто используются двоичные, или бинарные. Каждый узел двоичного дерева может иметь не более двух сыновей — левого и правого, причём единственный сын узла — обязательно левый или правый. Более сложный вариант — троичное дерево, где у каждого узла — не более трёх сыновей: левый, средний, правый — в любой комбинации. Каждый из сыновей может рассматриваться как корень соответствующего поддерева, возможно, пустого.

Для представления дерева в памяти можно предложить естественный способ — разветвляющийся список. Узлы дерева — объекты, связи между которыми осуществляются через указатели. Для создания дерева достаточно объявить класс «узел дерева», членами которого должны быть указатели на узлы того же типа: «левый» и «правый» (у троичного дерева — «левый», «средний» и «правый»). В узле могут быть и другие данные-члены. Минимально необходимым является тег — метка или номер узла, с помощью которого можно различать узлы в процессе их обработки. Однако для работы с деревом в целом удобнее иметь особый класс «дерево», в котором собираются данные, относящиеся к дереву в целом и функции-члены для работы с деревом. Чтобы эти функции имели доступ к данным узла, достаточно объявить класс «дерево» дружественным для класса «узел».

//Класс «узел дерева»

class Node { char d; //тег узла

Node * lft; // левый сын

// Node * mdl; средний сын (если нужно)

Node * rgt; // правый сын

public:

Node(){ lft=0; rgt=0; } // конструктор узла

~Node(){ if(lft) delete lft; // деструктор (уничтожает поддерево)

if (rgt) delete rgt; }

friend class Tree; // дружественный класс «дерево»

};

// Класс «дерево в целом»

class Tree

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

char num, maxnum; //счётчик тегов и максимальный тег

int maxrow, offset; //максимальная глубина, смещение корня

char ** SCREEN; // память для выдачи на экран

void clrscr(); // очистка рабочей памяти

Node* MakeNode(int depth); // создание поддерева

void OutNodes(Node * v, int r, int c); // выдача поддерева

Tree (const Tree &); // фиктивный конструктор копии

Tree operator = (const Tree &) const; // фиктивное присваивание

public:

Tree(char num, char maxnum, int maxrow);//конструктор пустого дерева

~Tree();

void MakeTree() // ввод — генерация дерева

{ root = MakeNode(0); }

bool exist() { return root!= NULL; } // проверка «дерево не пусто»

int DFS(); // обходы дерева

int BFS();

void OutTree(); // выдача на экран

};

Кроме данных, в классе Tree объявлены скрытые функции-члены, вспомогательные функции, которые не входят в интерфейс и предназначены только для вызова из других функций-членов. А конструктор копирования и перегрузка присваивания сделаны скрытыми умышленно: попытка создать в программе ситуацию, в которой эти функции могут быть вызваны, приведёт к ошибке на этапе компиляции «нарушение защиты».

Конструктор дерева инициализирует параметры разметки и создаёт рабочую память — матрицу символов, необходимую для выдачи изображения дерева на экран.

Tree:: Tree(char nm, char mnm, int mxr):

num(nm), maxnum(mnm), maxrow(mxr), offset(40), root(NULL)

{ SCREEN = new char * [maxrow];

for(int i = 0; i < maxrow; i++) SCREEN[i] = new char[80]; }

Деструктор дерева уничтожает матрицу символов и запускает деструктор узла для корня.

Tree:: ~Tree() { for(int i = 0; i < maxrow; i++) delete [ ]SCREEN[i];

delete [ ]SCREEN; delete root; }

Обратите внимание на то, как создаётся и уничтожается матрица.