Here's some snippets on creating the barebones of a binary tree using ASM. I know that there are a lot of optimizations that should be done and topics like deleting from a tree, that should be included here but since I have a lot of things to do, I'll leave it up to those who will use it. If I can find a time, I'll release some examples, together with the updated linked list project.

CurNode == rootNode
[size=9]

PrefixPrint PROC CurNode:DWORD

mov eax, CurNode
or eax, eax
jnz @F
ret

@@:

push eax
invoke dwtoa, (BINTREE PTR[eax]).ID, OFFSET tmpBufr
invoke SendDlgItemMessage, wHndle, IDE_BINTREEOUTPUT, EM_REPLACESEL, NULL, OFFSET Newline
invoke SendDlgItemMessage, wHndle, IDE_BINTREEOUTPUT, EM_REPLACESEL, NULL, OFFSET tmpBufr
pop eax
push eax
mov eax, (BINTREE PTR[eax]).ptLeft
invoke PrefixPrint, eax
pop eax
mov eax, (BINTREE PTR[eax]).ptRight
invoke PrefixPrint, eax

ret

PrefixPrint ENDP
[/size]

IDValue == id/key of the structure
[size=9]

CreateNode PROC IDValue:DWORD

invoke GetProcessHeap
mov hPrcs, eax
invoke HeapAlloc, eax, HEAP_ZERO_MEMORY, SIZEOF BINTREE
mov hMem, eax

mov edx, IDValue
mov (BINTREE PTR [eax]).ID, edx
mov (BINTREE PTR [eax]).ptLeft, NULL
mov (BINTREE PTR [eax]).ptRight, NULL

ret

CreateNode ENDP
[/size]
CurNode == rootNode
IDValue == id/key of the structure
[size=9]

FindASpot PROC CurNode:DWORD, IDValue:DWORD

mov eax, CurNode
or eax, eax
jnz @@NodeNotNull
ret

@@NodeNotNull:

mov edx, IDValue
push eax
push edx

cmp edx, (BINTREE PTR [eax]).ID
jl @@GoLeft
ja @@GoRight

invoke MessageBox, NULL, OFFSET BinTreeError, OFFSET BinTreeTitle, MB_OK
pop edx
pop eax
ret

@@GoLeft:

cmp (BINTREE PTR [eax]).ptLeft, NULL
jne @@RecurseOnLeft

push eax
invoke CreateNode, edx
pop ecx
mov (BINTREE PTR [ecx]).ptLeft, eax
jmp @@FoundASpot

@@RecurseOnLeft:

mov eax, (BINTREE PTR [eax]).ptLeft
invoke FindASpot, eax, edx
jmp @@FoundASpot

@@GoRight:

cmp (BINTREE PTR [eax]).ptRight, NULL
jne @@RecurseOnRight

push eax
invoke CreateNode, edx
pop ecx
mov (BINTREE PTR [ecx]).ptRight, eax
jmp @@FoundASpot

@@RecurseOnRight:

mov eax, (BINTREE PTR [eax]).ptRight
invoke FindASpot, eax, edx

@@FoundASpot:

pop edx
pop eax

ret

FindASpot ENDP
[/size]
nNode == rootNode
[size=9]

DestroyTree PROC nNode:DWORD

mov eax, nNode
or eax, eax
jnz @F
ret

@@:

push eax
mov eax, (BINTREE PTR[eax]).ptLeft
invoke DestroyTree, eax
pop eax
push eax
mov eax, (BINTREE PTR[eax]).ptRight
invoke DestroyTree, eax
pop eax
invoke HeapFree, hPrcs, NULL, eax

ret

DestroyTree ENDP
[/size]
The use of the Win32 API and the structure fields should be self explanatory. If you have questions tell me.

