Построение двоичного дерева (asm x86)

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 19:51, 9 августа 2015.

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

;+-------------------------------------------------------------------------+
;| Программа: prg02_12.asm. Построение и инициализация двоичного дерева. |
;+-------------------------------------------------------------------------+				
;| Вход: произвольный массив чисел в памяти.	           |
;+-------------------------------------------------------------------------+
;| Выход: двоичное дерево в памяти.                                           |
;+-------------------------------------------------------------------------+

node_tree        struc                                      ;узел дерева
symbol           db      0                                  ;содержательная часть
l_son	         dd      0	                            ; указатель на старшего (левого) сына
r_son	         dd      0	                            ; указатель на младшего (правого) сына
ends		
.data
mas              db	 37h. 12h. 8h. 65h. 4h. 54h. 11h. 02h. 32h. 5h
                 db    	  4h. 87h. 7h. 21h. 65h. 45h. 22h. 11h. 77h. 51h
                 db	 26h. 73h. 35h. 12h. 49h. 37h. 52h
                 l_mas = $ - mas
.code
BuildBinTree   proc            
         ;-----формируем корень дерева и указатель на дерево HeadTree.
         ;     Для размещения дерева используем кучу, выделяемую процессу 
         ;     по умолчанию (1 Мбайт), но при необходимости можно создать
         ;     и дополнительную кучу с помощью HeapCreate               
         ;-----HANDLE GetProcessHeap (VOID)
               call GetProcessHeap
               mov Hand_Head. eax                     ;сохраняем дискриптор
         ;-----запрашиваем и инициализируем блок памяти
         ;    из кучи для корня дерева
               xor ebx. ebx                                 ; будет указатель на предыдущий узел
         ;-----LPVOID HeapAlloc(HANDLE hHeap. DWORD dwFlags. DWORD dwBytes)
               push type node_tree                     ; размер структуры для узла дерева
               push 0                                          ; флаги не задаем
               push eax                                       ; описатель кучи
               call HeapAlloc
               mov HeadTree. eax                       ; запоминаем указатель на корень
               mov ebx. eax                                ; и в ebx
         ;-----подчистим выделенную область памяти в куче
               push ds
               pop es
               mov edi. eax
               mov ecx, type node_tree
               xor al. al
               cld
               rep stosb
               lea esi. mas                                   ; первое число из mas в корень дерева
               lodsb ; число в al
               mov [ebx]. symbol. al
         ;-----далее в цикле работаем с деревом и масивом mas
               mov ecx. l_mas - 1
         ;-----запращиваем блок памяти из кучи для узла дерева:
               ; LPVOID HeapAlloc (HANDLE hHeap. DWORD dwFlags. DWORD dwBytes)
@@cycl1:       push ecx                                ; HeapAlloc портит ecx. возвращая в нем некоторое значение
               push type node_tree                     ; размер структуры для узла дерева
               push 0                                          ; флаги не задаем
               push Hand_Head                           ; описатель куче
               call HeapAlloc
               pop ecx
               mov ebx. eax                                ; запоминаем указатель на узел дерева в ebx
               mov NewNode. eax                       ; и во временную переменную
         ;-----подчистим выделенную область памяти в куче
               mov edi. eax
               push ecx
               mov ecx. type node_tree
               xor al. al
               cld
               rep stosb
               pop ecx
         ;-----читаем очередное число из mas и записываем его в новый узел
               lodsb                                          ; число в al
               mov [ebx].symbol. al
         ;-----ищем место в дерево согласно условиям упорядочивания и настраиваем указатели в узлах дерева
               mov ebx. HeadTree
               m_search: cmp al. [ebx].symbol
               mov edi. ebx                               ; продублируем 
               jae m1 ; если al >= [ebx].symbol
         ;-----если меньше, то идем по левой ветке
               mov ebx. [ebx].l_son
               test ebx. ebx
               jnz m_search
         ;-----если этого сына нет, то добавляем его к "папе"
               mov ebx. NewNode
               mov [edi].l_son. ebx
               jmp end_cycl1
         ;-----если больше или равно, то по правой ветви
m1:            mov ebx. [ebx].r_son
               test ebx. ebx
               jnz m_search
         ;-----если этого сына нет, то добавляем его к "папе"
               mov ebx. NewNode
               mov [edi].r_son. ebx
               end_cycl1: loop @@cycl1
               ret                                              ; двоичное дерево поиска построено
BuildBinTree           endp
start          proc near                                 ; точка входи в программу
               call BuildBinTree
               ;...
end

В результате мы должны получить дерево, обойдя которое в определенном порядке, сформируем упорядоченный массив чисел: 2h. 4h. 4h. 5h. 7h. Вh. 11h. 11h. 12h. 12h. 21h. 22h. 2бh. 32h. 35h. 37h. 37h. 45h. 49h. 51h. 52h. 54h. 65h. 65h. 73h. 77h. 87h.