Бинарные деревья. Выделим бинарное дерево - конечное множество узлов, которое является пустым или состоит из корня и двух непересекающихся бинарных деревьев

Выделим бинарное дерево - конечное множество узлов, которое является пустым или состоит из корня и двух непересекающихся бинарных деревьев, называемых левым и правым поддеревьями данного корня.

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

Определим бинарное дерево как конечное множество узлов, которое или пусто, или состоит из корня и из двух непересекающихся бинарных деревьев, называемых левым и правым поддеревьями данного корня.

Помимо таких структур, как деревья, леса и бинарные деревья, имеется тип, тесно связанный с первыми двумя. Эти структуры называют обычно списочными структурами. Такой список определяется как конечная последовательность списков, число которых, может быть равно нулю.

Представление бинарного дерева в компьютере вытекает из его определения. То есть мы имеем переменную Т, которая указывает на корень бинарного дерева. А каждый узел имеет две переменные связи: LLink и RLink, которые указывают на левое и правое поддеревья соответственно. Если дерево пусто, то указатель на него равен nil.

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

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

Прямой порядок обхода:

Попасть в корень

Пройти левое поддерево

Пройти правое поддерево

Центрированный порядок обхода:

Пройти левое поддерево

Попасть в корень

Пройти правое поддерево

Обратный порядок обхода:

Пройти левое поддерево

Пройти правое поддерево

Попасть в корень

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

1.2. “Прошитые” деревья

Можно несколько сэкономить память компьютера за счет применения так называемых “прошитых” деревьев. В “прошитых” деревьях концевые связи-указатели используются для связи с родителями, такие связи назвали нитями. А для того чтобы отличать нормальные связи от нитей, в каждом узле хранят две однобитовые переменные LTag и RTag. Эти переменные равны нулю, если соответствующие связи указывают на поддеревья, и единице, если связи являются нитями. Левая нить каждого узла указывает на узел, являющийся предшественником данного при центрированном обходе, правая - на узел, являющийся последователем данного узла.

При работе с древовидными структурами часто приходится решать задачу обхода дерева. Это - способ методичного исследования узлов дерева, при котором каждый узел проходится точно один раз. Для этого удобно использовать, например, такой рекурсивный алгоритм:

1. Корень дерева.

2. Если нет поддеревьев, то ВЫХОД, иначе обходим все поддеревья слева направо.

Дата добавления: 2014-01-07