Algorithm to implement non-binary trees using 1-dimensional vector?

Question

Each node of the tree might have an arbitrary number of children. I need a way to construct and traverse such trees, but to implement them using one dimensional vector or a list.

Answer 1

If you only can use one vector (not specified in question), and Nodes should not contain it's own list, only some pointers (addresses in vector), then you can try this:

1. each node holds address of its sibling
2. first node after given (if it is not its sibling) is child, with pointer to second child and so on
3. each of its child has it's own children

So for tree like this:

A
| \
B  E ___
|\  \ \ \
C D  F G H

Your vector would look like:

idx:    0 1 2 3 4 5 6 7
nodes:  A B C D E F G H
next:   _ 4 3 _ _ 6 7 _

where _ is null pointer

Edit:
Another approach:

1. every node holds address of region in vector occupied by its children
2. children are next to each other
3. there exists null node in vector, marking end of siblings group

For that approach given tree would look like:

idx:    0 1 2 3 4 5 6 7 8 9 A B
nodex:  A _ B E _ C D _ F G H _
child:  2   5 8   _ _   _ _ _

That way you can easily find children of any randomly given node and reorganize array without moving all elements (just copy children to end of table, update pointer and add next child to end of table)

Answer 2

The standard way of storing a full binary tree in an array (as is used for binary heap implementations) is nice because you can represent the tree with an array of elements in the order of a level-order tree traversal. Using that scheme, there are quick tricks for computing the parent and child node positions. Moving to a tree in which each node can have an arbitrary number of elements throws a wrench into that kind of scheme.

There are, however, several schemes for representing arbitrary trees as binary trees. They are discussed in great detail in Donald Knuth's Art of Computer Programming, Volume I, Section 2.3.

If the nodes themselves are permitted to contain a pointer, you could store a list of child indicies for each node. Is that possible in your case?