Обход узлов дерева (asm x86)

Возможны три варианта обхода дерева:

• сверху вниз - корень, левое поддерево,правое поддерево;
• слева направо - левое поддерево,корень,правое поддерево;
• снизу вверх - левое поддерево,правое поддерево,корень.

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

Код программы prg02_13.asm:

;+-------------------------------------------------------------------------+
;| Программа: prg02_13.asm. Обход двоичного дерева поиска (слева направо). |
;+-------------------------------------------------------------------------+				
;| Вход: двоичное дерево в памяти (строится по массиву чисел).	           |
;+-------------------------------------------------------------------------+
;| Выход: массив числе в памяти.                                           |
;+-------------------------------------------------------------------------+

node_tree        struc                                      ;узел дерева
symbol           db      0                                  ;содержательная часть
l_son	         dd      0	                            ; указатель на старшего (левого) сына
r_son	         dd      0	                            ; указатель на младшего (правого) сына
ends		
desc_stk	struc	                                    ; дескриптор программного стека
                ;...
ends		
        ;-------списание макрокоманд работы со стеком 
        ;-------создание стека
create_stk      macro handHead:REQ. descr:REQ. SizeStk:=<256>
endm
        ;добавление элемента в стек
push_stk        macro descr:REQ. rg_item:REQ
                ;...        
endm
pop_stk         macro descr:REQ. rg_item:REQ
                ;...
endm
.data
mas            db	37h. 12h. 8h. 65b. 4h. 54h. llh. 02h. 32h. 5h. 4h
               db	87h. 7h. 21h. 65h. 45h. 22b. llh. 77b.	51h. 26b
               db	73h. 3Sh. 12b. 49b. 37h. 52h ; исходный	массив
               l mas = $ - mas
ordered_array  db	l_mas dup  (0)	                ; упорядоченный массив
                                                        ; (результат см. в отладчике)  
doubleword_stk descr_stk <>                             ;дескриптор стека
count_call     dd       0                               ;счетчик рекурсивного вызова процедуры
.code
BuildBinTree   proc                                     ;см. prg02_12.asm
               ;...
         ;-----двоичное дерево поиска построено
               ret
BuildBinTree   endp
LRBeat         proc
         ;-----рекурсивная процедура обхода дерева - слева направо
         ;    (левое поддерево, корень, правое поддерево)
              inc       count_call                      ;подсчет количества вызовов процедуры
                                                        ;(для согласования количества записей и извлечений из стека)
              test      ebx. ebx
              jz        @@exit_p
              mov       ebx. [ebx]. l_son
              test      ebx. ebx
              jz        @@ml
              push_stk  doubleWord_stk. ebx
@@ml:         call      LRBeat
              pop_stk   doubleWord_stk. ebx
              jnc       @@m2
        ;-----подчистим за собой стек и на выход
             mov        ecx. count_call
             dec        ecx
             pop        NewNode       ;pop "в никуда"  
             loop       $ - 6
             jmp        @@exit_p
@@m2:        mov        al. [ebx]. symbol
             cld
             stosb
             mov       ebx. [ebx]. r_son
             test      ebx. ebx
             jz        @@ml
             push_stk  doubleWord_stk. ebx 
             call      LRBeat
@@exit_p:    dec       count_call
             ret
LRBeat       endp
Start        proc      near                            ; точка входа в программу
             call      BuildBinTree                    ; формируем двоичное дерево поиска
      ;-----Обходим узлы двоичного дерева слева направо и извлекаем
      ;     значения из содержательной части, нам понадобиться
      ;     свой стек (размер 256 байтов устроит), но макроопределение мы подкорректировали)
            creat_stk Hand_Head. doubleWord_stk
            push       ds
            pop        es
            lea        edi. ordered_array
            mov        ebx. HeadTree
            push_stk Hand_Head. doubleWord_stk. ebx      ;указатель на корень в наш стек
            call       LRBeat
           ;...

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

Для полноты изложения осталось только показать, как измениться процедура LBBeat для других вариантов обхода дерева. Варианты обеих операций, UDBeat и RLBeat, можно найти среди файлов, прилагаемых к книге.

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