Представление дерева в памяти

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

Связь узлов в дереве осуществляется таким образом (Рисунок 2.19, а), что каждый узел-сын содержит ссылку на вышестоящий узел (узел-отца). В этом случае корень будет содержать нулевой указатель на месте соответствующего указателя. Имея такой тип связей узлов в дереве, можно подниматься от нижних уровней дерева к его корню, что может быть полезным при реализации определенных видов синтаксического разбора.

Каждый узел дерева содержит указатели на свои поддеревья (Рисунок 2.19, б), то есть каждый отец ссылается на своих сыновей. Этот способ применим для представления деревьев небольшой арности, например бинарных деревьев. Имея указатель на корень дерева, можно достичь любого узла дерева.

Каждый узел дерева ссылается на свои поддеревья с помощью списка, при этом каждый узел содержит два указателя — для представления списка поддеревьев и для связывания узлов в этот список (Рисунок 2.19, е).

Рисунок 2.19. Варианты связи узлов дерева между собой

Бинарное дерево обычно представляется с помощью второго способа (Рисунок 2.19, б). Минимально для представления узла достаточно трех полей: содержательной части узла и двух указателей — на левого (старшего) и правого (младшего) сыновей. Таким образом, представить бинарное двоичное дерево можно с помощью нелинейного двусвязного списка. Структуру узла в программе можно описать так:

node_tree struc ;узел дерева

simbol db 0 содержательная часть

l_son dd 0 указатель на старшего (левого) сына

r_son dd 0 указатель на младшего (правого) сына

ends

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

Содержание раздела