copying a (BSP) tree into an array?

Newbie & Debugging Questions
#1

is there a efficient way to copy a Node & it’s children into a ‘orderly’ arranged array right now i have a left and right child and eventually i want an int that’s point into a global ‘nodes’ array for it’s left and right sibbling.

#2

From what sort of structure? i.e. What information does the array structure contain? Let’s assume something like this:


public class Node
{
    public Node left;
    public Node right;
    public Point point;
}

public class Point
{
    public int x;
    public int y;
}

The above requires 4 ints per node. So we can do something like this to serialize it:


public class NodeSerializer
{
    private int[] data;
    private int counter = 0;

    public NodeSerializer(int nodecount)
    {
        data = int[nodecount * 4];
    }

    private int getNextLocation()
    {
        int loc = counter;

        counter += 4;
        return loc;
    }

    public int[] serialize(Node node)
    {
        serialize(node, location);
        return data;
    }

    private void serialize(Node node, int location)
    {
         int left = (node.left != null) ? getNextLocation() : -1;
         int right = (node.right != null) ? getNextLocation() : -1;

         data[location] = left;
         data[location+1] = right;
         data[location+2] = node.point.x;
         data[location+3] = node.point.y;

         if(left >= 0) serialize(node.left, left);
         if(right >= 0) serialize(node. right, right);
    }
}

I just whipped that up, so I have no idea if it will work. However, I do have one question before I let you run off and implement this. Why are you trying to fit everything in an array? Is it just to write it to disk, or are you trying to “optimize”? If you’re thinking that using an int[] array will optimize your code you may want to rethink. I tried such an optimization when I was a C programmer and paid heavily for my attempts. If I’d just used a struct, my code would have been much simpler and easier to complete.

Good luck, StarFox! :slight_smile:

#3

[quote]is there a efficient way to copy a Node & it’s children into a ‘orderly’ arranged array right now i have a left and right child and eventually i want an int that’s point into a global ‘nodes’ array for it’s left and right sibbling.
[/quote]
You can use a 2 dimensional array maybe.

int[a][b]

All the parents in array (a) and the children in (b).