Java Serialize N ary tree that contains many null nodes

Question

I have an N-ary tree where each node contains some data and its children:

Node {
  // data
  Node[] children = new Node[30];
}

As you can see, the size of the children array is fixed to 30 regardless of the current number of descendants. The array can contain something like this:

null, null, someNode, null, anotherNode, ...

A tree like this is always incomplete; therefore, I can't serialize it as an array where c child is placed in N * i + 1 + c (being i the index of the parent node).

I can serialize the tree by preorder traversal using / symbol to represent null child, but this approach requires n*30*sizeOfData bytes. Even if I represent the absence of children by, for example, #, it will take n*30*sizeOfData - numberOfLeafs*29, which is too many.

If you know a better approach to serialize a tree like this please write me ;)

Thanks in advance.

Answer 1

If part of existing children is small, you'd better to explicitly write index of child like this

2: somenode
4: othernode

During reading just fill unused entries with nulls

Answer 2

Considering you use Java as you have mentioned it as a tag, you can use Hashmap instead of Node[], and you'll end up with something like this:

    Node {
     // data
     HashMap<Integer, Node> children; //Integer is index of child and Node is actual child, TODO: init it and write some function to control add/swap/delete children
   }

Now why I suggest this you may ask, I'll answer it here:

1. You'll get rid of wasted space in your previous model.

2. You'll have indices just like an array and you can loop over this map and traverse it in whatever order you like using both indices and children.

I hope this helps you.

Answer 3

Need more repuation or I would have added this as a comment rather than answer.

The serialization interface also allows the addition of readObject / writeObject methods so it'd be somewhat easy to implement the suggest by MBo: