We help IT Professionals succeed at work.

We've partnered with Certified Experts, Carl Webster and Richard Faulkner, to bring you two Citrix podcasts. Learn about 2020 trends and get answers to your biggest Citrix questions!Listen Now

x

help with binarytree conversion

azcalv408
azcalv408 asked
on
Medium Priority
199 Views
Last Modified: 2010-03-31
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;
   }
Comment
Watch Question

Top Expert 2006

Commented:
Array size should be atmost 2 ^ Tree-Depth
Top Expert 2006

Commented:
errata: atmost -> atleast
Top Expert 2006

Commented:
btw atmost is more correct
the size is between  2 ^ (Tree-Depth-1)  to  2 ^ Tree-Depth

Author

Commented:
none of the replies are relevant to the question...

Commented:
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[])

Author

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

Commented:
>> 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?

Author

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
Top Expert 2006

Commented:
> 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

Commented:
>> 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().

Not the solution you were looking for? Getting a personalized solution is easy.

Ask the Experts
Top Expert 2006

Commented:
> 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
Access more of Experts Exchange with a free account
Thanks for using Experts Exchange.

Create a free account to continue.

Limited access with a free account allows you to:

  • View three pieces of content (articles, solutions, posts, and videos)
  • Ask the experts questions (counted toward content limit)
  • Customize your dashboard and profile

*This site is protected by reCAPTCHA and the Google Privacy Policy and Terms of Service apply.

OR

Please enter a first name

Please enter a last name

8+ characters (letters, numbers, and a symbol)

By clicking, you agree to the Terms of Use and Privacy Policy.