?
Solved

help with binarytree conversion

Posted on 2006-10-24
11
Medium Priority
?
188 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;
   }
0
Comment
Question by:azcalv408
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 5
  • 3
  • 3
11 Comments
 
LVL 14

Expert Comment

by:hoomanv
ID: 17799935
Array size should be atmost 2 ^ Tree-Depth
0
 
LVL 14

Expert Comment

by:hoomanv
ID: 17799938
errata: atmost -> atleast
0
 
LVL 14

Expert Comment

by:hoomanv
ID: 17799943
btw atmost is more correct
the size is between  2 ^ (Tree-Depth-1)  to  2 ^ Tree-Depth
0
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!

 

Author Comment

by:azcalv408
ID: 17800773
none of the replies are relevant to the question...
0
 
LVL 9

Expert Comment

by:shinobun
ID: 17800801
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
 

Author Comment

by:azcalv408
ID: 17800855
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
 
LVL 9

Expert Comment

by:shinobun
ID: 17801144
>> 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
 

Author Comment

by:azcalv408
ID: 17801166
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
 
LVL 14

Expert Comment

by:hoomanv
ID: 17801190
> 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
 
LVL 9

Accepted Solution

by:
shinobun earned 400 total points
ID: 17806057
>> 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
 
LVL 14

Expert Comment

by:hoomanv
ID: 17809500
> 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

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!

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

In this post we will learn different types of Android Layout and some basics of an Android App.
In this post we will learn how to make Android Gesture Tutorial and give different functionality whenever a user Touch or Scroll android screen.
The viewer will learn how to implement Singleton Design Pattern in Java.
How to fix incompatible JVM issue while installing Eclipse While installing Eclipse in windows, got one error like above and unable to proceed with the installation. This video describes how to successfully install Eclipse. How to solve incompa…
Suggested Courses
Course of the Month11 days, 10 hours left to enroll

752 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question