Основные операторы, используемые для работы с деревьями

МЕТОД ВЛОЖЕННЫХ СКОБОК

(V0(V1(V2(V5)(V6))(V3)(V4))(V7(V8)(V9(V10))))

Рис. 20 -Представление дерева: а)- исходное дерево, б)- оглавление книг, в)- граф, г)- диаграмма Венна

Все эти представления демонстрируют одну и ту же структуру и поэтому эквивалентны. С помощью графа можно наглядно представить разветвляющиеся связи, которые по понятным причинам привели к общеупотребительному термину "дерево".

Дерево и лес любого вида можно преобразовать единственным образом в эквивалентное бинарное дерево.

Правило построения бинарного дерева из любого дерева:

1. В каждом узле оставить только ветвь к старшему сыну (вертикальное соединение);

2. Соединить горизонтальными ребрами всех братьев одного отца;

3. Таким образом перестроить дерево по правилу:

левый сын - вершина, расположенная под данной;

правый сын - вершина, расположенная справа от данной (т.е. на одном ярусе с ней).

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

В результате преобразования любого дерева в бинарное получается дерево в виде левого поддерева, подвешенного к корневой вершине.

В процессе преобразования правый указатель каждого узла бинарного дерева будет указывать на соседа по уровню. Если такового нет, то правый указатель NIL. Левый указатель будет указывать на вершину следующего уровня. Если таковой нет, то указатель устанавливается на NIL.

Рис.21 - Исходное дерево

Рис. 22 - Промежуточный результат перестройки дерева

Рис. 23 - Представление дерева в виде бинарного

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

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

1. PARENT – это оператор, который возвращает родителя для заданного узла из «дерева». Если заданный узел является корнем, то оператор возвращает условный знак, обозначающий «нулевой узел», что соответствует выходу за пределы «дерева».

2. LEFTMOST_CHILD – этот оператор используется для определения самого левого сына заданного узла в «дереве». Если заданный узел является листом, то возвращается знак, обозначающий «нулевой узел», так как он не имеет сына.

3. RIGHT_SIBLING – этот оператор возвращает правого брата заданного узла из «дерева» или знак, обозначающий «нулевой узел», если такого не существует. Для этого находится родитель для заданного узла, а потом и все сыновья найденного родителя, затем среди этих сыновей находится узел, расположенный справа от заданного узла.

4. LABEL – осуществляет возврат метки заданного узла из «дерева». Для этого необходимо, чтобы на узлах «дерева» были определены метки.

5. CREATEi – семейство операторов, создающих новый корень с определённой меткой, а далее для этого корня создаёт i сыновей, которые становятся корнями следующих поддеревьев. Эти операторы создают «дерево» с определённым корнем. Если i=0, то будет создан лишь один узел, который является одновременно и корнем, и листом.

6. ROOT– этот оператор создаёт корень «дерева». Если в «дереве» ещё нет элементов, то возвращается знак, который говорит о том, что «дерево» пустое.

7. MAKENULL – этот оператор делает заданное «дерево» пустым.