С помощью массивовПусть дерево T имеет узлы 1, 2, …., n. Возможно, самым простым представлением дерева T будет линейный массив A, где каждый элемент A [ i ] содержит номер родительского узла (является курсором на родителя). Поскольку корень дерева не имеет родителя, то его курсор будет равен 0. Рассмотрим примеры. Представляется линейным массивом(например А), где каждый элемент А[i] является указателем на родителя узла i. Корень дерева отличается от других узлов тем, что имеет нулевой указатель или указатель на самого себя как на родителя. Для заданного дерева вверху запись указателей будет иметь следующий вид
Каждый узел, кроме корня, имеет только одного родителя, что позволяет найти родителя за фиксированное время. Для приведенного на рисунке дерева внизу построим линейный массив по следующему правилу: A [ i ]= j, если узел j является родителем узла i, A [ i ]=0, если узел i является корнем. Тогда массив будет выглядеть следующим образом:
|
