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

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

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

• первый член совпадает с T◎
• соседние члены Ti и Ti+1 связаны элементарным шагом типа В с основой T∆ так, что все элементы дерева T∆, за исключением корня nd, отсутствуют в дереве Ti+1
• к последнему члену TN не применим никакой элементарный шаг типа В, то есть, нет такого узла nd, у которого (непустая) часть всех выходящих из него дуг отсутствовала бы в T⚪

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

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

Назад Вперёд