Travis Jones' Level order tree traversal algorithm.

TJTreeTraversal.c

#include <stdio.h>
#include <math.h>
#include <stdlib.h>

struct node
{
	int number;
	struct node ** children;
};
int count=0;
void makeTree(struct node *root, int numChildren, int rowsLeft);
/*
Builds a k-ary tree.
Precondition: root must already be pointing to a valid node.
*/
void printNode(struct node *root, int * path);
//Finds node specified by a k-ary number, where each digit is placed in the array path.
void convertNumber(int * destination, int number, int base, int numDigits, int maxDigits);
//Converts any number into a k-ary number, with each digit in a different element of an array.
void deleteTree(struct node *root, int k);
//Recursively cleans memory.

int main()
{
	//Make first node. 
	struct node *root=NULL;
	root=(struct node*)malloc(sizeof(struct node));
	root->number=0;
	
	//k is the number of child nodes per node. Rows is how many levels there are to the tree. 
	int k=0, rows=0;

	printf("Number of rows: ");
	scanf("%d", &rows);

	printf("Number of children per row: ");
	scanf("%d", &k);

	//Make the tree.
	makeTree(root, k, rows);
	
	int i, j, l;//i: current row, j: current node in row.

	int digits[rows];
	
	for(i=0; i<rows; i++) //i corresponds to both the current level, and the number of digits needed in the array digits.
	{
		for(j=0; j<(int)pow(k, i); j++) //pow(k, i) is the number of nodes in each level. j cycles through each node.
		{
			convertNumber(digits, j, k, i, rows); //digits is the array. j is the number needed to be converted to k-ary. 
                                                              //k is the base. i is the necessary number of digits.
			printNode(root, digits); //starts at point -1 because it hasn't chosen any children. Element 0 is the first choice.
		}
		printf("\n");
	}
	deleteTree(root, k); //Clean up memory.
	return 0;
}

void makeTree(struct node *root, int numChildren, int rowsLeft)
{
	//If its as deep as is needed, return.
	if(rowsLeft==0)
		return;
	//Initialize a dynamic number of pointers to nodes, of numChildren size.
	struct node *tempChild;
	root->children=(struct node**)malloc(sizeof(struct node*)*numChildren);//(struct node **)malloc(numChildren*sizeof(struct node*));
	int i;
	//Make each child, set its number, and make its children.
	for(i=0; i<numChildren; i++)
	{
		root->children[i]=(struct node*)malloc(sizeof(struct node));//(struct node *)malloc(sizeof(struct node));
		tempChild=root->children[i];
		tempChild->number=i;
		makeTree(tempChild, numChildren, rowsLeft-1);
	}
}

void printNode(struct node *root, int * path)
{
	int cur_depth=-1;
	//If there's no further directions in the path, or a child is null, print the current nodes number and return.
	while(1)
	{
		if(path[cur_depth+1]<0)
		{
			printf("%d", root->number);
			return;
		}
		if(root->children[path[cur_depth+1]]==NULL)
			return;
		//Go deeper.
		root=root->children[path[cur_depth+1]];
		cur_depth++;
	}
}

void convertNumber(int * destination, int number, int base, int numDigits, int maxDigits)
{
	int i;
	//Initializes all digits to -1.
	for(i=0; i<maxDigits; i++)
		destination[i]=-1;
	//Sets each digit.
	for(i=numDigits-1; i>=0; i--)
	{
		destination[i]=number%base;
		number/=base;
	}
}

void deleteTree(struct node *root, int k)
{
	int i=0;
	for(i=0; i<k; i++)
	{
		if(root->children)
			deleteTree(root->children[i], k);
	} 
	free(root);
}