Solved

help with binarytree conversion

Posted on 2006-10-24
11
183 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
  • 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
Netscaler Common Configuration How To guides

If you use NetScaler you will want to see these guides. The NetScaler How To Guides show administrators how to get NetScaler up and configured by providing instructions for common scenarios and some not so common ones.

 

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

Master Your Team's Linux and Cloud Stack!

The average business loses $13.5M per year to ineffective training (per 1,000 employees). Keep ahead of the competition and combine in-person quality with online cost and flexibility by training with Linux Academy.

Question has a verified solution.

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

Suggested Solutions

Title # Comments Views Activity
groupSum5 challenge 5 84
JUnit 4 @Before and @BeforeClass differences 3 59
javap bin 2 34
login form jsp example 2 25
For customizing the look of your lightweight component and making it look lucid like it was made of glass. Or: how to make your component more Apple-ish ;) This tip assumes your component to be of rectangular shape and completely opaque. (COD…
Introduction This article is the second of three articles that explain why and how the Experts Exchange QA Team does test automation for our web site. This article covers the basic installation and configuration of the test automation tools used by…
Viewers learn about the scanner class in this video and are introduced to receiving user input for their programs. Additionally, objects, conditional statements, and loops are used to help reinforce the concepts. Introduce Scanner class: Importing…
Viewers will learn about basic arrays, how to declare them, and how to use them. Introduction and definition: Declare an array and cover the syntax of declaring them: Initialize every index in the created array: Example/Features of a basic arr…

778 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