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

Хотя деревья общего вида достаточно важны, мы сосредоточимся на ограниченном классе деревьев, где каждый родитель имеет не более двух сыновей (Рис. 5). Такие бинарные деревья (binary trees) имеют унифицированную структуру, допускающую разнообразные алгоритмы прохождения и эффективный доступ к элементам. Изучение бинарных деревьев дает возможность решать наиболее общие задачи, связанные с деревьями, поскольку любое дерево общего вида можно представить эквивалентным ему бинарным деревом.

У каждого узла бинарного дерева может быть 0, 1 или 2 сына. По отношению к узлу слева будем употреблять термин левый сын (left child), а по отношению к узлу справа – правый сын (right child). Наименования "левый" и "правый" относятся к графическому представлению дерева. Бинарное дерево является рекурсивной структурой. Каждый узел – это корень своего собственного поддерева. У него есть сыновья, которые сами являются корнями деревьев, называемых левым и правым поддеревьями соответственно. Таким образом, процедуры обработки деревьев рекурсивны. Вот рекурсивное определение бинарного дерева:

Бинарное дерево - это такое множество узлов B, что

а) B является деревом, если множество узлов пусто (пустое дерево – тоже дерево);

б) B разбивается на три непересекающихся подмножества:

• {R} корневой узел

• {L1, L2, ..., Lm} левое поддерево R

• {R1, R2, ..., Rm} правое поддерево R

На любом уровне n бинарное дерево может содержать от 1 до 2n узлов. Число узлов, приходящееся на уровень, является показателем плотности дерева. Интуитивно плотность есть мера величины дерева (число узлов) по отношению к глубине дерева. На Рис. 5 дерево А содержит 8 узлов при глубине 3, в то время как дерево B содержит 5 узлов при глубине 4. Последний случай является особой формой, называемой вырожденным (degenerate) деревом, у которого есть единственный лист (E) и каждый нелистовой узел имеет только одного сына. Вырожденное дерево эквивалентно связанному списку.

Рис.5. Бинарные деревья

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

Вырожденные деревья являются крайней мерой плотности. Другая крайность – законченные бинарные деревья (complete binary tree) глубины N, где каждый уровень 0...N - 1 имеет полный набор узлов, и все листья уровня N расположены слева. Законченное бинарное дерево, содержащее 2N узлов на уровне N, является полным. На Рис. 6 показаны законченное и полное бинарные деревья.

Законченные и полные бинарные деревья дают интересные математические факты. На нулевом уровне имеется 2⁰ узлов, на первом — 2¹, на втором — 2² и т.д. На первых k-1 уровнях имеется 2^k-1 узлов.

1 + 2 + 4 + ... + 2^k-1 = 2^k-1

На уровне k количество дополнительных узлов колеблется от 1 до 2k (полное). В полном дереве число узлов равно

1 + 2 + 4 + ... + 2^k-1 + 2^k = 2^k-1 - 1

Число узлов законченного бинарного дерева удовлетворяет неравенству

2^k < N < 2^k-1 - 1 < 2^k-1

Решая его относительно k, имеем

k < log₂ (N) < k+1

Например, полное дерево глубины 3 имеет

2⁴ - 1 = 15 узлов

Рис.6. Классификация бинарных деревьев

Структура бинарного дерева

Структура бинарного дерева состоит из узлов. Как и в связанном списке, эти узлы содержат поля данных и указатели на другие узлы в коллекции. В этом разделе мы определим узлы дерева и операции для его построения и прохождения. Объявим класс TreeNode, реализующий функциональность узла дерева, и разработаем ряд функций, позволяющих создавать бинарные деревья и осуществлять прохождение по их узлам.

Узел дерева содержит поле данных и два поля с указателями. Поля указателей называются левым указателем (left) и правым указателем (right), поскольку они указывают на левое и правое поддерево, соответственно. Значение NULL является признаком пустого дерева.

Корневой узел определяет входную точку дерева, а поля указателей – узлы следующего уровня. Листовой узел содержит NULL в полях правого и левого указателей (Рис. 7).

Проектирование класса TreeNode

В этом разделе мы разберем разработку класса TreeNode, в котором объявляются объекты-узлы бинарного дерева. Узел состоит из поля данных, которое является открытым (public) элементом, т.е. к которому можно обращаться непосредственно. Это позволяет читать или обновлять данные во время прохождения дерева, а также допускает возвращение ссылки на данные. Последняя особенность используется более сложными структурами данных, например, словарями. Два поля с указателями являются закрытыми (private) элементами, доступ к которым осуществляется посредством функций Left() и Right().

Спецификация класса TreeNode

ОБЪЯВЛЕНИЕ

