Converting Binary Tree into a sorted array

Question

Following my previous question, I would like now to put the Binary Tree values in a sorted array.

So, first I used my numOfNodeswn function that counts total sum of nodes in my tree,

I created an array according to the result of this function and I started to think that Instead of locating the minimum value of the tree and making not-that-easy successor function, I can simply take advantge of the utility of this kind of tree and make a kind of Inorder process, which during it I can put the correct values into my array.

My main problem is to control of variable i- which is the index according to it, I will know exactly where to put the correct values.

(header is the the head of the tree)

This is what I wrote so far:

public double[] toDoubleArray() {
    double[] arr = new double[numOfNodeswn(header)];
    int i=0;
    return putvalues(arr, i, header);
    }



private double[] putvalues(double[] arr, int i, RBNode t) {

    if (t!=null){
        putvalues (arr, i, t.left);
        arr[i]=t.value;
        i++;
        putvalues (arr, i, t.right);    
}
    return arr;

}

duffymo · Accepted Answer · 2011-04-23 13:50:49Z

2

I think you need to do a depth first iteration over the binary tree. Load each entry into th tree and increment the index as you go. The result should be a sorted array.

answered Apr 23, 2011 at 13:50

duffymo

310k46 gold badges376 silver badges570 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Unknown user Over a year ago

Thank you for the comment. What do you mean by doing a depth first iteration and loading the tree? By given a binary tree I need to do this. Are you suggesting that I should create the array during the creating of the tree? and if so, How will I control the array size? I don't have a pre information about the size of the tree.

duffymo Over a year ago

No, I'm saying that if you have a binary tree, and you do a depth first traversal of the tree, then you'll get the elements in ascending order. Print them out and see if that's true. If yes, then you can see how you can substitute loading into an array for the printing operation to get the result you want. You can easily get information about how many nodes are in the tree. If you don't maintain it as a member variable in your binary tree class, then do the depth first iteration and sum up the count as you go.

Unknown user Over a year ago

This is exactly what I am trying to do, My recursive function putvalues is going to the most-left node, but instead of printing it, I want to put it into array. If you'll change this two line arr[i]=t.value; i++; in a print command, You will get the tree printed in a sorted way as I wished and I know I can simply get information about the amount of nodes, I did it. My problem is exactly how to control the entry to the array.

just_doug · Accepted Answer · 2011-04-23 13:57:56Z

1

You're correct to do an in-order traversal of the tree. Perhaps instead of returning arr you should return an integer, corresponding to the first open spot in the array. This seems like a homework assignment, so I don't want to give too much away.

answered Apr 23, 2011 at 13:57

just_doug

1431 silver badge7 bronze badges

2 Comments

Unknown user Over a year ago

Is there any short way know what is the next avilable spot in given array, I can do it for a loop every iteration but I believe there's more simpler way, No?

just_doug Over a year ago

In the base case, you have a leaf node (which extends the array by one). So, if you pass in next_spot as an argument, it just returns next_spot + 1. Play with this on paper for a minute and the recursive case should be pretty clear.

Collectives™ on Stack Overflow

Converting Binary Tree into a sorted array

2 Answers 2

3 Comments

2 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

3 Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related