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.

2
Contributors
3
Replies
4
Views
7 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.
[/edit]

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.