Code:

/* question 10_34, print out the nodes of a binary tree in level
order. The root node is at level 0. On the next level of nodes are the
children of the previous level. First, print the root node. Then print
the left child and the right child that are at level 1. Continue printing
the nodes from left to right, level by level. This is called breadth-first
traversal */
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#define SIZE 15
typedef int DATA;
struct node {
DATA d;
struct node *left;
struct node *right;
int level;
};
typedef struct node NODE;
typedef NODE *BTREE;
// Simple fifo definition, used to institute
// a breadth-first traversal.
typedef struct sFifo *fP;
typedef struct sFifo
{
BTREE fData [64];
int fSize;
int fUsage;
BTREE *fPut;
BTREE *fGet;
} cFifo;
void inorder(const BTREE root);
void preorder(const BTREE root);
void postorder(const BTREE root);
BTREE new_node();
BTREE init_node(DATA d1, BTREE p1, BTREE p2, int level);
BTREE insert(BTREE parent, BTREE root, int item);
int count_nodes(BTREE root, int cnt);
int count_Lnodes(BTREE root, int cnt);
BTREE create_tree(int a[], int i, int size, int level);
int *order_array(int a[]);
void divide_array(int a[], int b[], int c[], int size);
int find_center(int a[], int size);
void print_array(int ordered_array[]);
void bfTraversal(BTREE parent, BTREE root, int i, int j);
void breadthFirst (fP tQ, BTREE p);
BTREE get (fP q);
void put (fP q, BTREE p);
int countLevels (BTREE p, int level);
int main(void)
{
BTREE b_tree;
int array_of_ints[] = {2, 4, 6, 7, 8, 9, 11, 12, 15, 17, 21, 23, 24, 27, 30};
int key[15] = {0};
int *keyPtr = 0;
int nLevels;
cFifo treeQ = {0};
b_tree = create_tree(array_of_ints, 0, SIZE, 0);
printf("Tree printed 'pre-order'\n");
preorder (b_tree);
printf("\nTree inorder\n");
inorder (b_tree);
putchar('\n');
printf("Number of nodes = %d\n", count_nodes(b_tree, 0));
printf("Number of Leaf nodes = %d\n", count_Lnodes(b_tree, 0));
printf("The tree in breadth-first order...\n");
breadthFirst(&treeQ, b_tree);
putchar('\n');
return 0;
}
/* breadth-first traversal for a binary tree */
void breadthFirst (fP tQ, BTREE p)
{
BTREE trv;
tQ->fUsage = 0;
tQ->fSize = 64;
tQ->fGet = tQ->fPut = &tQ->fData [0];
put (tQ, p);
while (tQ->fUsage)
{
trv = get (tQ);
{
printf ("%d ", trv->d);
if ((trv->left) || (trv->right))
{
if (trv->left) put (tQ, trv->left);
if (trv->right) put (tQ, trv->right);
}
if (trv->level == 1) putchar('\n'); // new line after EACH line is full??
}
}
}
/* inorder binary tree traversal and print */
void inorder(const BTREE parent)
{
if (parent != NULL) {
inorder(parent->left); /* recur left */
printf("%d ", parent->d);
inorder(parent->right); /* recur right */
}
}
/* preorder binary tree traversal and print */
void preorder(const BTREE root)
{
if (root != NULL) {
printf("%d (level->%d), \n", root->d, root->level);
preorder(root->left); /* recur left */
preorder(root->right); /* recur right */
}
}
/* creating binary trees */
BTREE new_node()
{
return (malloc(sizeof(NODE)));
}
BTREE init_node(DATA d1, BTREE p1, BTREE p2, int level)
{
BTREE t;
t = new_node();
t->d = d1;
t->left = p1;
t->right = p2;
t->level = level;
return t;
}
// create ordered binary tree using recursion, divide array, then insert center int
BTREE create_tree(int a[], int i, int size, int level)
{
int b[SIZE] = {0}, c[SIZE] = {0};
if (size == 0) return NULL;
if (size == 1) init_node(a[0], NULL, NULL, level);
if (i <= SIZE)
{
level++;
divide_array(a, b, c, size); // b and c are a divided in 2
return init_node(find_center(a, size), create_tree(b, 2*i+1, size-size/2-1, level),
create_tree(c, 2*i+2, size/2, level), level);
}
}
void print_array(int ordered_array[])
{
int i;
for (i = 0; i < SIZE; ++i)
printf("%d ", ordered_array[i]);
putchar('\n');
putchar('\n');
}
// put an array in alphabetical order
int *order_array(int a[])
{
int j, i, temp;
int *b = a;
for (i = 0; i < SIZE-1; ++i)
for (j = i+1; j < SIZE; ++j)
if (a[i] > a[j])
{
temp = a[i];
a[i] = a[j];
a[j] = temp;
}
return b;
}
// send function a, the array to be divided, and b and c, the 2 array pointers
void divide_array(int a[], int b[], int c[], int size)
{
int i, j;
for (i = 0; i < size/2; ++i) b[i] = a[i];
i++; // removing middle item, the one being added
for (j = 0; i < size; ++i, ++j) c[j] = a[i];
}
// find center of an array
int find_center(int a[], int size)
{
int center;
center = (size-1)/2;
return a[center];
}
// count total number of nodes
int count_nodes(BTREE root, int cnt)
{
if (root != NULL) {
cnt = count_nodes(root->left, cnt); /* recur left */
cnt = count_nodes(root->right, ++cnt); /* recur right */
}
return cnt;
}
// count number of leaf nodes
int count_Lnodes(BTREE root, int cnt)
{
if (root != NULL) {
cnt = count_Lnodes(root->left, cnt);
cnt = count_Lnodes(root->right, cnt);
if (root->left == NULL && root->right == NULL) ++cnt;
}
return cnt;
}
BTREE get (fP q)
{
// Simple fifo get procedure
BTREE p = NULL;
if (q->fUsage)
{
q->fUsage--;
p = *q->fGet++;
}
return p;
}
void put (fP q, BTREE p)
{
// Simple fifo put procedure
if (q->fUsage < q->fSize)
{
*q->fPut++ = p;
q->fUsage++;
}
}
// not used in this program right now
int countLevels (BTREE p, int level)
{
// This is simpler if you only record the level in
// the node and don't return it
int lLevel = 0, gLevel = 0;
p->level = level;
level++;
if (p->left) lLevel = countLevels (p->left, level);
if (p->right) gLevel = countLevels (p->right, level);
gLevel = gLevel > lLevel? gLevel : lLevel;
level = level > gLevel? level : gLevel;
return level;
}

Tweet This+ 1 thisPost To Linkedin