BST with arrays

[Obsidian_496]

Hello.

I've been trying to understand an online material about Binary search trees posted there
http://www.vias.org/cppcourse/chap21_10.html

I wonder if the code given for class is wrong, or does it use ideas I'm not familiar with? I'm not able to get it to work in my Borland compiler either. It seems to me like there is a } missing, and I also wonder why is class declared as public? I've never had to declare classs as public so far in home assignments, and I can't find much about it on the net.

I'm only having trouble understanding this class.

public class Tree { 
    Object[] array; 

    public Tree () { 
        array = new Object [128]; 
    }

Thanks.

[Narue]

The code isn't C++, it's Java.

[edit]
I'd recommend this site for your binary search tree needs. It's largely in C, but the conversion is much easier than from Java.
[/edit]

[Obsidian_496]

I see. I've created binary search trees before. Now I have to create one by using arrays, and that e-book looked promising..

Another question. I have read about 2 ways of implementing BST with an array. In one, the struct only has 2 elements:

struct item
{
    int index; 
    int data;
};

Information about left and right child is not stored. Following logic is used if I want to determine relationship between elements. r is the index of element, and n is the total number of elements, if I undertstand right.

Parent(r) = (r-1)/2 if r <> 0 and r < n.
Leftchild(r) = 2r + 1 if 2r + 1 < n.
Rightchild(r) = 2r + 2 if 2r + 2 < n.
Leftsibling(r) = r - 1 if r is even, r > 0, and r < n.
Rightsibling(r) = r + 1 if r is odd and r + 1 < n.
(taken from presentation)

Second way stores 2 additional bits of info in the array - left and right children.

Which one of these would be better? I bet on first one, which is what I'm going to create tomorrow :)
It simply must be easier thatn it seems.

And thanks for the link.

[Narue]

>Which one of these would be better?
Neither is better. Your first idea less flexible but offers a complete tree. Your second idea matches the linked version, but also has the disadvantages of an unbalanced tree. The former is what I'd expect for an array-based heap, and the latter strikes me more as a general binary tree structure implemented using an array.