Respresenting a tree as a two dimensional array..

[EngSara]

Hi,

I need to store each path in a tree as a row in a two dimensional array of size #of paths x N. I couldn't find the appropriate indexing scheme for the array. Any ideas would be appreciated. Thanks,

[EngSara]

Sorry for the typing mistake in the title :)
Correct title: "Representing a tree as a two dimensional array"

[vijayan121]

I need to store each path in a tree as a row in a two dimensional array of size #of paths x N. I couldn't find the appropriate indexing scheme for the array.

Could you clarify your question? Is it a binary tree or an n-ary tree? What do you mean by 'each path in a tree'? Or is it a directed acyclic graph?

[EngSara]

it is not a binary tree.. each parent could has the same number of children but not necessarily 2 children. Each path means the set of nodes from the root to a leaf.. so each row in the array should contain the set of nodes from the root to one leaf

[vijayan121]

Let us say that we have a full 3-ary tree as follows:

[B]root[/B] 0
                                           |
                  -------------------------------------------------
                  |                        |                      |
                [B]alpha[/B] 1                   [B]beta[/B] 2                 [B]gamma[/B] 3
                  |                        |                      |
        --------------------     --------------------     --------------------
        |         |        |     |         |        |     |         |         |
      [B]delta[/B] 4  [B]epsilon[/B] 5  [B]zeta[/B]   [B]eta[/B]      [B]theta[/B]    [B]iota[/B]  [B]kappa[/B]    [B]lambda[/B]      [B]mu[/B]
        |
--------------------
|        |         |
[B]nu[/B]       [B]xi[/B]      [B]omicron[/B]

A two dimensional array representation of this tree (in the manner required) could be:

row 0: root, alpha, delta, nu
row 1: root, alpha, delta, xi
row 2: root, alpha, delta, omicron
row 3: root, alpha, epsilon, null
row 4: root, alpha, zeta, null
row 5: root, beta, eta, null
row 6: root, beta, theta, null
row 7: root, beta, iota, null
row 8: root, gamma, kappa, null
row 9: root, gamma, lambda, null
row 10: root, gamma, mu, null

If the full tree is a complete tree (every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible), a one dimensional array representation is possible. For the complete 3-ary tree above:

root, alpha, beta, gamma, delta, epsilon, zeta, eta, theta, iota, kappa, lambda, mu, nu, xi, omicron
  0     1     2      3      4       5       6    7     8      9     10     11    12  13  14    15

The position of the children of node at position p would be p*3+1, p*3+2, p*3+3
The position of the parent of node at position c would be (c-1)/3

In general, for a complete n-ary tree,
The position of the children of node at position p would be p*n+1, p*n+2, .. p*n+n
The position of the parent of node at position c would be (c-1)/n

[EngSara]

Yes it is a complete n-ary tree. How I can traverse all the paths?. Thanks,

[vijayan121]

Compute the depth D of the n-ary tree.
The two dimensional matrix representation will have D columns.

Perform a traversal (say a postorder traversal) of the n-ary tree. During the traversal,

a. Push each node encountered onto a stack. (the first node pushed would be the root).

b. If the node is a leaf node:
        Add the entire contents of the stack as a row of the 2D array. 
        If the size of the stack is less than [b]D[/b], add a [b]null[/b] at the end. 
        (with a complete n-ary tree, more than one [b]null[/b] will never be required.)

    Else:
        Move down to the next level, processing each of the [b]n[/b] children one by one.

c. Pop the node just visited off the stack, move up one level and continue with the traversal.