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

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

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

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

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

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

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

и указателем

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

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

, содержимое узла, и

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

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

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

. При этом

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

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

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