Want to protect your cyber security and still get fast solutions? Ask a secure question today.Go Premium

x
  • Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 190
  • Last Modified:

help with binarytree conversion

Hi,
   I'm trying to convert linked representation of a binary tree to its array format, but I'm having problem calculating the last index for the array. How do I keep track of the index since "last" only gives number of elements ?  thanks

   public T[] converttoarray(Node<T> root, T[] a, int i)
   {
      if(root != null) {
         a[i] = root.element;
         last++;
         converttoarray(root.left, ar, 2*i + 1);

         converttoarray(root.right, ar, 2*i + 2);
      }

      return a;
   }
0
azcalv408
Asked:
azcalv408
  • 5
  • 3
  • 3
1 Solution
 
hoomanvCommented:
Array size should be atmost 2 ^ Tree-Depth
0
 
hoomanvCommented:
errata: atmost -> atleast
0
 
hoomanvCommented:
btw atmost is more correct
the size is between  2 ^ (Tree-Depth-1)  to  2 ^ Tree-Depth
0
Technology Partners: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

 
azcalv408Author Commented:
none of the replies are relevant to the question...
0
 
shinobunCommented:
Why don't you create a List<T> first, then convert it to T[] with the toArray() [1] method?  Then, you don't need to worry about the indexes until the whole tree is processed.

[1] http://java.sun.com/j2se/1.5.0/docs/api/java/util/List.html#toArray(T[])
0
 
azcalv408Author Commented:
but the point here is to write it using regular arrays (i could use ArrayList and make it easier as well), and keep track of the last index. thanks
0
 
shinobunCommented:
>> the point here is to write it using regular arrays

Some kind of homework?  The only reasonable solution I can think of is adding a getTotalChildCount() method on the Node class and using that.

>> and keep track of the last index

Why do you need the last index for?
0
 
azcalv408Author Commented:
and no it's not homework....I'm experimenting of converting array tree to linked tree, and the other way around. It's how I learn. I think the number of children method might work. thanks
0
 
hoomanvCommented:
> the number of children method might work
No the has tree contains 6 children, but the last index in array would be 14
You know why ? As I told you it is somthing between 2 ^ (Hight - 1)  and  2 ^ Hight
It depends on the rightmost deeper node

           o
         /   \
       o      o
         \       \
           o      o
                 /
               o

0
 
shinobunCommented:
>> It depends on the rightmost deeper node

Why would you want to keep all the redundant empty elements?  You only need 6 to convert it to an array.  Unless you want to preserve the tree structure in the array, this is.  :)

Given the root node, the last index would be root.left.getTotalChildCount() + 1 + root.right.getTotalChildCount().
0
 
hoomanvCommented:
> Why would you want to keep all the redundant empty elements?
>> I'm trying to convert linked representation of a binary tree to its array format
So you lose the tree structure
0

Featured Post

Industry Leaders: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

  • 5
  • 3
  • 3
Tackle projects and never again get stuck behind a technical roadblock.
Join Now