Array-based tree traversal

tree.c

/* 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]);
        }
}