Дерево - связный граф без циклов, удовлетворяющий следующим условиям:
- Существует единственная вершина, называемая корнем, в которую не входит ни одна дуга.
- В каждую вершину входит ровно одна дуга.
- Из каждой вершины выходит произвольное чмсло дуг.
- Потомки любой вершины упорядочены, обычно слева направо.
Вершины, не имеющие потомков называются листьями дерева .
Дерево называется бинарным, если из любой вершины выходит не более двух дуг, которын называютмя левым и правым потомками.
Бинарное дерево может быть размеченным, т.е. каждой вершине приписана определенная информация, например целое число из некоторого множества. Разметка дерева удовлетворяет следующим требованиям:
- Любая вершина, находящаяся на любом уровне слева от заданной вершины имеет пометку меньше, чем пометка заданной вершины.
- Любая вершина, находящаяся на любом уровне справа от заданной вершины имеет пометку больше, чем пометка заданной вершины.
Пример размеченного бинарного дерева привед на рисунке ниже.
При работе с бинарным деревом его удобно рассматривать как рекурсивную структуру, состоящую из трех элементов:
дерево =
|
вершина (элемент базисного типа) дерево левое дерево правое |
Поэтому многие алгоритмы для работы с деревом может быть представлены в рекурсивном виде, т.е. компактны и просты для понимания. Бинарное дерево не обязано содержать числовую информацию в качестве своей вершины. Информационная составляющая вершины может быть любого типа. Единственным условием является возможность применения операции сравнения '<' или '>' к вершинам дерева. Некоторые существенно упрощаются при наличии еще одного элемента в структуре дерева - родительской вершины. Единственная вершина дерева - корневая - не имеет родителя. Приведем некоторые из алгоритмов обработки дерева. Будем считать, что вершинам приписаны целые значения, а тип дерева задан структурой следующего вида
struct tree
фсо int top ; // значение вершины
tree * left ; // указатель на левой поддерево
tree * right ; // указатель на правое поддерево
tree * parent ; // указатель на родительскую вершину
tree(k)фсо top = k;
left = right = parent = NULL;
фсз // функция - конструктор, инициализирует поле top
фсз; // заданным значением k, а указатели - значением NULL.
Как отмечалось ранее, структуры могут иметь члены-функции, определяющие операции, которые могут выполняться над структурой. В данном случае использована одна специализированная функция - конструктор. Назначение консруктора - инициализация членов-данных структуры. Следует обратить внимание, что
- имя конструктора совпадает с именем структуры,
- синтаксис объявления констуктора не содержит типа возвращаемого результата, так как имя конструктора уже задает тип ( struct определяет пользовательский тип данных).
- вызов любых членов-функций, в том числе и конструкторов, выполняется аналогично обращению к членам-данным, то есть с использованием операций '->' и '.' .
