9.11. Алгоритм построения дерева согласно ЭШ типа Б)

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

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

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

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

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

█

Назад Вперёд