Построение двоичного дерева
Построение двоичного дерева
Как уже отмечалось выше, для реализации двоичного поиска необходим упорядоченный массив чисел. Поэтому уже на этапе построения двоичное дерево необходимо специальным образом организовать. Двоичное дерево поиска организуется так, что между его узлами существуют следующие соотношения: для каждого узла а, все элементы левого поддерева меньше а, а элементы правого поддерева больше либо равны а.
:prg02_12.asm - программа построения и инициализации двоичного дерева.
:Вход: произвольный массив чисел в памяти.
:Выход: двоичное дерево в памяти.
;объявления структур:
node_tree struc :узел дерева
simbol db 0 содержательная часть
l_son dd 0 указатель на старшего (левого) сына
r_son dd 0 указатель на младшего (правого) сына
ends
.data
mas db 37h.12h.8h.65h.4h.54h.llh.02h.32h.5h.4h.87h.7h.21h.65h.45h.22h.
Ilh,77h.51h,26h.73h.35h.l2h.49h.37h.52h l_mas=$-mas
.code
BuildBinTree proc
формируем корень дерева и указатель на дерево HeadTree
:для размещения дерева используем кучу, выделяемую процессу по умолчанию (1 Мбайт).
:но при необходимости можно создать и доп. кучу с помощью HeapCreate
iHANDLE GetProcessHeap (VOID):
call GetProcessHeap
movHand_Head,eax сохраняем дескриптор ;запрашиваем и инициализируем блок памяти из кучи для корня дерева:
xorebx.ebx :здесь будет указатель на предыдущий узел ;LPVOID HeapAllос(HANDLE hHeap, DWORD dwFlags, DWORD dwBytes):
push type node_tree :размер структуры для узла дерева
push 0 ;флаги не задаем
push eax :описатель кучи (он же в Hand_Head)
call НеарАПос
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);
Сборник по задачам и примерам Assembler
Построение двоичного дерева
Построение двоичного дерева
Как уже отмечалось выше, для реализации двоичного поиска необходим упорядоченный массив чисел. Поэтому уже на этапе построения двоичное дерево необходимо специальным образом организовать. Двоичное дерево поиска организуется так, что между его узлами существуют следующие соотношения: для каждого узла а, все элементы левого поддерева меньше а, а элементы правого поддерева больше либо равны а.
:prg02_12.asm - программа построения и инициализации двоичного дерева.
:Вход: произвольный массив чисел в памяти.
:Выход: двоичное дерево в памяти.
;объявления структур:
node_tree struc :узел дерева
simbol db 0 содержательная часть
l_son dd 0 указатель на старшего (левого) сына
r_son dd 0 указатель на младшего (правого) сына
ends
.data
mas db 37h.12h.8h.65h.4h.54h.llh.02h.32h.5h.4h.87h.7h.21h.65h.45h.22h.
Ilh,77h.51h,26h.73h.35h.l2h.49h.37h.52h l_mas=$-mas
.code
BuildBinTree proc
формируем корень дерева и указатель на дерево HeadTree
:для размещения дерева используем кучу, выделяемую процессу по умолчанию (1 Мбайт).
:но при необходимости можно создать и доп. кучу с помощью HeapCreate
iHANDLE GetProcessHeap (VOID):
call GetProcessHeap
movHand_Head,eax сохраняем дескриптор ;запрашиваем и инициализируем блок памяти из кучи для корня дерева:
xorebx.ebx :здесь будет указатель на предыдущий узел ;LPVOID HeapAllос(HANDLE hHeap, DWORD dwFlags, DWORD dwBytes):
push type node_tree :размер структуры для узла дерева
push 0 ;флаги не задаем
push eax :описатель кучи (он же в Hand_Head)
call НеарАПос
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);