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,
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,
Sorry for the typing mistake in the title :)
Correct title: "Representing a tree as a two dimensional array"
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 nary tree? What do you mean by 'each path in a tree'? Or is it a directed acyclic graph?
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
Let us say that we have a full 3ary 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 3ary 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 (c1)/3
In general, for a complete nary 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 (c1)/n
Yes it is a complete nary tree. How I can traverse all the paths?. Thanks,
Compute the depth D of the nary tree.
The two dimensional matrix representation will have D columns.
Perform a traversal (say a postorder traversal) of the nary 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 nary 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.