CODEWITHSUNDEEP
arraysalgorithmdata-structurestree
Muaz Kassm
Muaz Kassm

Reputation: 31

how to represent non-binary trees with 1D-arrays?

A way to use 1D-arrays to represent non-binary trees

we can use 1D-array for representing binary trees when we have a finite and small number of nodes whereas a node at index i has two sons at indices 2*i and 2*i+1. can I use 1D-arrays for storing non-binary trees, (when a node has more than 2 sons), in the same manner? I thought of using this way to store a tree with 3 sons at most where the index of the node is i and its sons are at 3*i, 3*i + 1 and 3*i + 2.. but doing so, i am left with a lot of empty (not used) array cells. is there a better way?

Upvotes: 2

Views: 1863

Answers (1)

RobertBaron
RobertBaron

Reputation: 2854

Here is one solution to pack all nodes in a one-dimensional array.

Each node consist of a variable-number of array cells. The first cell of the node is the count C of its child nodes. The next C cells contain the indexes of the first cell of its child nodes in the array.

For example:

Indexes: 0 1 2 3 4
Values:  2 3 4 0 0

is a graph with of 3 nodes; 1 node that has 2 child nodes. First node is at cell index 0 whose value is 2, the number of its child nodes. Next 2 values are the indexes of the child nodes, 3 and 4. Cells at indexes 3 and 4 have values 0 because they have no child node.

Upvotes: 1

Related Questions