I know that in an array [0,1,2,3,4,5,6,7,8,9,10]
the parent 0, has children 2 * i +1, and 2 * i + 2. How do I go about writing a recursive function to make it a dynamic binary tree with a parent node containing the the info at array[0] and its children node.left and node.right = 1 and 2 respectively?
I'm trying to come up with a recursive function to take an array and using the fact that a nodes children are 2*i +1 and 2*i +2 it would fill the binary tree with the info in the array.
like
................................a[0] (root)
................................./....\
...........................a[1]....a[2]
............................/....\......../...\
....................a[3]..a[4]..a[5]..a[6]
root.data = a[0];
root.leftChild.data = a[1];
root.rightChild.data =a[2];
> I have the node class and the array filled with the
> info, I am just having a hard time writing a
> recursive function to convert the array to a dynamic
> binary tree
What is the requirement to be recursive?
Why not simply walk through the array, calling BinaryTree.insert(array) [or whatever the name is]?
> What is the requirement to be recursive?
> Why not simply walk through the array, calling
> BinaryTree.insert(array[ i ]) [or whatever the name is]?
[ fixed the Italics trap ;-) ]
I you want to do a BFS you have to manage a queue; otherwise you
have to keep on searching the (partially built) tree for the right node.
kind regards,
Jos
> > What is the requirement to be recursive?
> > Why not simply walk through the array, calling
> > BinaryTree.insert(array[ i ]) [or whatever the name
> is]?
>
> [ fixed the Italics trap ;-) ]
>
> I you want to do a BFS you have to manage a queue;
> otherwise you
> have to keep on searching the (partially built) tree
> for the right node.
I'm not sure I am following you, Jos. Could you please explain?
On a different note, I went in to a local beer store this past Saturday ...
I have never seen some many kinds of different beer from the US and around the world! Even Grolsch with the ceramic top!
I know where I'll be spending my pocket change from now on!!
> > I you want to do a BFS you have to manage a queue; otherwise you
> > have to keep on searching the (partially built) tree for the right node.
>
> I'm not sure I am following you, Jos. Could you please explain?
Walking the array in the order 0, 1, 2 ... n-1 is identical to walking the
tree in breadth first order. You have to keep track then of *which* node
to use for a next child. A queue can do that but recursion (depth first)
is easier here.
[ here comes the much more important stuff: ]
> On a different note, I went in to a local beer store this past Saturday ...
> I have never seen some many kinds of different beer from the US and
> around the world! Even Grolsch with the ceramic top!
> I know where I'll be spending my pocket change from now on!!
I didn't know Grolsch even exported their ceramic top bottles? I thought
they only send their inferior plastic top bottles to those bloody foreighners.
I'd say: go for the Grolsch and the Duvel (from Belgium) ;-)
kind regards,
Jos
> > > I you want to do a BFS you have to manage a
> queue; otherwise you
> > > have to keep on searching the (partially built)
> tree for the right node.
> >
> > I'm not sure I am following you, Jos. Could you
> please explain?
>
> Walking the array in the order 0, 1, 2 ... n-1 is
> identical to walking the
> tree in breadth first order.
Okay
You have to keep track
> then of *which* node
> to use for a next child. A queue can do that but
> recursion (depth first)
> is easier here.
I thought the assignment was simply to take the elements from an array and throw them into a Binary Tree? Perhaps I am being a bit stoopid here, but why keep track of the nodes, just add the data?
> [ here comes the much more important stuff: ]
> > On a different note, I went in to a local beer
> store this past Saturday ...
> > I have never seen some many kinds of different beer
> from the US and
> > around the world! Even Grolsch with the ceramic
> top!
> > I know where I'll be spending my pocket change from
> now on!!
>
> I didn't know Grolsch even exported their ceramic top
> bottles? I thought
> they only send their inferior plastic top bottles to
> those bloody foreighners.
> I'd say: go for the Grolsch and the Duvel (from
> Belgium) ;-)
I think you are right, the tops are plastic.
Duvel huh? I'll give it a try.
> I thought the assignment was simply to take the
> elements from an array and throw them into a Binary
> Tree? Perhaps I am being a bit stoopid here, but why
> keep track of the nodes, just add the data?
The array stores the complete binary tree as follows: array[0] is the
root of the tree and array[2*i+1] and array[2*i+2] are the children of
node array[ i ] (if present). The 'task' is to build a real, complete binary
tree with identical structure as the (conceptual) tree stored in the array.
The choices are:
1) BFS and a queue
2) recursion <-- the easiest solution!
3) Duvel < best!
kind regards,
Jos
ok, so this is my problem
i have a node class with String letters, Node leftChild, and Node rightChild
i have an array[ ] of ["a","b","c","d","e","f",.....]
lets say i go
for (int i=0; i<lengthofArray; i++)
{
if (i=0)
BinaryTree.root.letters=array[0];
else
{
BinaryTree.root.leftChild.letters=array[2*i+1];
BinaryTree.root.rightChild.letters=array[2*i+2];
}
root=root.leftChild;
}
how do i advance the root to branch off in the different directions for this to work?>
> > I thought the assignment was simply to take the
> > elements from an array and throw them into a
> Binary
> > Tree? Perhaps I am being a bit stoopid here, but
> why
> > keep track of the nodes, just add the data?
>
> The array stores the complete binary tree as follows:
> array[0] is the
> root of the tree and array[2*i+1] and array[2*i+2]
> are the children of
> node array[ i ] (if present). The 'task' is to build
> a real, complete binary
> tree with identical structure as the (conceptual)
> tree stored in the array.
Aah, reading back through the posts, I now see this. Dumb me! ;-(
> The choices are:
>
> 1) BFS and a queue
> 2) recursion <-- the easiest solution!
> 3) Duvel < best!
So you are saying that Belgian beers are superior to Dutch beers?
If the current node contains Grolsch, is Duvel inserted into the right subtree or the left subtree? :-)
> how do i advance the root to branch off in the
> different directions for this to work?
You don't, you let the recursive calls do it; here's the spoiler:public Node build(int[] array, int i) {
if (i >= array.length) return null; // nothing to build
Node node= new Node(array[i]); // new node for array[i]
node.left= build(array, 2*i+1); // build left sub-tree
node.right= build(array, 2*i+2); // build right sub-tree
return node;
}
kind regards,
Jos
> So you are saying that Belgian beers are superior to Dutch beers?
Yes; just their beers of course, nothing else. Maybe their chocolate, but
those are the only two things that are superior to the Dutch version:
beer, chocolate and coffee. Well maybe coffee too; there are just three
Belgian things superior to the Dutch version: beer, chocolate, coffee
and food. OMG I can't say it.
> If the current node contains Grolsch, is Duvel inserted into the right
> subtree or the left subtree? :-)
Duvel inserts itself everywhere it wants to; beware.
kind regards,
Jos ;-)
My nodes are being filled with null I don't know why
public class BinaryTree
{
public static class Node
{
private String data;
private Node leftLink;
private Node rightLink;
public Node(String n)
{
data=n;
leftLink=null;
rightLink=null;
}
public Node(String n, Node left, Node right)
{
data =n;
leftLink =left;
rightLink =right;
}
}
private Node root;
public BinaryTree()
{
root=null;
}
public static Node build(String[] array, int i) {
if (i >= array.length) return null; // nothing to build
Node node= new Node(array[i]); // new node for array[i]
node.leftLink= build(array, 2*i+1); // build left sub-tree
node.rightLink= build(array, 2*i+2); // build right sub-tree
return node;
}
}
The test program:
public class Test
{
public static void main (String [] args)
{
String array [] = new String [10];
array[0] = "root";
array[1] = "roots left child";
array[2] = "roots right child";
BinaryTree tree = new BinaryTree();
for (int i=0;i<array.length;i++)
{
tree.build(array,i);
}
}
}
>
After this:String array [] = new String [10];
array[0] = "root";
array[1] = "roots left child";
array[2] = "roots right child";
the indexes 3 to 9 are null. So, either fill them with Strings, or don't create an array of size 10, but with a size 3.
No explanation; just something to chew on:public Node build(int[] array, int i) {
if (i >= array.length) return null;
Node node= new Node(array[i]);
node.left= build(array, 2*i+1);
node.right= build(array.2*i+2);
return node;
}
kind regards,
Jos
> So you are saying that Belgian beers are superior to Dutch beers?
> If the current node contains Grolsch, is Duvel inserted into the right
> subtree or the left subtree? :-)
In this case I'd suggest to kick out the Grolsch and you'll have an extra spot for Duvel!
> Yes; just their beers of course, nothing else. Maybe their chocolate,
> but those are the only two things that are superior to the Dutch
> version: beer, chocolate and coffee. Well maybe coffee too; there
> are just three Belgian things superior to the Dutch version: beer,
> chocolate, coffee and food. OMG I can't say it.
And Belgians can count better than the Dutch! How many things did you list there? And I was thinking of Jos as a man with a solid math background!
> No explanation; just something to chew on:[code]
> public Node build(int[] array, int i) {
>if (i >= array.length) return null;
> Node node= new Node(array);
>node.left= build(array, 2*i+1);
> node.right= build(array.2*i+2);
>return node;
> code]
> kind regards,
>
> Jos
all my nodes are null with this and i don't understand why
Put a setter in BinaryTree for root and test with this:
public class Test
{
public static void main (String [] args)
{
String array [] = new String [3];
array[0] = "root";
array[1] = "roots left child";
array[2] = "roots right child";
BinaryTree tree = new BinaryTree();
tree.setRoot(tree.build(array,0));
}
}
When build the tree you must start from the root. You make a tree but it is not attached to yours. Try this:
public class BinaryTree {
public class Node {
private String data;
private Node leftLink;
private Node rightLink;
public Node(String n) {
this( n, null, null );
}
public Node(String n, Node left, Node right) {
data = n;
leftLink = left;
rightLink = right;
}
public String getData() {
return this.data;
}
public Node getLeft() {
return this.leftLink;
}
public Node getRight() {
return this.rightLink;
}
}
private Node root;
public BinaryTree() {
// root=null;
}
private void print(Node n) {
if ( n != null ) {
System.out.println( n.getData() );
print( n.leftLink );
print( n.rightLink );
}
}
public void printTree() {
print( root );
}
public void makeTree(String[] array) {
this.root = this.build( array, 0 );
}
private Node build(String[] array, int i) {
if ( i >= array.length )
return null;
Node node = new Node( array[ i ], build( array, 2 * i + 1 ), build( array, 2 * i + 2 ) );
return node;
}
// to test it
public static void main(String[] args) {
String array[] = new String[ 3 ];
array[ 0 ] = "root";
array[ 1 ] = "roots left child";
array[ 2 ] = "roots right child";
BinaryTree tree = new BinaryTree();
tree.makeTree( array );
tree.printTree();
}
}
Think about calling recursive method within a for loop ;)
