I've been trying to understand an online material about Binary search trees posted there

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]; 


6 Years
Discussion Span
Last Post by Narue

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

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.

Edited by Narue: n/a


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.


>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.

Edited by Narue: n/a

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.