Комбинаторные алгоритмы для программистов



             

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


Почти все машинные представления деревьев основаны на связанных распределениях. Каждый узел состоит из поля

INFO
и нескольких полей для указателей. Например, представление, которое будет удобным для изложения множества и мультимножества, для каждого узла имеет единственное поле для указателя
FATHER
, указывающего на отца данного узла. При этом приведенное на рис. 4.1 дерево будет выглядеть так, как показано на рис. 4.6.

Такое представление полезно, если необходимо подниматься по дереву от потомков к предкам. Такая операция встречается довольно редко. Чаще требуется опуститься по дереву от предков к потомкам.

Представление дерева (или леса) с использованием указателей, ведущих от предков к потомкам, довольно сложно, поскольку узел, имея не более чем одного отца, может в то же время иметь произвольно много сыновей. Другими словами, при таком представлении узлы должны различаться по размеру, что является определенным неудобством. Один из путей обхода этой трудности состоит в том, чтобы определить соответствие между деревьями и бинарными деревьями, поскольку бинарные деревья легко представить узлами фиксированного размера.


Рис. 4.5.  Дерево из рис. 4.1, представленное с помощью узлов с полем
INFO
и указателем
FATHER

Каждый узел в этом случае имеет три поля:

LEFT
, указатель местоположения корня левого поддерева,
INFO
, содержимое узла, и
RIGHT
, указатель местоположения корня правого поддерева. Все сказанное выше проиллюстрировано на рис. 4.6.


Рис. 4.6.  Бинарное дерево и его представление с помощью узлов с тремя полями
LEFT
,
INFO
,
RIGHT

Можно представлять деревья как бинарные, используя узлы фиксированного размера, представляя каждый узел леса в виде узла, состоящего из полей

LEFT
,
INFO
,
RIGHT
. При этом
LEFT

предназначается для указания самого левого сына данного узла, а поле

RIGHT
- для указания следующего брата данного узла.




Содержание  Назад  Вперед