; ------------------------------------------------------------------------
; 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 'win32axp.inc'

struct Node
       item dd ?
       left dd ?
       right dd ?
ends

	section '.code' code readable executable
start:
; ------------------------------------------------------
; First insert ten random integers into our Binary Tree.
; ------------------------------------------------------
	mov ebx, 10
.insert_items:
	cinvoke rand
	and eax, 0xff
	stdcall insert, tree, eax
	dec ebx
	jnz .insert_items

; ----------------------------------------------------------
; Now just do traversals of the Tree and print the integers.
; ----------------------------------------------------------

; PRE-ORDER
	cinvoke printf, pre_msg
	stdcall preorder, [tree]

; IN-ORDER
	cinvoke printf, in_msg
	stdcall inorder, [tree]

; POST-ORDER
	cinvoke printf, post_msg
	stdcall postorder, [tree]

	cinvoke printf, thanks
	cinvoke getchar

; ----------------------
; End of the show. Exit!
; ----------------------
	cinvoke exit, 0

; ----------------------------------------------------------------
; 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.
; ----------------------------------------------------------------
proc insert root, item
	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:
	stdcall insert, ecx, edx
	jmp .return
.insert_right:
	add ecx, 8
	jmp .recursion
.new_node:
	cinvoke malloc, 12
	mov ecx, [root]
	mov [ecx], eax
	mov edx, [item]
	mov [eax], edx
	mov dword [eax+4], 0
	mov dword [eax+8], 0
.return:
	ret
endp

; -------------------------------------------------
; Travers the Tree in preorder and print each item.
; -------------------------------------------------
proc preorder uses ebx, root
	mov ebx, [root]
	cmp ebx, 0
	jz .return

	cinvoke printf, str1, dword[ebx+Node.item]
	stdcall preorder, dword[ebx+Node.left]
	stdcall preorder, dword[ebx+Node.right]
.return:
	ret
endp

; ------------------------------------------------
; Travers the Tree in inorder and print each item.
; ------------------------------------------------
proc inorder uses ebx, root
root equ ebp+8
	mov ebx, [root]
	cmp ebx, 0
	jz .return

	stdcall inorder, dword[ebx+Node.left]
	cinvoke printf, str1, dword[ebx+Node.item]
	stdcall inorder, dword[ebx+Node.right]
.return:
	ret
endp

; ------------------------------------------------
; Travers the Tree in postorder and print each item.
; ------------------------------------------------
proc postorder uses ebx, root
	mov ebx, [root]
	cmp ebx, 0
	jz .return

	stdcall postorder, dword[ebx+Node.left]
	stdcall postorder, dword[ebx+Node.right]
	cinvoke printf, str1, dword[ebx+Node.item]
.return:
	ret
endp

	section '.data' data readable writable
NL equ 13,10
tree dd 0	; Pointer to Node
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'