A tree needs no pointers if every node has a fixed place in an array. Watch how each cell finds its children.
A tree stored without pointers
Seven keys placed in an array, level by level
#include <stdio.h> #define EMPTY -1#define CELLS 7 static const int tree[CELLS] = { 50, 30, 70, 20, 40, 60, 80 }; int main(void){ for (int i = 0; i < CELLS; i++) { if (tree[i] == EMPTY) continue; int l = 2 * i + 1; int r = 2 * i + 2; printf("%d:", tree[i]); if (l < CELLS && tree[l] != EMPTY) printf(" left %d", tree[l]); if (r < CELLS && tree[r] != EMPTY) printf(" right %d", tree[r]); if (i > 0) printf(" parent %d", tree[(i - 1) / 2]); printf("\n"); } return 0;}main has started. The tree is 7 cells, outside main.
- cell i
- –
- children at
- –
- parent at
- –
Output
Describe this picture
A picture across the frame, with the code under it; on a phone the tree sits above the array. On the left, the tree is drawn as circles holding the keys, each with a small number beside it, the index of its cell; an empty position is a faint dashed circle. On the right is the array tree[7], seven cells in a row with their indices above them. For each cell the program reads, the node and its cell are ringed, the cells of its children are tinted in the accent colour and the cell of its parent in the second colour, and a marker i points to the cell in the array. The code pane shows the whole program, with the line about to run marked. The clip reads the complete tree, about 12 seconds, one beat per cell: 50 in cell 0 with its children in cells 1 and 2, then 30 in cell 1 with children in cells 3 and 4 and its parent in cell 0, and so on. At cell 4, which holds 40, the beat is longer: its children would be in cells 9 and 10, past the end, and its parent is cell 1. Under the picture are one sentence on the current cell, the readouts “cell i”, “children at” and “parent at”, the control and the output, which gains one line per cell, from 50: left 30 right 70 to 80: parent 70. The control, “Shape”, has the positions “complete” and “lopsided”; lopsided plays tree-array-lopsided.c, eight cells in which cells 4, 5 and 6 hold −1, shown greyed in the array and as dashed circles in the tree, and 10 sits in cell 7 under 20. The transport plays and pauses, steps one beat back or forward, and scrubs; a paused step is kept in the page address as array.step, and the shape as array.shape.
Level by level, left to right
Number the positions of a binary tree level by level, left to right: the root is 0, its children 1 and 2, theirs 3, 4, 5 and 6, and so on. Store each node’s key in the array cell with its number. The seven keys of the house tree, 50 30 70 20 40 60 80, fill cells 0 to 6 exactly, in that order:
#define EMPTY -1
#define CELLS 7
static const int tree[CELLS] = { 50, 30, 70, 20, 40, 60, 80 };No node holds a pointer, yet every link is there, because the numbering makes them arithmetic. The children of cell i are in cells 2i + 1 and 2i + 2, and its parent is in cell (i − 1) / 2, with C’s integer division. 30 is in cell 1: its children are in cells 3 and 4 (20 and 40) and its parent in cell 0 (50).
The program reads each cell and prints what the formulas find:
for (int i = 0; i < CELLS; i++) {
if (tree[i] == EMPTY)
continue;
int l = 2 * i + 1;
int r = 2 * i + 2;
printf("%d:", tree[i]);
if (l < CELLS && tree[l] != EMPTY)
printf(" left %d", tree[l]);
if (r < CELLS && tree[r] != EMPTY)
printf(" right %d", tree[r]);
if (i > 0)
printf(" parent %d", tree[(i - 1) / 2]);
printf("\n");
}Follow the clip to cell 4, which holds 40. Its children would be in cells 9 and 10, but the array ends at cell 6, so 40 is a leaf. Its parent is in cell (4 − 1) / 2 = 1, which holds 30. The program prints 40: parent 30.
Now set “Shape” to lopsided. This tree is 50, with 30 and 70 under it, 20 under 30, and 10 under 20. Placed by the same numbering, 10 belongs in cell 2 × 3 + 1 = 7, because 20 is in cell 3. Cell 4 is where 30’s right child would go, and cells 5 and 6 where 70’s children would go. None of them exist, so those cells hold EMPTY (−1, a value no key uses). Three of the eight cells are empty.
Key idea
The formulas need no pointers. A complete tree fills cells 0 to n − 1 exactly; any other shape pays for its gaps in empty cells.
The code and its cost
The three formulas
For a node in cell i:
- left child: cell 2i + 1
- right child: cell 2i + 2
- parent: cell (i − 1) / 2, rounded down, for i > 0
A child cell past the end of the array, or holding EMPTY, means there is no child there. Why these numbers: level k holds the cells 2ᵏ − 1 to 2ᵏ⁺¹ − 2, and the j-th node of a level, counting from 0, has its children at the 2j-th and (2j + 1)-th places of the next. The formulas say exactly that.
When the array is the right choice
A complete binary tree, one with every level full except perhaps the last, which is filled from the left, packs into cells 0 to n − 1 with no gaps. Finding a child or the parent is one multiplication or one division, and there is no pointer to follow, allocate or free. This is how heaps are stored (Binary heaps).
When it wastes space
Every missing node in the middle of the tree leaves an empty cell, and so do all the positions below it that the array has to keep. The worst case is a chain. A chain of h + 1 nodes going right from the root sits in cells 0, 2, 6, 14, …: the last is cell 2^(h+1) − 2, so the array needs 2^(h+1) − 1 cells for h + 1 keys. Four keys need 15 cells; twenty keys would need over a million.
Trees with any number of children
A folder can hold any number of folders, so a node can’t have a fixed set of child pointers. One answer gives each node an array of child pointers. Another needs only two pointers per node, whatever the number of children:
struct gnode {
int id;
struct gnode *first_child, *next_sibling;
};first_child points down to the node’s first child, and next_sibling points across to the next child of the same parent. A node’s children form a linked list, the one you met in Linked lists. Listing them is a walk along that list:
for (const struct gnode *c = t->first_child; c != NULL; c = c->next_sibling)
printf("%c ", c->id);Draw the down arrows as left and the across arrows as right, and the general tree has become a binary tree: every node has two pointers, and the binary tree lessons apply to it.
Running it yourself
gcc -std=c11 -Wall -Wextra -pedantic tree-array.c -o tree-array
./tree-arrayIt prints one line per node, from 50: left 30 right 70 to 80: parent 70. tree-array-lopsided.c is the same program with CELLS 8 and the cells { 50, 30, 70, 20, EMPTY, EMPTY, EMPTY, 10 }; it prints five lines, from 50: left 30 right 70 to 10: parent 20.
Worked example
Memory. The seven keys as linked nodes (Binary trees) take 7 × 24 = 168 bytes of nodes, and malloc keeps a little more for each block. As an array they take 7 × 4 = 28 bytes. For a complete tree the array is six times smaller here, and has no pointers to get wrong.
A chain. A right-going chain of 4 nodes sits in cells 0, 2, 6 and 14: 15 cells for 4 keys, 11 of them empty.
A folder tree. A root folder holds the folders A, B and C, and A holds A1 and A2. With first-child, next-sibling nodes: the root’s first_child is A; A’s next_sibling is B, and B’s is C; A’s first_child is A1, and A1’s next_sibling is A2. The program general.c builds exactly this, with each node’s id a character ('R' for the root, '1' and '2' for A1 and A2), and runs the loop above on the root and then on A:
A B C
1 2
24 bytes per nodeEvery node is 24 bytes, whatever its number of children: an int, 4 bytes of padding, and two pointers.
Two checks. Where are the children of cell 3? (Cells 7 and 8.) Where is the parent of cell 12? (Cell 5: (12 − 1) / 2 = 5, rounded down.)
Where it’s used
Heaps. A heap is a complete binary tree kept in an array exactly like this, so a priority queue needs no pointers at all (Binary heaps).
Segment trees. Trees that store a sum or minimum for each range of an array use the same numbering.
Files and documents. Folders on a disk and the elements of a web page are general trees, with any number of children per node.
Reference card
| Code or idea | Meaning |
|---|---|
| cell i | the node numbered i, level by level, left to right |
2 * i + 1, 2 * i + 2 | the left and right child’s cells |
(i - 1) / 2 | the parent’s cell, for i > 0 |
| complete tree | fills cells 0 to n − 1 exactly |
EMPTY | a cell with no node: the cost of a lopsided shape |
| chain of h + 1 nodes | needs 2^(h+1) − 1 cells |
first_child, next_sibling | any number of children with two pointers per node |
Platform: C11, gcc on x86-64 Linux: int 4 bytes, pointers 8, little-endian. Addresses in the pictures are short stand-ins, by one rule for the whole course; sizes are the real ones.