ОПИСАНИЕ

// Следующее объявление понадобится

// нам в дальнейшем

template <class T>

class BinSTree;

// объявление объекта для узла бинарного дерева

template <class T>

class TreeNode

{

private:

// указатели левого и правого дочерних узлов

TreeNode<T> *left;

TreeNode<T> *right;

public:

// открытый элемент, допускающий обновление

T data;

// конструктор инициализирует поля данных и указателей

// значение NULL соответствует пустому поддереву

TreeNode(const T& item, TreeNode<T> *lptr,

TreeNode<T> *rptr):data(item), left(lptr), right(rptr)

{

}

// методы доступа к полям указателей

TreeNode<T>* Left(void) const;

TreeNode<T>* Right(void) const;

// сделать класс BinSTree дружественным, поскольку

// необходим доступ к полям left и right

friend class BinSTree<T>;

};

Конструктор инициализирует поля данных и указателей. Если задать вместо обоих указателей NULL, узел будет инициализирован как лист.

Если в параметр lptr или rptr конструктора поместить указатели на другой объект TreeNode, конструктор присоединяет этот объект как левого или правого сына нового узла.

Методы доступа Left и Right возвращают соответствующий указатель. Класс BinSTree объявляется дружественным классу TreeNode и может модифицировать указатели. Другие клиенты должны использовать конструктор для создания указателей и методы Left и Right для прохождения дерева.

ПРИМЕР 

// указатели целочисленных узлов дерева

TreeNode<int> *root, *lchild, *rchild;

TreeNode<int> *p;

// создать листья, содержащие

// 20 и 30 в качестве данных

lchild = new TreeNode<int> (20);

rchild = new TreeNode<int> (30);

// создать корень, содержащий число

// 10 и двух сыновей

root = new TreeNode<int> (10, lchild, rchild);

root->data = 50; // присвоить корню 50

Методы Left и Right возвращают значения полей левого и правого указателей. Благодаря этому клиент имеет доступ к левому и правому сыновьям узла.

Построение бинарного дерева

Бинарное дерево состоит из коллекции объектов TreeNode, связанных между собой посредством полей Left и Right. Объект TreeNode создается динамически с помощью функции new.

TreeNode<int> *p; // объявление указателя

// на узел дерева

p = new TreeNode(item); // левый и правый указатели равны NULL

Вызов функции new обязательно должен включать значение данных, и необязательно указатели на правое и/или левое поддерево. Определим функцию GetTreeNode, принимающую данные, и ноль или более указателей на объект TreeNode для создания и инициализации узла бинарного дерева. При недостаточном количестве доступной памяти программа прекращается сразу после выдачи сообщения об ошибке.

// создать объект TreeNode с указательными полями lptr и rptr.

// по умолчанию указатели содержат NULL.

template <class T>

TreeNode<T> *GetTreeNode(T item, TreeNode<T> *lptr = NULL,

TreeNode<T> *rptr = NULL)

{

TreeNode<T> *p;

// вызвать new для создания нового узла

// передать туда параметры lptr и rptr

p = new TreeNode<T> (item, lptr, rptr);

// если памяти недостаточно, завершить

// программу сообщением об ошибке

if (p == NULL)

{

cerr << “Ошибка при выделении памяти!\n";

exit(1);

}

// вернуть указатель на выделенную системой память

return p;

}

Функция FreeTreeNode принимает указатель на объект TreeNode и освобождает занимаемую узлом память, вызывая оператор С++ delete.

// освободить динамическую память, занимаемую данным узлом

template <class t>

void FreeTreeNode(TreeNode<T> *p)

{

delete p;

}

Функция GetTreeNode может быть использована для явного построения каждого узла дерева и, следовательно, всего дерева. Это было продемонстрировано на дереве с тремя узлами, содержащими 10, 20 и 30. Для более крупного экземпляра процесс будет немного утомительным, так как вы должны поместить в дерево все значения данных и указателей.

Создадим функцию MakeCharTree, строящую три дерева, узлы которых содержат символьные элементы данных. Эти деревья будут использоваться для иллюстрации методов TreeNode в следующем разделе. Параметры функции включают в себя ссылку на корень дерева и число n (0 < n < 2), которое служит для обозначения дерева. Следующие объявления создают указатель на объект TreeNode, с именем root, и назначают его корнем дерева Tree_2.

// объявить указатель на корень

TreeNode<char> *root;

// сформировать на этом корне дерево tree_2

MakeCharTree(root,2);

На рисунке 8 показаны три дерева, построенных этим методом. Мы не приводим здесь кода этой функции ввиду ее примитивности, потренируйтесь сами.

Рис. 8. Дерево MakeCharTree