Динамические структуры данных. Алексеев А.Ю - 62 стр.

UptoLike

ВУЗ: 

КамчатГТУ | Петропавловск-Камчатский

Составители: 

Рубрика: 

Здесь вектор типа Mem представляет собой память для хранения одного
бинарного дерева (или нескольких бинарных деревьев, ограниченных в сово-
купности). Элемент вектора есть запись типа Node, содержащая узел и ссылки
на поддеревья. На рис.3.11 приведен пример представления бинарного дерева.
Дерево представляется переменной типа BinT, например b:BinT, значение ко-
торой b=3 есть номер элемента массива, в котором хранится корень дерева.
Фактически переменная b играет роль ссылки на корень дерева (или адреса
корня в векторной памяти). Пустому дереву соответствовало бы значение
b=0, т.е. в этом представлении константа NillBT = 0. Элементы вектора, не за-
нятые под хранение узлов дерева, образуют свободную память, которую
удобно организовать в виде линейного циклического списка (для этого ис-
пользуется одно из полей звена Node (например, поле LSub)). При этом эле-
мент вектора с индексом (адресом) 0 играет роль ссылки на начало списка
свободной памяти.
Рис. 3.11. Пример ссылочного представления бинарного дерева на базе вектора.
Справа – бинарное дерево; слева – его размещение в массиве, играющем
роль динамической памяти.
Мы не будем более подробно рассматривать эту реализацию, поскольку
она во многом аналогична ссылочной реализации линейного списка на базе
вектора, рассмотренной ранее в 1.4.
Бинарное
дерево:
a
d
c b
e
f
g
2
0
f
0
6
5
a
4
0
c
1
8
b
7
9
10
e
0
0
d
0
11
0
g
0
12
0
0:
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
LSu
Info
RSu
Связи списка
свободной
п
а
мяти:
62
   Здесь вектор типа Mem представляет собой память для хранения одного
бинарного дерева (или нескольких бинарных деревьев, ограниченных в сово-
купности). Элемент вектора есть запись типа Node, содержащая узел и ссылки
на поддеревья. На рис.3.11 приведен пример представления бинарного дерева.
Дерево представляется переменной типа BinT, например b:BinT, значение ко-
торой b=3 есть номер элемента массива, в котором хранится корень дерева.
Фактически переменная b играет роль ссылки на корень дерева (или адреса
корня в векторной памяти). Пустому дереву соответствовало бы значение
b=0, т.е. в этом представлении константа NillBT = 0. Элементы вектора, не за-
нятые под хранение узлов дерева, образуют свободную память, которую
удобно организовать в виде линейного циклического списка (для этого ис-
пользуется одно из полей звена Node (например, поле LSub)). При этом эле-
мент вектора с индексом (адресом) 0 играет роль ссылки на начало списка
свободной памяти.
                                             Связи списка           Бинарное
            LSu         Info        RSu       свободной              дерево:
                                               памяти:
                    2                                                   a
      0:
      1:            0     f     0
      2:            6                                               b       c

      3:            5     a     4
                    0     c     1                               d       e       f
      4:
      5:            8     b     7
      6:            9                                                   g
      7:           10     e     0
      8:            0     d     0
      9:           11
      10:           0     g     0
      11:          12
      12:           0


    Рис. 3.11. Пример ссылочного представления бинарного дерева на базе вектора.
        Справа – бинарное дерево; слева – его размещение в массиве, играющем
                             роль динамической памяти.

     Мы не будем более подробно рассматривать эту реализацию, поскольку
она во многом аналогична ссылочной реализации линейного списка на базе
вектора, рассмотренной ранее в 1.4.



                                        62

Страницы