Иллюстрированный самоучитель по задачам и примерам Assembler › Сложные структуры данных › Дерево [страница - 73] | Самоучители по программированию

Дерево

;LPVOID HeapAllос(HANDLE hHeap, DWORD dwFlags, DWORD dwBytes):
push type node_tree:размер структуры для узла дерева
push 0;флаги не задаем
push eax:описатель кучи (он же в Hand_Head)
call НеарАllос
mov HeadTree.eax запоминаем указатель на корень дерева
mov ebx.eax:и в ebx:подчистим выделенную область памяти в куче
push ds
pop es
mov edi.eax
mov ecx.type node_tree
mov al.0 rep stosb
leaesi.mas;первое число из mas в корень дерева
lodsb;число в al
mov [ebx].simbol.al
mov ecx.l_mas-l @@cycll:;далее в цикле работаем с деревом и массивом mas
push ecx;НеарА11ос портит ecx. возвращая в нем некоторое значение
;запрашиваем блок памяти из кучи для узла дерева:
;LPVOID HeapAllос(HANDLE hHeap. DWORD dwFlags, DWORD dwBytes);
push type node_tree:размер структуры для узла дерева
push 0:флаги не задаем
push HandJHead:описатель кучи
call НеарАllос
pop ecx
mov ebx.eax запоминаем указатель на узел дерева в ebx
mov NewNode.eax:и во врем, перем.
;подчистим выделенную область памяти в куче
movedi.eax
push ecx
mov ecx.type node_tree
mov al.0 rep stosb
pop ecx
:читаем очередное число из mas и записываем его в новый узел lodsb:число в al mov [ebx].simbol,al
;ищем место в дереве согласно условиям упорядочивания;и настраиваем указатели в узлах дерева
mov ebx.HeadTree m_search: cmpal.[ebx].simbol mov edi.ebxпродублируем
jae ml:если al >= [ebxj.simbol:если меньше, то идем по левой ветке
mov ebx.[ebx].l_son
cmp ebx.O
jnem_search;если этого сына нет. то добавляем его к папе
mov ebx.NewNode
mov [edi].l_son.ebx
jmp end_cycl 1
:если больше или равно, то по правой ml: mov ebx. [ebx] .r_son
cmp ebx.O
jnem_search:если этого сына нет. то добавляем его к папе
mov ebx.NewNode
mov [edi].r_son.ebx end_cycll: loop @@cycll
ret;двоичное дерево поиска построено BuildBinTree endp start proc near
:точка входа в программу:
call BuildBinTree

В результате мы должны получить дерево, обойдя которое в определенном порядке, получим упорядоченный массив чисел:

2h.4h.4h,5h.7h,8h.9h.11h,12h.l2h.21h.22h.26h.32h,35h,37h.37h.
45h.49h.51h.52h. 54h.65h.65h.73h.77h.87h.

Убедимся в этом, разработав программу обхода двоичного дерева.

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

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

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

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

Отметим особенности функции LRBeat, производящей обход дерева. Во-первых, она рекурсивная, во-вторых, в ней для хранения адресов узлов используется свой собственный стек. Стек, поддерживаемый на уровне архитектуры микропроцессора, используется для работы процедурного механизма, и мы со своими проблемами только "путаемся у него под ногами".