9.18. Алгоритм построения ряда деревьев согласно ЭШ типа Г

Получает на вход пару деревьев – <T⚪, T◎>.

Рекурсивным применением строит ряд деревьев T1 ..TN, в котором:

• первый член совпадает с T◎
• соседние члены Ti и Ti+1 связаны элементарным шагом типа Г так, что все вершины дерева Ti, за исключением некоторого узла nd*, присутствуют в дереве Ti+1
• к последнему члену TN не применим никакой элементарный шаг типа Г, то есть, TN не имеет такого узла nd* с единственной непосредственно подчинённой вершиной nd⫰, для которых nd⫰ присутствует, а nd* отсутствует в T⚪

Содержательно:

1. в дереве T◎ ищет (любой) узел nd* с единственной непосредственно подчинённой вершиной nd⫰ такой, что nd⫰ присутствует, а nd* отсутствует в T⚪
2. если такой узел nd* существует:
   1. он удаляется из входящего T◎ с получением дерева T⦻
   2. T⦻ включается очередным членом в строящийся ряд деревьев
   3. алгоритм применяется рекурсивно к паре <T⚪, T⦻>
3. если такого дерева нет, происходит возврат с признаком окончания ряда

█

Назад Вперёд