Сборник по задачам и примерам 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);

Построение двоичного дерева


Сборник по задачам и примерам 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);



Содержание раздела






Содержание раздела