So the idea is that we're defining a tree as a series of parallel arrays, in depth-first traveral order. One of these arrays, actually the only necessary array contains the depth [0, +inf) of the element at that index. The index identifies a node in the tree.
int tree_size;
int *tree_depths; // int[tree_size]To associate data with these nodes, we define a parallel array of the same size. In our example case just names:
typedef char const* cstring;
cstring *tree_names; // cstring[tree_size]Let's define an example tree:
void
build_example_tree(void) {
static char const* s_tree_names[] = {
"root",
"Fruits",
"apple",
"orange",
"Vegetables",
"artichoke",
"Cruciferous",
"broccoli",
"cauliflower",
"cabbage",
"kale",
"spinach",
};
static int s_tree_depths[] = {
0 /* root */,
1,
2,
2,
1,
2,
2,
3,
3,
3,
3,
2,
};
tree_size = sizeof s_tree_depths / sizeof s_tree_depths[0];
assert(tree_size * sizeof s_tree_names[0] == sizeof s_tree_names);
tree_depths = s_tree_depths;
tree_names = s_tree_names;
}Printing the tree is rather straightforward, since the depth can be used as the indentation for the element:
void
print_tree_to_stdout(void) {
int i, n;
printf("Here is the tree:\n");
for (i = 0, n=tree_size; i < n; i++) {
printf("%*.s%s\n", tree_depths[i]*4, "", tree_names[i]);
}
}Calculating the depth of the tree involves finding the max value for the depth:
int
tree_depth(void) {
int max_depth = 0;
int i, n;
for(i = 0, n = tree_size; i < n; i++) {
max_depth = max_depth < tree_depths[i]
? tree_depths[i]
: max_depth;
}
return max_depth;
}Now imagine we wanted to tally up the number of children at each branch of the tree.
void
print_nodes_with_counts(int *counts) {
int i, n;
for (i = 0, n=tree_size; i < n; i++) {
printf("%*.s", tree_depths[i]*4, "");
printf("%s", tree_names[i]);
if (counts[i] > 0)
printf(" (%d children)", counts[i]);
printf("\n");
}
}A naive implementation with an inner loop would look like so:
void
count_up_children_naive(void) {
int i, n;
int *counts = calloc(tree_size, sizeof *counts);
int max_depth = tree_depth();
// keep track of our parent path during the iteration:
int *parent_at_depth = calloc(max_depth, sizeof *parent_at_depth);
int num_ops = 0;
for (i = 0, n = tree_size; i < n; i++) {
int const this_depth = tree_depths[i];
parent_at_depth[this_depth] = i;
counts[i] = 0;
// sum up the count upwards up to the root:
int next_depth = i + 1 >= n ? 0 : tree_depths[i + 1];
for (int rd = this_depth; rd > 0; rd--) {
int pi = parent_at_depth[rd - 1];
counts[pi]++; num_ops++;
}
}
printf("Here is the tree with child count per node (Naive version, %d ops):\n", num_ops);
print_nodes_with_counts(counts);
free(counts);
free(parent_at_depth);
}If we wanted to be less naive and reduce the number of operations in case we have deep trees, we would attempt to tally up in a similar way as recursive calls would:
void
count_up_children(void) {
int i, n;
int *counts = calloc(tree_size, sizeof *counts);
int max_depth = tree_depth();
// keep track of our parent path during the iteration:
int *parent_at_depth = calloc(max_depth, sizeof *parent_at_depth);
int *counts_at_depth = calloc(max_depth, sizeof *counts_at_depth);
int num_ops = 0;
for (i = 0, n = tree_size; i < n; i++) {
int const this_depth = tree_depths[i];
parent_at_depth[this_depth] = i;
counts_at_depth[this_depth]++; num_ops++;
counts[i] = 0;
if (i + 1 < n && this_depth < tree_depths[i + 1]) {
// initialize children count
counts_at_depth[this_depth + 1] = 0;
}
// sum up the count upwards, setting the count per parent:
int next_depth = i + 1 >= n ? 0 : tree_depths[i + 1];
for (int rd = this_depth; rd > next_depth; rd--) {
int pi = parent_at_depth[rd - 1];
counts[pi] = counts_at_depth[rd];
counts_at_depth[rd - 1] += counts[pi]; num_ops++;
}
}
printf("Here is the tree with child count per node (Reduced alu ops: %d for deep trees):\n", num_ops);
print_nodes_with_counts(counts);
free(counts);
free(parent_at_depth);
free(counts_at_depth);
}A possibility is also to precompute an array of successor depths to assist with climbing up and down the tree:
void
count_up_children_ndepth(void) {
int i, n;
// fill up next_depths
int *next_depths = calloc(tree_size, sizeof *next_depths);
for (i = 0, n = tree_size; i < n; i++) {
next_depths[i] = (n - i) > 1 ? tree_depths[i + 1] : 0;
}
// count up, but using a precomputed next_depths:
int *counts = calloc(tree_size, sizeof *counts);
int max_depth = tree_depth();
// keep track of our parent path during the iteration:
int *parent_at_depth = calloc(max_depth, sizeof *parent_at_depth);
int *counts_at_depth = calloc(max_depth, sizeof *counts_at_depth);
int num_ops = 0;
for (i = 0, n = tree_size; i < n; i++) {
int const this_depth = tree_depths[i];
parent_at_depth[this_depth] = i;
counts_at_depth[this_depth]++; num_ops++;
counts[i] = 0;
if (this_depth < next_depths[i]) {
// initialize children count before visiting them
counts_at_depth[this_depth + 1] = 0;
}
// sum up the count upwards after visiting all children,
// setting the count per parent:
for (int rd = this_depth, rd_last = next_depths[i]; rd > rd_last; rd--) {
int pi = parent_at_depth[rd - 1];
int count = counts_at_depth[rd];
counts[pi] = count;
counts_at_depth[rd-1] += count; num_ops++;
}
}
printf("Here is the tree with child count per node (Reduced alu ops: %d for deep trees):\n", num_ops);
print_nodes_with_counts(counts);
free(parent_at_depth);
free(counts_at_depth);
free(counts);
free(next_depths);
}Bundling this into our example program:
int
main(void) {
build_example_tree();
print_tree_to_stdout();
printf("Tree depth is %d\n", tree_depth());
count_up_children_naive();
count_up_children();
count_up_children_ndepth();}Here is the tree:
root
Fruits
apple
orange
Vegetables
artichoke
Cruciferous
broccoli
cauliflower
cabbage
kale
spinach
Tree depth is 3
Here is the tree with child count per node (Naive version, 24 ops):
root (11 children)
Fruits (2 children)
apple
orange
Vegetables (7 children)
artichoke
Cruciferous (4 children)
broccoli
cauliflower
cabbage
kale
spinach
Here is the tree with child count per node (Reduced alu ops: 16 for deep trees):
root (11 children)
Fruits (2 children)
apple
orange
Vegetables (7 children)
artichoke
Cruciferous (4 children)
broccoli
cauliflower
cabbage
kale
spinach