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?

Answer 3

With no restrictions on the values of the nodes, and assuming you can use only a single list, I would construct it as follows:

Represent each node as ( val ; [ int ; ...] ) where val is the node's value and each int is the position in the list of one of it's children. Use a non-printable separator if necessary.

Traversal is very slow.

Answer 4

You can implement it using one dimensional linked list with little overhead.

Every parent will contain pointers to its children.(But this requires deciding if the max number of nodes are know before hand).

For a tree having A as root node and B,C,D as children its representation will be as below.

A -> B A -> C A -> D

Note that there are 3 links from A.

One way to overcome the upperlimit on the number of nodes is having additional pointer in the nodes.

So, now A ->(child) B ->(adj) ->(adj) C ->(adj) -> D

In this case, its quite complex to update the tree, when deletion occurs.

Its even easier to design better data structures if you could tell your time bounds on the various operations.

Answer 5

What you basically do is write the beginnings of a memory manager for a Lisp interpreter by pairing off the vector's elements into cons cells. Here is such a thing I threw together in C just now:

#include <stdbool.h>
#include <iso646.h>
#include <stdlib.h>
#include <stdio.h>
#include <assert.h>

#define MEMORY_SIZE 1024
#define NIL 0
#define IVAL_MASK 0x8000000

struct pair
{
    bool allocated;
    size_t first;
    size_t second;
};

size_t allocate_pair(struct pair vector[])
{
    for (size_t i = 1; i < MEMORY_SIZE; i++)
        {
            if (not vector[i].allocated)
                {
                    vector[i].allocated = true;
                    return i;
                }
        }

    return NIL;
}

size_t make_pair(struct pair vector[], size_t a, size_t b)
{
    size_t the_pair = allocate_pair(vector);

    if (the_pair != NIL)
        {
            vector[the_pair].first = a;
            vector[the_pair].second = b;
            return the_pair;
        }
    else
        {
            fprintf(stderr,
                    "Out of pairs -- make_pair(%p, %zu, %zu)",
                    vector,
                    a,
                    b);
            exit(EXIT_FAILURE);
        }
}

size_t first(struct pair vector[], size_t index)
{
    assert(vector[index].allocated);

    return vector[index].first;
}


size_t second(struct pair vector[], size_t index)
{
    assert(vector[index].allocated);

    return vector[index].second;
}

void print_pair_aux(struct pair[], size_t, size_t);
void print_pair(struct pair vector[], size_t p)
{
    assert(vector[p].allocated);

    size_t a = first(vector, p);
    size_t b = second(vector, p);

    printf("(");

    print_pair_aux(vector, a, b);

    printf(")");
}

void print_pair_aux(struct pair vector[], size_t a, size_t b)
{
    if (a == NIL)
        printf("NIL");
    else if (a >= IVAL_MASK)
        printf("%zu", a &~ IVAL_MASK);
    else
        print_pair(vector, a);

    if (b == NIL)
        printf("");
    else if (b >= IVAL_MASK)
        printf(" . %zu", b &~ IVAL_MASK);
    else
        {
            printf(" ");
            print_pair_aux(vector,
                           first(vector, b),
                           second(vector, b));
        }

}

int main(void) 
{
    struct pair *vector = calloc(MEMORY_SIZE, sizeof *vector);

#define cons(A,B) make_pair(vector, (A), (B))
#define ival(x) ((x) | IVAL_MASK)

    size_t a = cons(ival(3), cons(ival(4), NIL));
    size_t b = cons(ival(2), cons(a, NIL));
    size_t c = cons(ival(6), cons(ival(7), cons(ival(8), NIL)));
    size_t d = cons(ival(5), cons(c, NIL));
    size_t e = cons(ival(1), cons(b, cons(d, NIL)));

    print_pair(vector, e);
    puts("");
}

$ cc -std=c99 try.c
$ ./a.out
(1 (2 (3 4)) (5 (6 7 8)))