456 Часть III. Современное программирование на C++

/ I Выталкивание одного наружу. STUDENT si(students.Pop());

cout « "Студент " « sl.GetIdO « "изъят из стека." « endl;

const STUDENT s2(students.Top());

cout « "Студент " « s2.GetId() « "остался на вершине стека."« endl;

Бинарное дерево

Бинарные деревья (binary trees) состоят из узлов (nodes), которые содержат собственно данные и два указателя на потомков — левого и правого. Узел, не имеющий потомков, называется конечным узлом (terminal node). Начальный узел называется корневым (root node). Добавление элемента в двоичное дерево происходит следующим образом. Новый элемент сравнивается с корневым узлом при помощи операции <. Если он меньше корневого, он сравнивается с левым узлом, а затем (если он меньше) с его потомком; в противном случае, если элемент больше корневого узла, он сравнивается с правым узлом. Процесс повторяется до тех пор, пока не окажется, что потомков больше нет. Тогда добавляется новый узел со значением, равным этому элементу.

Достоинство бинарных деревьев заключается в эффективном доступе к данным, содержащимся в дереве. Эта эффективность зависит от того, насколько дерево является сбалансированным. Крайним примером несбалансированного дерева является размещение в таком дереве упорядоченного списка. В этом случае каждый узел будет иметь только одного потомка — левого, если список был отсортирован по возрастанию и только правого, если по убыванию. Результатом будет однонаправленный список. Хорошо сбалансированное дерево имеет одинаковое число левых и правых потомков. Поиск в бинарном дереве и добавление новых элементов наиболее эффективны в случае хорошо сбалансированных деревьев.

Класс STUDENT, определенный в листинге 18.5 (student2.h), имеет хорошо определенные операции сравнения и равенства, поэтому объекты этого класса можно использовать в бинарном дереве:

typedef TBinarySearchTreeImp<STODENT> STUDENT_TREE;

typedef TIBinarySearchTreeImp<STUDENT> STUDENT_POINTER_TREE;

Оба конструктора не имеют аргументов. Функции-члены Add, Detach, Find,

Flush, ForEach, GetItemsInContainer И IsEmpty аналогичны ТВКИМ же функЦИ-

ям для контейнеров-массивов.

Листинг 18.14 демонстрирует использование косвенного контейнера типа бинарное дерево.

^include <iostream.h> ttinclude <iomanip.h>