Представления и реализации бинарных деревьев
Рассмотрим варианты представления и реализации структуры данных бинарного дерева. Пусть базовый тип узлов есть Elem.
Ссылочная реализация бинарного дерева в связанной памяти основана на представлении типа BT (Elem) рекурсивными типами BinT и Node:
type
BinT = ^Node; {представление бинарного дерева}
Node = record {узел: }
Info: Elem; {- содержимое}
LSub: BinT; {- левое поддерево}
RSub: BinT {- правое поддерево}
end {Node}
Здесь каждый узел дерева рассматривается как корень соответствующего поддерева, и этому поддереву сопоставляется запись из трех полей: поле Info хранит значение корня (типа Elem), а поля LSub и RSub - указатели на левое и правое поддеревья. Пустому дереву сопоставляется константа NilBT
На рис. а, б изображены бинарное дерево и его представление в ссылочной реализации.
ЛЕКЦИЯ 10. РЕАЛИЗАЦИЯ БИНАРНОГО ДЕРЕВА НА БАЗЕ ВЕКТОРА. ПРОШИТЫЕ БИНАРНЫЕ ДЕРЕВЬЯ
Цели и задачи лекции:
1.Ознакомление с векторной реализацией дерева.
2. Ознакомление с особенностями построения прошитых деревьев
Основные рассматриваемые вопрос: реализация бинарного дерева на базе вектора. Прошитые бинарные деревья.
Ссылочная реализация ограниченногобинарного дерева на базе вектора:
type Adr = 0 .. MaxAdr; {диапазон «адресов» в векторе Mem}
BinT = Adr; {представление бинарного дерева}
Node = record {узел: }
Info: Elem; {- содержимое}
LSub: BinT; {- левое поддерево}
RSub: BinT {- правое поддерево}
|
|
|
end {Node};
Mem = array [Adr]of Node {вектор для хранения дерева}
Здесь вектор типа Mem представляет собой память для хранения одного бинарного дерева (или нескольких бинарных деревьев, ограниченных в совокупности). Элемент вектора есть запись типа Node, содержащая узел и ссылки на поддеревья. На рис. приведен пример представления бинарного дерева. Дерево представляется переменной b: BinT, причем значение b = 3 есть номер элемента массива, в котором хранится корень дерева. Фактически переменная b играет роль ссылки на корень дерева (или адреса корня в векторной памяти). Пустому дереву соответствовало бы значение b = 0, т. е. в этом представлении константа NillBT = 0. Элементы вектора, не занятые под хранение узлов дерева, образуют свободную память, которую удобно организовать в виде линейного циклического списка (для этого используется одно из полей звена Node, например, поле LSub). При этом элемент вектора с индексом (адресом) 0 играет роль ссылки на начало списка свободной памяти.
Рис. Пример ссылочного представления бинарного дерева на базе вектора.
Представление по уровням полного бинарного дерева в виде массива
В виде массива проще всего представляется полное бинарное дерево, так как оно всегда имеет строго определенное число вершин на каждом уровне. Вершины можно пронумеровать слева направо последовательно по уровням и использовать эти номера в качестве индексов в одномерном массиве.
|
|
|
Рис. Представление бинарного дерева в виде массива
Если число уровней дерева в процессе обработки не будет существенно изменяться, то такой способ представления полного бинарного дерева будет значительно более экономичным, чем любая списковая структура.
Однако далеко не все бинарные деревья являются полными. Для неполных бинарных деревьев применяют следующий способ представления. Бинарное дерево дополняется до полного дерева, вершины последовательно нумеруются. В массив заносятся только те вершины, которые были в исходном неполном дереве. При таком представлении элемент массива выделяется независимо от того, будет ли он содержать узел исходного дерева. Следовательно, необходимо отметить неиспользуемые элементы массива. Это можно сделать занесением специального значения в соответствующие элементы массива. В результате структура дерева переносится в одномерный массив. Адрес любой вершины в массиве вычисляется как
адрес = 2к-1+i-1,
где k-номер уровня вершины, i- номер на уровне k в полном бинарном дереве. Адрес корня будет равен единице. Для любой вершины можно вычислить адреса левого и правого потомков
|
|
|
адрес_L = 2к+2(i-1)
адрес_R = 2к+2(i-1)+1
Главным недостатком рассмотренного способа представления бинарного дерева является то, что структура данных является статической. Размер массива выбирается исходя из максимально возможного количества уровней бинарного дерева. Причем чем менее полным является дерево, тем менее рационально используется память.
Прошитые бинарные деревья
Порядок обхода бинарного дерева можно хранить непосредственно в структуре данных. Для этого достаточно ввести дополнительное поле указателя в элементе списковой структуры и хранить в нем указатель на вершину, следующую за данной вершиной при обходе дерева.
Представление деревьев в виде массивов также допускает хранение порядка прохождения дерева. Для этого вводится дополнительный массив, в который записываются адрес вершины в основном массиве, следующей за данной вершиной.
Рис. Представление симметрично прошитого бинарного дерева в виде массивов
Такие структуры данных получили название прошитых бинарных деревьев. Указатели или адреса, определяющие порядок обхода называют нитями. При этом в соответствии с порядком прохождения вершин
|
|
|
различают право прошитые, лево прошитые и симметрично прошитые бинарные деревья.
Дата добавления: 2018-05-02; просмотров: 836; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!