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


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

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


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




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



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




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