BTW, bitRAKE`s gonna love this because it has a lot of recursion :grin:

Have Fun!!! :grin:
Posted on 2002-04-01 00:36:41 by stryker
Hi Stryker

Can you send the whole program?, Then I can disect and maybe figure it out, THis is funny I just came back from my Data Structures class in C++, and binary trees was the lecture, and I have to write a Binary Tree program in C++ too
Wow!

Andy
Posted on 2002-04-01 10:56:22 by andy981
I would love to release the source but the problem is, this is also my homework :) My professor knows this board and I don't want to ... I'll just post a part of the whole code on how to do it. This should suffice your question but not totally.
[size=9]

@@BTN_ADDTOBTREE:

invoke GetDlgItemInt, hWnd, IDE_INTOBTREE, OFFSET bState, FALSE

cmp rootNode, NULL
jne @@rootExists

invoke CreateNode, eax
mov rootNode, eax
jmp @@PRINTCURRENTBINTREE

@@rootExists:

invoke FindASpot, rootNode, eax

@@PRINTCURRENTBINTREE:

invoke SetDlgItemText, hWnd, IDE_BINTREEOUTPUT, NULL
invoke PrefixPrint, rootNode
jmp @@RETURN_TRUE[/size]
Assuming we clicked a button called AddToTree...
1. First we get the key/id number of the node from an edit box.
2. We then check if a root node exists,

if not we will call CreateNode, the return value will be the pointer in memory that was allocated.

if it exists we will call the FindASpot procedure, what this does is it will recurse until it finds the right spot to place the leaf node.

3. Then print the current members of the current tree.


I forgot to add these 2 things on how to print the tree. :)
[size=9]

InfixPrint PROC CurNode:DWORD

mov eax, CurNode
or eax, eax
jnz @F
ret

@@:

push eax
mov eax, (BINTREE PTR[eax]).ptLeft
invoke InfixPrint, eax
pop eax
push eax
invoke dwtoa, (BINTREE PTR[eax]).ID, OFFSET tmpBufr
invoke SendDlgItemMessage, wHndle, IDE_BINTREEOUTPUT, EM_REPLACESEL, NULL, OFFSET Newline
invoke SendDlgItemMessage, wHndle, IDE_BINTREEOUTPUT, EM_REPLACESEL, NULL, OFFSET tmpBufr
pop eax
mov eax, (BINTREE PTR[eax]).ptRight
invoke InfixPrint, eax

ret

InfixPrint ENDP

PostfixPrint PROC CurNode:DWORD

mov eax, CurNode
or eax, eax
jnz @F
ret

@@:

push eax
mov eax, (BINTREE PTR[eax]).ptLeft
invoke PostfixPrint, eax
pop eax
push eax
mov eax, (BINTREE PTR[eax]).ptRight
invoke PostfixPrint, eax

pop eax
invoke dwtoa, (BINTREE PTR[eax]).ID, OFFSET tmpBufr
invoke SendDlgItemMessage, wHndle, IDE_BINTREEOUTPUT, EM_REPLACESEL, NULL, OFFSET Newline
invoke SendDlgItemMessage, wHndle, IDE_BINTREEOUTPUT, EM_REPLACESEL, NULL, OFFSET tmpBufr

ret

PostfixPrint ENDP[/size]
If spring semester is over I'll release the whole source. ;) Here are the structures and "variables" I used
[size=9]

_DATA SEGMENT
Newline DB 0Dh, 0Ah, 0
BinTreeTitle DB "stryker", 0
BinTreeError DB "Cannot Add To The Tree. Current", 0Dh, 0Ah
DB "ID Value Already Exists On The Tree.", 0
_DATA ENDS

_BSS SEGMENT
tmpBufr DB 9 DUP(?)
bState DD ?
hPrcs DD ?
hMem DD ?
rootNode DD ?
wHndle DD ?
_BSS ENDS

BINTREE STRUCT
ID DD ?
ptLeft DD ?
ptRight DD ?
BINTREE ENDS
[/size]
Posted on 2002-04-01 12:07:23 by stryker
Originally posted by stryker
I would love to release the source but the problem is, this is also my homework :) My professor knows this board and I don't want to ...


Why don't you just copyright your work with your real name...
Since the day of posting is also shown on the board it will validate your claim that this is your material...

For me... Code snippets are nice (for proof of concept), but don't really help when I'm just learning about a topic...

I do understand your concern and will just have to wait till you leave school for this program :)

Sliver
Posted on 2002-04-01 13:22:27 by Sliver
Here's another one on searching for a node in the tree
[size=9]

BSearch PROC nNode:DWORD, IDValue:DWORD

mov eax, nNode
mov edx, IDValue

@@SwingNode:

cmp eax, NULL
je @@BSearchExit

cmp edx, (BINTREE PTR [eax]).ID
jl @@GoLeft
ja @@GoRight
ret

@@GoLeft:

mov eax, (BINTREE PTR [eax]).ptLeft
jmp @@SwingNode

@@GoRight:

mov eax, (BINTREE PTR [eax]).ptRight
jmp @@SwingNode

@@BSearchExit:

xor eax, eax
ret

BSearch ENDP
[/size]
The return value will be in EAX, if it returns 0 then the key/id doesn't exists, else ...

Preliminary call: invoke BSearch, rootNode, IDorKeyToSearch


Have Fun!!! :grin:
Posted on 2002-04-02 23:49:45 by stryker
Here's another update. This one will count all the nodes in a tree.
[size=9]

BCount PROC nNode:DWORD, nCount:DWORD

mov eax, nCount
mov ecx, nNode
or ecx, ecx
jz @F
inc eax
push ecx
mov ecx, (BINTREE PTR [ecx]).ptLeft
invoke BCount, ecx, eax
pop ecx
mov ecx, (BINTREE PTR [ecx]).ptRight
invoke BCount, ecx, eax
@@:

ret

BCount ENDP
[/size]
Return value will be in eax.

Preliminary Call: invoke BCount, rootNode, 0


Have Fun!!! :grin:
Posted on 2002-04-03 23:10:20 by stryker
I forgot: To those who wants to optimized the procedures, I'll give you a hint: There are redundant codes and too much overkill parameters on the procedures. ;) You can initialize some parts even before a procedure is called.
Posted on 2002-04-03 23:43:18 by stryker
Here's another update:
[size=9]

Max PROC A:DWORD, B:DWORD

mov eax, A
mov edx, B
cmp eax, edx
jb @F
ret
@@:
mov eax, edx
ret

Max ENDP

BHeight PROC nNode:DWORD

mov ecx, nNode
or ecx, ecx
jnz @F
mov eax, -1
ret
@@:

push ecx
mov ecx, (BINTREE PTR [ecx]).ptLeft
invoke BHeight, ecx
pop ecx
push eax
mov ecx, (BINTREE PTR [ecx]).ptRight
invoke BHeight, ecx
pop edx
inc eax
inc edx
invoke Max, eax, edx
ret

BHeight ENDP

BLevel PROC nNode:DWORD

mov ecx, nNode
or ecx, ecx
jnz @F
xor eax, eax
ret
@@:

push ecx
mov ecx, (BINTREE PTR [ecx]).ptLeft
invoke BLevel, ecx
pop ecx
push eax
mov ecx, (BINTREE PTR [ecx]).ptRight
invoke BLevel, ecx
pop edx
inc eax
inc edx
invoke Max, eax, edx
ret

BLevel ENDP
[/size]

    [*]BHeight will give you the height of the tree.
    [*]BLevel will give you the level of the tree.
    [*]Preliminary Call: invoke Function, rootNode
    [*]Return Value/s : in EAX.

    Have Fun!!! :grin:
Posted on 2002-04-05 23:56:03 by stryker
Hi Stryker

Maybe you can do me a big favor,
Sorry for polutting the site with C++
but maybe you have done Binary Tree in C++
and I can't seem to get a working delete function going
here is what Is the worth while part I have


int tree::remove(NodePtr tPtr,int key)
{

int rt_child = 0, lft_child = 0;
NodePtr ptr = tPtr, parent = tPtr,dltPtr, S = tPtr, save = tPtr;
if (root == NULL)
return 0;
else
{
if (ptr == NULL)
return 0;
//this is good because it finds the parent
while (ptr != NULL && ptr->myKey != key) {
parent = ptr;
if (key < ptr->myKey) ptr = ptr->left;
else ptr = ptr->right;
}

}
}

Do you have any ideas!
Posted on 2002-04-08 22:46:28 by andy981
I have one in C but it's on the other computer at my home. When I get back I'll post the source. :)

Since I don't have my tools right now, I'll just give you some ideas on how to work it out.

1. First you need to search for the key inside the tree and check if it exists, if it does there are 3 cases you need to consider:

Case 1: If the node to be deleted is a leaf, meaning no right and left child, just deallocate it and nullify the pointer of the parent(left or right whichever it points to the deallocated node). You also need to be careful if it's the root node.

Case 2: If the node has only one child(either left or right), just update the parent of that node to point to the child of the node deallocated. Meaning if I have a tree like this A->B->C and I want to remove B just make A point to C and deallocate B. Again you need to be careful on which pointer(left or right) to update.

Case 3: If the node has two children, There are 2 ways to solve it. From the node to be deallocated:

1. Find the largest value on the left subtree and pick that value to replace the node to be deallocated then resort to either cases 1 and 2.

2. Find the smallest value on the right subtree and pick that value to replace the node to be deallocated then resort to either cases 1 and 2.
Posted on 2002-04-08 22:59:28 by stryker
I sent a zip of what I already have done

It should run and quite easily if you have Visual C++

just put in a folder and click the dsw file

the function in question is

the class function

called
int tree::remove(NodePtr tPtr,int key)


in the implementation file tree.cpp

THanks Andy
Posted on 2002-04-08 23:30:13 by andy981
Here's my Binary Trees in C. Sorry for the ugly text positions on the console, this was just a testbed. :)
Posted on 2002-04-09 00:09:01 by stryker
That should help a lot,

I'll test it more later today, I'm sure the delete will work,

Andy
Posted on 2002-04-09 07:10:45 by andy981
Yes, I'm back from my vacation and will go for another one tomorrow. :)

Here's the final installment for the binary trees. I don't know if this one works perfectly but I did my best to hunt down the bugs. :)

To remove a node from the tree, just pass the root node and the key of the node to delete and call BDelete.
[size=9]

BRemove PROC nParent:DWORD, nNode:DWORD

mov ecx, nParent
mov eax, nNode

cmp (BINTREE PTR [eax]).ptLeft, NULL
jne @@CheckRightNode
cmp (BINTREE PTR [eax]).ptRight, NULL
jne @@ChildOnRight

;Leaf Node

cmp eax, rootNode
jne @F
mov rootNode, 0
jmp @@DeallocateNode
@@:

cmp (BINTREE PTR [ecx]).ptLeft, eax
jne @@NullifyRight
mov (BINTREE PTR [ecx]).ptLeft, NULL
jmp @@DeallocateNode

@@NullifyRight:

mov (BINTREE PTR [ecx]).ptRight, NULL
jmp @@DeallocateNode

@@CheckRightNode:

cmp (BINTREE PTR [eax]).ptRight, NULL
jne @@TwoChildren

;Child On Left

or ecx, ecx
jnz @F

mov ecx, (BINTREE PTR [eax]).ptLeft
mov rootNode, ecx
jmp @@DeallocateNode

@@:

cmp (BINTREE PTR [ecx]).ptLeft, eax
je @@JoinLeft

mov edx, (BINTREE PTR [eax]).ptLeft
mov (BINTREE PTR [ecx]).ptRight, edx
jmp @@DeallocateNode

@@JoinLeft:

mov edx, (BINTREE PTR [eax]).ptLeft
mov (BINTREE PTR [ecx]).ptLeft, edx
jmp @@DeallocateNode

@@ChildOnRight:

;Child On Right

or ecx, ecx
jnz @F

mov ecx, (BINTREE PTR [eax]).ptRight
mov rootNode, ecx
jmp @@DeallocateNode

@@:

cmp (BINTREE PTR [ecx]).ptLeft, eax
je @@JoinRight

mov edx, (BINTREE PTR [eax]).ptRight
mov (BINTREE PTR [ecx]).ptRight, edx
jmp @@DeallocateNode

@@JoinRight:

mov edx, (BINTREE PTR [eax]).ptRight
mov (BINTREE PTR [ecx]).ptLeft, edx
jmp @@DeallocateNode

@@TwoChildren:

;Two Child Nodes

mov edx, eax
mov ecx, eax
mov eax, (BINTREE PTR [eax]).ptLeft

@@FindTheLargestKey:

cmp (BINTREE PTR [eax]).ptRight, NULL
je @@Replace
mov ecx, eax
mov eax, (BINTREE PTR [eax]).ptRight
jmp @@FindTheLargestKey

@@Replace:

;Just copy the contents to its new location

push (BINTREE PTR [eax]).pID
pop (BINTREE PTR [edx]).pID

;Process other structure field names.

;Revert to the 2 cases above. Because the one to replace
;cannot be and will not have 2 child nodes. The one to replace
;will either fall into cases 1 and 2 which is either a leaf node
;or a node with only one child.

invoke BRemove, ecx, eax
ret

@@DeallocateNode:

invoke HeapFree, hPrcs, NULL, eax
ret

BRemove ENDP

BDelete PROC nNode:DWORD, IDValue:DWORD

mov eax, nNode
mov edx, IDValue

@@SwingNode:

or eax, eax
jz @@BSearchExit

cmp edx, (BINTREE PTR [eax]).pID
jl @@GoLeft
ja @@GoRight

invoke BRemove, ecx, eax
ret
@@GoLeft:

mov ecx, eax
mov eax, (BINTREE PTR [eax]).ptLeft
jmp @@SwingNode

@@GoRight:

mov ecx, eax
mov eax, (BINTREE PTR [eax]).ptRight
jmp @@SwingNode

@@BSearchExit:

xor eax, eax
ret

BDelete ENDP[/size]
I'll be in Lake Tahoe tomorrow, then to Vegas then to Grand Canyon then to Utah... So long suckerz... :grin:

And no I didn't went to prison or jail!!! :grin:
Posted on 2002-04-18 21:19:06 by stryker
Originally posted by stryker
I'll be in Lake Tahoe tomorrow, then to Vegas then to Grand Canyon then to Utah... So long suckerz... :grin:


When your from Mars you obviously want to get in the sites while you have the chance...

Lucky bastard :)

Sliver
Posted on 2002-04-19 01:19:19 by Sliver