Дерево
:prg02_13.asm – программа обхода двоичного дерева поиска (слева направо). ;Вход: произвольный массив чисел в памяти. :Выход: двоичное дерево в памяти. объявления структур: nodejxee struc:узел дерева ends : для программного стека desc_stk struc:дескриптор стека ends ;описание макрокоманд работы со стеком: create_stk macro HandHead:REQ.descr:REQ.Si zeStk: = <256> ¦.создание стека endm push_stk macro descr:REQ.rg_item:REQ добавление элемента в стек endm pop_stkmacro descr:REQ .rg_item:REQ извлечение элемента из стека endm .data исходный массив: masdb 37h.l2h,8h.65h.4h.54h.11h.02h.32h,5h,4h,87h.7h.21h.65h.45h.22h,llh.77h. 51h.26h.73h.35h.12h.49h.37h.52h l_mas=$-mas упорядоченный массив (результат см. в отладчике): ordered array db 1 mas dup (0) doubleWord_stkdesc_stk <> – . дескриптор стека count call dd 0:счетчик количества рекурсивного вызова процедуры .code BuildBinTree proc;см .prg02_12.asm :двоичное дерево поиска построено 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. Более подробные сведения о сбалансированных деревьях вы можете получить, изучая соответствующую литературу. Здесь же будем считать, что сбалансированное дерево уже построено. Разберемся с тем, как производить включение и исключение узлов в подобном, заранее построенном упорядоченном дереве.