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

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


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

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

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

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


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

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

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


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

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

,
,
. При этом

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

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



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