Multi branch tree in c

Question

I want to create a multi branch tree in c, can you guys please help me out.

Tree structure:

                  O
                 /|\
                / | \
               O  O  O
              /|\     \
             / | \     \
            O  O  O     O

Try first with simple [BST](http://en.wikipedia.org/wiki/Binary_search_tree) tree and then extend it to fulfil your task — janisz, Jun 25 '14 at 07:36
Will the number of branches for a node be the same everytime? or will the no. of branches vary? — Mahesh Bansod, Jun 25 '14 at 07:55
You may want to check: http://stackoverflow.com/questions/189855/n-ary-trees-in-c and — Jakub, Jun 25 '14 at 08:13

score 1 · Answer 1 · answered Jun 25 '14 at 07:59

1

Most common approach is First-Child/Next-Sibling tree. It uses only 2 pointers to keep any number of children, not unlike linked list.

typedef struct node {
    struct node *child;
    struct node *next;
} node;

answered Jun 25 '14 at 07:59

Agent_L

4,960
28
30

score 0 · Answer 2 · answered Jun 25 '14 at 07:39

Here is a basic tree structure:

typedef struct node {
    struct node *left;
    struct node *right;
    char *string;
} node;

You can easily extend it for more branches by holding an array of pointers to node instead of just left and right but it won't be that efficient.

score 0 · Answer 3 · answered Jun 25 '14 at 07:55

If the number of child nodes is fixed, or has a maximum number, you can use a pointers array:

typedef struct node {
    struct nodes *childs[];
    char *string;
} node;

Or you can dynamically allocate it:

typedef struct node {
    struct nodes **childs;
    char *string;
} node;

This allows direct access to the childs.
Another option is to use linked list to hold the childs. This way you can add/remove as many as you'd like, but you lose the direct access.

Multi branch tree in c

3 Answers3