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


Обход узлов дерева



Обход узлов дерева

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

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

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

: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.llh.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




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