Skip to content

Instantly share code, notes, and snippets.

@aptavout aptavout/tree.c
Created Sep 23, 2014

Embed
What would you like to do?
Array-based tree traversal
/* demonstrate tree data structure with multi-dimensional arrays */
/* construct a tree of this form: */
/* 1 */
/* 2 3 */
/* 4 5 6 */
/* as a table, */
/* node children */
/* 1 2 3 */
/* 2 4 5 */
/* 3 6 */
/* 4 */
/* 5 */
/* 6 (don't forget the orphans) */
#include <stdio.h>
/* this first define should be removed because i am making many assumptions */
/* with the tree being a binary tree already (see traverse_tree()). */
#define MAX_LEAVES 2 /* a tree with two leaves per node */
#define MAX_COLS 3 /* MAX_LEAVES + 1 */
#define MAX_ROWS 6
void in_order(int tree[][MAX_COLS], int row);
void post_order(int tree[][MAX_COLS], int row);
int find_index(int tree[][MAX_COLS], int node);
void pre_order(int tree[][MAX_COLS], int row);
void print_children(int tree[][MAX_COLS], int node);
main()
{
int tree[MAX_ROWS][MAX_COLS];
int i, j;
/* initialize the tree */
for (i = 0; i < MAX_ROWS; ++i)
for (j = 0; j < MAX_COLS; ++j)
tree[i][j] = -1;
tree[0][0] = 1;
tree[0][1] = 2;
tree[0][2] = 3;
tree[1][0] = 2;
tree[1][1] = 4;
tree[1][2] = 5;
tree[2][0] = 3;
tree[2][1] = 6;
tree[3][0] = 4;
tree[4][0] = 5;
tree[5][0] = 6;
for (i = 0; i < MAX_ROWS; ++i)
print_children(tree, i);
pre_order(tree, 0);
printf("---\n");
post_order(tree, 0);
printf("---\n");
in_order(tree, 0);
}
/* in_order: left, visit, right */
void in_order(int tree[][MAX_COLS], int row)
{
int row_index;
if (tree[row][1] != -1) {
row_index = find_index(tree, tree[row][1]);
if (row_index != -1) {
printf("value of row_index is %d\n", row_index);
printf("visiting node %d next.\n", tree[row_index][0]);
in_order(tree, row_index);
} else {
printf("ERROR: node %d not found\n", tree[row][1]);
}
}
/* "visit" node */
printf("i am at node %d.\n", tree[row][0]);
if (tree[row][1] == -1 && tree[row][2] == -1) {
printf("node %d has no children.\n", tree[row][0]);
return;
}
if (tree[row][2] != -1) {
row_index = find_index(tree, tree[row][2]);
if (row_index != -1) {
printf("value of row_index is %d\n", row_index);
printf("visiting node %d next.\n", tree[row_index][0]);
in_order(tree, row_index);
} else {
printf("ERROR: node %d not found\n", tree[row][2]);
}
}
}
/* post_order: left, right, root */
void post_order(int tree[][MAX_COLS], int row)
{
int row_index;
if (tree[row][1] != -1) {
row_index = find_index(tree, tree[row][1]);
if (row_index != -1) {
printf("value of row_index is %d\n", row_index);
printf("visiting node %d next.\n", tree[row_index][0]);
post_order(tree, row_index);
} else {
printf("ERROR: node %d not found\n", tree[row][1]);
}
}
if (tree[row][2] != -1) {
row_index = find_index(tree, tree[row][2]);
if (row_index != -1) {
printf("value of row_index is %d\n", row_index);
printf("visiting node %d next.\n", tree[row_index][0]);
post_order(tree, row_index);
} else {
printf("ERROR: node %d not found\n", tree[row][2]);
}
}
printf("i am at node %d.\n", tree[row][0]);
if (tree[row][1] == -1 && tree[row][2] == -1) {
printf("node %d has no children.\n", tree[row][0]);
return;
}
}
int find_index(int tree[][MAX_COLS], int node)
{
int i;
for (i = 0; i < MAX_ROWS; ++i)
if (tree[i][0] == node)
return i;
return -1;
}
/* pre_order: root, left, right */
void pre_order(int tree[][MAX_COLS], int row)
{
printf("i am at node %d.\n", tree[row][0]);
if (tree[row][1] == -1 && tree[row][2] == -1) {
printf("node %d has no children.\n", tree[row][0]);
return;
}
int row_index;
if (tree[row][1] != -1) {
row_index = find_index(tree, tree[row][1]);
if (row_index != -1) {
printf("value of row_index is %d\n", row_index);
printf("visiting node %d next.\n", tree[row_index][0]);
pre_order(tree, row_index);
} else {
printf("ERROR: node %d not found\n", tree[row][1]);
}
}
if (tree[row][2] != -1) {
row_index = find_index(tree, tree[row][2]);
if (row_index != -1) {
printf("value of row_index is %d\n", row_index);
printf("visiting node %d next.\n", tree[row_index][0]);
pre_order(tree, row_index);
} else {
printf("ERROR: node %d not found\n", tree[row][2]);
}
}
}
void print_children(int tree[][MAX_COLS], int row)
{
if (row > MAX_ROWS) return;
if (tree[row][1] != -1 && tree[row][2] != -1)
printf("the children of %d are %d and %d\n", tree[row][0],
tree[row][1], tree[row][2]);
else if (tree[row][1] == -1 && tree[row][2] == -1)
printf("%d does not have any children.\n", tree[row][0]);
else {
printf("the child of %d is ", tree[row][0]);
if (tree[row][1] != -1)
printf("%d\n", tree[row][1]);
else if (tree[row][2] != -1)
printf("%d\n", tree[row][2]);
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.