Сборник по задачам и примерам Assembler


Обход узлов дерева - часть 3


Включение узла в упорядоченное бинарное дерево

Задача включения узла в дерево уже была решена нами при построении дерева. Осталось оформить соответствующий фрагмент программы в виде отдельной процедуры addNodeTree. Чтобы не дублировать код, разработаем рекурсивный вариант процедуры включения — addNodeTree. Он хоть и не так нагляден, как нерекурсивный вариант кода в программе prg_03.asm, но выглядит достаточно профессионально. Текст процедуры addNodeTree вынесен на дискету.

Работу процедуры addNodeTree можно проверить с помощью программы prgO2_ 13.asm (в е ей соответствует программа prgO2_14.asm).

В результате проведенных работ мы получили дублирование кода, строящего и дополняющего дерево. В принципе для строительства и включения в дерево достаточно одной процедуры addNodeTree. Но в учебных целях мы ничего изменять не будем, чтобы иметь два варианта строительства дерева — рекурсивный и не рекурсивный. При необходимости читатель сам определит, какой из вариантов более всего отвечает его задаче и в соответствии с этим доработает этот код.

Исключение узла из упорядоченного бинарного дерева

Эта процедура более сложная. Причиной тому то обстоятельство, что существует несколько вариантов расположения исключаемого узла в дереве: узел является листом, узел имеет одного потомка и узел имеет двух потомков. Самый непростой случай — последний. Процедура удаления элемента del NodeTree является рекурсивной и, более того, содержит вложенную процедуру del, которая также является рекурсивной. Текст процедуры del NodeTree вынесен на дискету.

Работу этой процедуры можно проверить с помощью программы prg02_13.asm (в е ей соответствует программа prg02_15.asm).

Графически процесс исключения из дерева выглядит так, как показано на Рисунок 2.20. Исключаемый узел помечен стрелкой.

Рисунок 2.20. Исключение из дерева

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




- Начало -  - Назад -  - Вперед -