Solved

help with binarytree conversion

Posted on 2006-10-24
11
187 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
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!

 

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 100 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

Creating Instructional Tutorials  

For Any Use & On Any Platform

Contextual Guidance at the moment of need helps your employees/users adopt software o& achieve even the most complex tasks instantly. Boost knowledge retention, software adoption & employee engagement with easy solution.

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 connect and configure Android Device (Smartphone etc.) with Android Studio. After that we will run a simple Hello World Program.
Viewers learn how to read error messages and identify possible mistakes that could cause hours of frustration. Coding is as much about debugging your code as it is about writing it. Define Error Message: Line Numbers: Type of Error: Break Down…
This theoretical tutorial explains exceptions, reasons for exceptions, different categories of exception and exception hierarchy.

695 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