Вопрос №23. Деревья как АТД, набор операций. Реализация АТД - дерево (с помощью массивов, с использованием списка сыновей)

Список операций АТД TREE:

l MAKENULL(T) - создать пустое дерево;

l ROOT(T) - получить метку корня дерева;

l PARENT(n, T) - узнать родителя;

l LEFTMOST_CHILD(n, T) - самый левый сын;

l RIGHT_SIBLING(n, T) - правый брат;

l LABEL(n, T) получить метку узла;

l CREATE(n, T1, T2,...) - создать дерево из узла-корня и набора поддеревьев.

Рекурсивная функция, которая позволяет обходить дерево в порядке прямого обхода и составлять его
список:

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

Сама функция может работать в двух режимах:

1. обход по направлению к потомкам самого левого еще не проверенного пути дерева до тех пор, пока не встретится лист, при этом узлы заносятся в стек.

2. возврат по пройденному пути с поочередным извлечением узлов до тех пор, пока не встретится узел, имеющий еще неописанного правого брата.