Binary Tree (Solved)

[Tec-Nico]

Hey... I am trying to create a Binary Tree Structure But I cannot use pointers... Any Ideas there? (Phinds already gave me an idea of this and I have already created a Binary Tree, so don't mind this)

I would really appreciate any help. I am doing it from the scratch so please be patient with me...

(As a matter of fact the Binary Tree is complete, I am just working on restructuring the Tree. I am writing a code to avoid the worst case with this... Can anyone tell me how to calculate the right and left height of a node using its level and the right or left height of the whole tree? With this Information I can be able to solve the whole problem)

Come on... Don't tell me you are not interested. I know every programmer would like to have a Binary Tree, they are very useful!

The code below has not yet the Balancing Rotations nor the DeleteNode. But since nobody has replied, I guess you don't want it. If you feel like it, please reply. (This was solved and the code is added later in this thread)

Thanks

[phinds]

check this out

[Tec-Nico]

I am going to test it now.. Thanks a lot!

[Tec-Nico]

Thank you phinds!

I just checked it and it is as I was programming it. But I have a doubt...

How would you perform an inorder, post-order and pre-order?

How did you solve the problem of pointers? I see you made an array of BTrees but I still don't get how it works. Could you explain it to me in a simple way?

Tell me, what if I wanted to resize it?

I have something like this... How can I adapt it?

'Forget it.. I already solved this.
 
'Useful Note: Use IsObject and IsEmpty to know if an Object is Null.
'Don't use IsNothing since it does not exist, though VB swears it
'does.

What am I doing wrong?

[Tec-Nico]

Alright... After having slept I found the solution to my own question.

Tell me... If Left or Right is 0 it means it is a leaf, right?

Taking that in consideration I created the following procedures:

'Don't Mind this, if it is -1 then it means it is a leaf.
If (you want to see code) Then Go Below

But still I am trying to make the BTree to resize and not to stay in only 15 elements...

I am working on it... Could you please provide me with more information regarding to your code?

Thanks in advance!

[Tec-Nico]

Why can't I resize the array?

'Don't Mind this.. I already solved it.
 
'Don't try to Redim an Array part of a Data Structure if you ignore
'How it works!
 
'There are 10 kinds of people on Earth. The ones who know binary...
'And the ones who don't.

By the way, is UnWind a procedure to Balance the BTree?

[phinds]

you have to use redim with preserve to change the size of the array

unwind just sucks all the elements out of the tree, but does so in order.

this is the classic binary tree algorithm. I found it in the original C book by K&R 25 years ago.

[Tec-Nico]

I know... If you see I tried Redim Preserve.

But it only works for the first 3 elements. This means it will do fine until Index = 3 then it messes up since it says the Array is Temporaly Locked. Why is this happening?

[phinds]

sorry, I was in a hurry and didn't look at your code to see that you had used redim

I've never tried anything like what you're doing, so have no idea why it doesn't work. When I redim, I redim an array, not an array that is part of a structure.

[techyspecy]

Try this module dudes, its pretty usefull i guess

[phinds]

comment on the .BAS module posted in the previous entry of this thread:

he's got a lot of good stuff in there, but you have to take what he says with a heavy grain of salt, since some of it is patently untrue, even according to his own comments.

example: he states (correctly) that a quick sort isn't quick at all on pre-sorted lists and can in fact be twice as slow as even a bubble sort under those conditions. Then later, he states that a quick sort is 50 times faster than a bubble sort on a pre-sorted list (which is definitely not even close to being correct).

[Tec-Nico]

I have not tried the module yet... As a matter of fact I just downloaded it.

Anyway, thanks to Phinds I was able to develop my own BTree class I will show here. I have been working now in the Balancing Code... Do you have any algorithm that might do the trick?

I don't want you to try to code it but just the algorithm would be nice. I haven't found it in my Data Structure Notebook. I wonder why I did not take notes then... I have some excercises but no algorithm.... Hmmmm...

Oh well, here is the BTree Type so you can check it out. Thanks to all!

'Nobody replied to this... So I guess you don't care for the code.
'That is why I took it off. If you want it, please feel free to ask.
 
If (You Want The Code) Then Ask

I add here the module. Guys, check the code posted above works since I had to translate the name of some functions... That would be the main problem since some functions were named in Spanish for when my professor would check the code.

In addition, if you don't feel comfortable with Spanish Names in the functions of this module, please feel free to change them. (The module is attached to the Next Reply)

[Tec-Nico]

Here is the module. If you are going to use it, please don't forget to acknow my work.

However, you could wait more until I post the final version with the DeleteNode procedure as well as Balance. Or you could also try to help out with the algorithm... It is up to you.

[Tec-Nico]

I noticed nobody took their time to check it... Is it that nobody likes BTrees?

Or maybe my code must suck for you... Oh well...
I'll keep working then.

[Tec-Nico]

So far I have been able to code the DeleteNode procedure and I am done programming the Rotations.

RR, LL, RL and LR are already done. I also implemented some code to locate the parts which are not balanced... But Do you know how can I get the right and left height of a node with its level and the tree's right or left height?

Any ideas?

Oh come on... Don't tell me nobody here knows about BTrees.

Thanks in advance, Me

[Tec-Nico]

Why don't I get replies?

[Edneeis]

I just think a lot of people either don't know what a BTree is or really don't think it sounds like something they need, don't take it personal or anything.

[Shaggy Hiker]

I agree with Edneeis. Most of my work in VB is just way too simple. I've never come across a situation where a binary tree would be useful. In C++, on the other hand...

Always innovate, ya' just never know when something will be just what is needed.

[Tec-Nico]

Here is the Binary Tree, if you want to check it and comment it I would feel happy to hear of you.

Thanks for your help...

[Shawn N]

What do you use this program for? Just curious.

[Tec-Nico]

It is a program that shows you the Binary Tree formed by giving an array of integer numbers. The tree will be balanced of course, you can see the properties of each node by clicking on it, you can delete nodes (giving the number of the node, not the integer you gave to form the tree) And you could also perform some searching. (The code is there but I did not add a search trigger)

This is mostly to help those people who are asked to develop a Binary Tree as they learn how to program... What do you think?

[BuggyProgrammer]

you really didn't have to dig up so many old posts and post in it saying that you have a program that worked

[Tec-Nico]

I am just doing what I would like someone to do to me. If they found a solution to a problem I had and they knew how hard it was they would find me to give me the answer of it.

I just wanted to help... Sorry if it appeared I wanted to show off or something. But I still remember when that professor asked me for this program (Semesters ago) And how I would liked someone to help me with it.

[Shawn N]

I still don't understand what the hell's the purpose of the program. Sorry.

[Tec-Nico]

1.- Create a node structure
2.- Create a Binary tree structure
3.- Be able to create a tree from an array
4.- Be able to graph this tree
5.- Be able to erase nodes from the tree
6.- Be able to search for data in the tree
7.- Be able to balance the tree
8.- Be able to provide an inorder, preorder and postorder code that will let you call another procedure in them

I guess that sumarizes it...

[phinds]

Tec-Nico's last answer looks too much at the details and not enough at the big picture. The point of a binary tree is that there are certain types of data manipulation algorithms that simple cannot be done in any way that is even close to the effeciency of a binary tree.

The classic example is the need to enumerate all the identical elements in a data collection and to present an ordered list of all the elements with the number of times each occurs. There are plenty of practical applications for this, and it is just one example of a situation where there are LOTS of ways to do the job but none of them will approach a binary tree in effeciency.

Because of this, and the fact that they are an elegant use of doubly-linked lists, binary trees are a staple of computer science classes.

[Tec-Nico]

Amen, Phinds. I thought he asked what the program could achieve and not what the Binary Trees were for...

I have to thank you, Phinds, you were helped me a lot so I could achieve this.

I hope you like the program I developed with your advice.