flat assembler
Message board for the users of flat assembler.

Index > Windows > binary tree example for windows (console)

Author
Thread Post new topic Reply to topic
0.1



Joined: 24 Jul 2007
Posts: 474
Location: India
0.1
Code:
; ------------------------------------------------------------------------
; A Binary Tree example.
;
; The Tree is saved in a global pointer - Tree.
; Only insert and preorder, inorder & postorder functions are implemented.
; ------------------------------------------------------------------------

        format PE console

        include 'macro\import32.inc'

        section '.code' code readable executable
start:
; ------------------------------------------------------
; First insert ten random integers into our Binary Tree.
; ------------------------------------------------------
        mov ebx, 10
.insert_items:
        call dword [rand]
        and eax, 0xff
        push eax
        push tree
        call insert
        dec ebx
        jnz .insert_items
; ----------------------------------------------------------
; Now just do traversals of the Tree and print the integers.
; ----------------------------------------------------------

; PRE-ORDER
        push pre_msg
        call dword [printf]
        add esp, 4
        push dword [tree]
        call preorder

; IN-ORDER
        push in_msg
        call dword [printf]
        add esp, 4
        push dword [tree]
        call inorder

; POST-ORDER
        push post_msg
        call dword [printf]
        add esp, 4
        push dword [tree]
        call postorder

        push thanks
        call dword [printf]
        add esp, 4
        call dword [getchar]
; ----------------------
; End of the show. Exit!
; ----------------------
        push 0
        call dword [exit]

; ----------------------------------------------------------------
; Insert the item given in the Tree pointed by the address passed.
; Insert works in such a way that the  inorder traversal will give
; us results in non-decreasing sorted order.
; ----------------------------------------------------------------
insert:
root equ ebp+8
item equ ebp+12
        enter 0,0
        mov eax, [root]
        cmp dword [eax], 0
        jz .new_node
        mov ecx, [eax]
        mov edx, [item]
        cmp [ecx], edx
        jle .insert_right
; Otherwise insert left.
        add ecx, 4
.recursion:
        push edx
        push ecx
        call insert
        jmp .return
.insert_right:
        add ecx, 8
        jmp .recursion
.new_node:
        push 12
        call dword [malloc]
        add esp, 4
        mov ecx, [root]
        mov [ecx], eax
        mov edx, [item]
        mov [eax], edx
        mov dword [eax+4], 0
        mov dword [eax+8], 0
.return:
        leave
        ret 8

; -------------------------------------------------
; Travers the Tree in preorder and print each item.
; -------------------------------------------------
preorder:
root equ ebp+8

        enter 0,0
        cmp dword [root], 0
        jz .return

        mov eax, [root]
        push dword [eax]
        push str1
        call dword [printf]
        add esp, 8

        mov eax, [root]
        add eax, 4
        push dword [eax]
        call inorder

        mov eax, [root]
        add eax, 8
        push dword [eax]
        call inorder
.return:
        leave
        ret 4

; ------------------------------------------------
; Travers the Tree in inorder and print each item.
; ------------------------------------------------
inorder:
root equ ebp+8

        enter 0,0
        cmp dword [root], 0
        jz .return

        mov eax, [root]
        add eax, 4
        push dword [eax]
        call inorder

        mov eax, [root]
        push dword [eax]
        push str1
        call dword [printf]
        add esp, 8

        mov eax, [root]
        add eax, 8
        push dword [eax]
        call inorder
.return:
        leave
        ret 4


; ------------------------------------------------
; Travers the Tree in postorder and print each item.
; ------------------------------------------------
postorder:
root equ ebp+8

        enter 0,0
        cmp dword [root], 0
        jz .return

        mov eax, [root]
        add eax, 4
        push dword [eax]
        call inorder

        mov eax, [root]
        add eax, 8
        push dword [eax]
        call inorder

        mov eax, [root]
        push dword [eax]
        push str1
        call dword [printf]
        add esp, 8
.return:
        leave
        ret 4


        section '.data' data readable writable
NL equ 13,10
tree dd 0
pre_msg db NL,'Preorder Traversal: ',0
in_msg  db NL,'Inorder Traversal: ',0
post_msg db NL,'Postorder Traversal: ',0
thanks db NL,NL,'Thanks for watching this boring stuff.',NL,NL,'Now press <ENTER> to exit ',0
str1 db "%d ",0


        section '.idata' import data readable

library msvcrt,'msvcrt.dll'

import  msvcrt,\
        exit,'exit',\
        rand,'rand',\
        malloc,'malloc',\
        printf,'printf',\
        getchar,'getchar'

    


Last edited by 0.1 on 17 Sep 2007, 05:39; edited 7 times in total
Post 03 Sep 2007, 09:32
View user's profile Send private message Reply with quote
vid
Verbosity in development


Joined: 05 Sep 2003
Posts: 7105
Location: Slovakia
vid
did you try to debug it? if not, download OllyDebug and learn it.

people usually aren't in moodto lookfor your bugs Wink
Post 03 Sep 2007, 12:35
View user's profile Send private message Visit poster's website AIM Address MSN Messenger ICQ Number Reply with quote
0.1



Joined: 24 Jul 2007
Posts: 474
Location: India
0.1
Why they are showing so much reluctance!
Have I done something wrong (violated the forum rules, hurt some one ...) ?
You guys used to be way more helpful earlier!

Sad I am not at all comfortable using the debuggers Sad
Sad They scare me away Sad
Post 03 Sep 2007, 12:48
View user's profile Send private message Reply with quote
LocoDelAssembly
Your code has a bug


Joined: 06 May 2005
Posts: 4633
Location: Argentina
LocoDelAssembly
The inorder proc needs the pointer passed by value and you do that when you call it from main, however, the recursive calls does not respect the requirement and pass it by reference in the same way the recursive calls are made in insert proc (which is OK in that one).

Replace the push eax / call inorder pairs with push dword [eax] / call inorder .

The bug is very simple, however I wasn't able to figure it out myself after carefully reading, I had to use OllyDbg Sad This is soooo sad :'(

PS: BTW, remember to remove the "jmp .return" at inorder proc.
Post 03 Sep 2007, 13:26
View user's profile Send private message Reply with quote
0.1



Joined: 24 Jul 2007
Posts: 474
Location: India
0.1
binary tree example that prints the tree on console


Description:
Download
Filename: tree.asm
Filesize: 3.03 KB
Downloaded: 44 Time(s)


_________________
Code:
 o__=-
 )
(\
 /\  
    
Post 06 Oct 2007, 13:00
View user's profile Send private message Reply with quote
0.1



Joined: 24 Jul 2007
Posts: 474
Location: India
0.1
the binary tree example in HL macros syntax


Description: the binary tree example in HL macros syntax
Download
Filename: btree.asm
Filesize: 3.68 KB
Downloaded: 37 Time(s)


_________________
Code:
 o__=-
 )
(\
 /\  
    
Post 08 Oct 2007, 12:34
View user's profile Send private message Reply with quote
Display posts from previous:
Post new topic Reply to topic

Jump to:  


< Last Thread | Next Thread >
Forum Rules:
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
You cannot attach files in this forum
You can download files in this forum


Copyright © 1999-2020, Tomasz Grysztar. Also on YouTube, Twitter.

Website powered by rwasa.