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


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


:двоичное дерево поиска построено

ret

BuildBinTree endp LRBeat proc

:рекурсивная процедура обхода дерева - слева направо :(левое поддерево, корень, правое поддерево)

inc count_call ;подсчет количества вызовов процедуры

:(для согласования количества записей и извлечений из стека)

cmp ebx.O

je @@exit_p

mov ebx.[ebx].l_son

cmp ebx, 0

je @@ml

push_stk doubleWord_stk.ebx mini: call LRBeat

pop stkdoubleWord stk.ebx

r r_ —

jnc @@m2

:подчистим за собой стек и на выход raovecx.count_call

dec ecx

pop NewNode:pop "в никуда"

loop $-6

jmp @@exi t_p @@m2: moval,[ebx].simbol

stosb

mov ebx, [ebx]. r_son cmp ebx.O je @@ml push stk doubleWord stk.ebx

c'all LRBeat " @@exit_p: deccount_call

ret

LRBeat endp start proc near ;точка входа в программу:

call BuildBinTree :формируем двоичное дерево поиска ;обходим узлы двоичного дерева слева направо и извлекаем значения ;из содержательной части, нам понадобится свой стек (размер (256 байт) нас устроит. :но макроопределение мы подкорректировали)

create_stk Hand_Head.doubieWord_stk

push ds

pop es

lea edi.ordered_array

mov ebx.HeadTree push_stk doubleWord_stk.ebx указатель на корень в наш стек

call LRBeat

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

Для полноты изложения осталось только показать, как изменится процедур;!. LRBeat для других вариантов обхода дерева.

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




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