### Thread: breadth-first traversal of a binary tree

1. No Profile Picture
Contributing User
Devshed Newbie (0 - 499 posts)

Join Date
Oct 2003
Location
Posts
228
Rep Power
12

#### breadth-first traversal of a binary tree

I have been looking at the breadth first traversal that DaWei included in his binary tree creation and display program. Here is just the showTree() function. I was actually on the verge of quitting trying because I feel over my head, and I am not looking for sympathy, just relating the reason for this post... since I have found this forum to be a great source of encouragement as well as help. Anyhooo, I understand that in all the references on the internet I can find to a breadth-first traversal, you need to make a FIFO structure, but don't understand why / how it is applied or works. If anyone is not too busy, could you give me a hand understanding. Just to cannibalize this code I need to understand more than I do.
I am trying to write a basic breadth-first traversal that will print each level on a new line,
Thanks...

Code:
```void showTree (fP tQ, BTREE p, int l)
{
// Originally a much simpler breadth-first traversal, expanded
// to graphically present the tree organization.
int i = 0;
int line, level = -1;
char *sPos;
BTREE trv;
tQ->fUsage = 0;
tQ->fSize = 64;
tQ->fGet = tQ->fPut = &tQ->fData [0];

put (tQ, p);
while (tQ->fUsage)
{
trv = get (tQ);
if (trv->level > level) level = trv->level;
if (level > l) break;
switch (level)
{
case 0: line = 0;
break;
case 1: line = 8;
break;
case 2: line = 12;
break;
case 3: line = 15;
break;
case 4: line = 17;
break;
}
sPos = &screen [line][vCoord [i]];
if (trv->d >= 0)
sprintf (sPos, "%02d", trv->d);
else
sprintf (sPos, "%s", "  ");
*(sPos + 2) = ' ';
i++;
if ((trv->left) || (trv->right))
{
if (trv->left)  put (tQ, trv->left);
if (trv->right) put (tQ, trv->right);
}
}
printf ("\n");
for (i = 0; i < 18; i++) printf ("%s\n", screen [i]);
}```
Last edited by gtpc; June 8th, 2004 at 01:36 PM.
2. Hi, Bob. Here's the code, stripped to traversal. I haven't compiled it since I stripped it, might have broken it . :o
Code:
```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);
}
}
}```
Here the while loop is 'unrolled' for clarity. It's a fifo, the 'get' works from top down. Simplified to neither child if no child, but
as you can see with experimentation, it works either way.
Code:
```put node (root)

while nodes
{
get node, print it (root) (or otherwise record it)
put left
put right

get node (left) print it (left)
put left-left
put left-right

get node (right) print it (right)
put right-left
put right-right

get node (left-left) print it NO CHILDREN, NO PUTS

get node (left-right) print it NO CHILDREN, NO PUTS

get node (right-left) print it NO CHILDREN, NO PUTS

get node (right-right) print it NO CHILDREN, NO PUTS

get node (fifo empty, break, done)
}```
Regards,

David

EDIT: I see some hangover inefficiency there, part of the old show manipulation, trim away.

EDIT 2: To print on a new line for each level, you'll need to add level information back in or derive it. It easily prints a breadth first traversal a level per line regardless of tree completeness, however, it won't print a proper positional representation of an incomplete tree without faking a complete tree with padding. Thus all the hooraw in the showTree procedure, as well as the padTree thangy. Cute, though, if I say so mesel' :cool: .
Last edited by DaWei_M; June 4th, 2004 at 03:25 PM.
3. No Profile Picture
Contributing User
Devshed Newbie (0 - 499 posts)

Join Date
Oct 2003
Location
Posts
228
Rep Power
12
Thanks Dave. I will have a look at this and see if I can make it work. I really want to get past this AND understand it.

EDIT: you are right, I need to get some level info in this. That is in fact one of the great hurdles here. I see even in your code that you added 'int level' in the struct node, but I don't see anywhere in the program where level is added to. Since the level goes basically :
level 1, 1 node
level 2, 2 nodes
level 3, 4, nodes, etc, I see it is times 2 each level, I am thinking is there a way I can just use that? Of course then when I move on to general trees, which are not binary (do not have 2 children per parent) it will be useless... sigh****
Last edited by gtpc; June 4th, 2004 at 04:18 PM.
4. [QUOTE=gtpc] you need to make a FIFO structure, but don't understand why / how it is applied or works. [/QOUTE]

say this is your tree
Code:
```            h
/       \
d         p
/  \        / \
b    f       k   s
/\   /\     /\   /\
a c  e g   j m r   t```
You start at the top node(h), you do what you have to and then you add the two children to the FIFO
FIFO = d->p
You visit d (remove from FIFO) and add it's children to the FIFO
FIFO=p->b->f
Now you visit p(remove from FIFO) and add it's children
FIFO=b->f->k->s
Now you visit b(remove from FIFO) and add it's children.
FIF0=f->k->s->a->c
etc until your FIFO is empty(NULL)

If you don't need to keep track of what level the node appears in the tree it's just a matter of having a simple link list with a top and an end pointer. You add the pointers(to tree node) of the children to the end pointer, and you remove the pointers(to tree nodes) from the top pointer.

By doing you get a list of all the pointers to the nodes in the same level in the tree in a row in FIFO. All the pointers to the nodes directly below that level, will follow those pointers.

If you have to keep track of what level each node(tree) appears in the tree you'll have to add a int level to each node of the FIFO. Of course the children of a node, will be one level further down the tree than the parent.

If you're trying to print out a "image" of the tree, and it's not a complete tree, you'll have to add another int variable call it x to each node of the FIFO, that keeps track of how far to the right the node appears in a tree. The left child will have that value 2*x-1, and the right child will have that value 2*x. In this way you can calculate how many nodes are missing between two nodes that appear in that level of the tree.
Last edited by fisch; June 4th, 2004 at 06:13 PM.
5. The count levels procedure. Pretty sure it would work for ternary and greater trees with suitable additions.
Code:
```int countLevels (BTREE p, int level)
{
// This is simpler if you only record the level in
// the node and don't return it.
// If you return it, the greater of the l (lesser or left) and g (greater/right)
// levels is returned from each recursive call
int lLevel = 0, gLevel = 0; // Not necessary unless the level count is to be returned
p->level = level;           // Puts the level in the node
level++;                    // Increments the level to pass to the children
// Pass their level to the children in the recursive call
if (p->left) lLevel = countLevels (p->left, level);
if (p->right) gLevel = countLevels (p->right, level);
// Test for the greatest level from the two children and return it.
gLevel = gLevel > lLevel? gLevel : lLevel;
level = level > gLevel? level : gLevel;
return level;
}```
6. Fisch is correct that the proper position on the screen can be calculated if the nodes are labeled. The tree can be displayed without requiring gotoxy type positioning and just constructed with the proper number of spaces. I did it this way once.

Unfortunately, the 'tween' spacing for each line varies and it really gets hairy if you want to take advantage of overlapping into empty areas where possible to reduce the tree width. It turns out to be simpler to just make a 2D template of spaces and connectors and plop the values into the appropriate position in the grid. The five-level limit I have is based on a good fit to an 80-char line.

That confusing array, vCoord, is just a sequential list of all the horizontal positions, without regard to line number. You'll notice in showTree that the index begins at 0 and just goes up one for each thangy printed, whether it's node contents or spaces for a dummy node, no attention paid to level by 'i', just incremented through the position list.
7. No Profile Picture
Contributing User
Devshed Newbie (0 - 499 posts)

Join Date
Oct 2003
Location
Posts
228
Rep Power
12
Hahaha! This is worse than I thought. And the sun and warmth and my bike and the golf course are not helping! Dave, are you saying that the countLevels() function is where I get my level info to insert in each node. I dont want to make a 2D tree, but in order to print a newline for each level, don't I still need level info in each node?
8. You need the level info. countLevels is putting it into each node with this statement:
Code:
`    p->level = level;           // Puts the level in the node`
You start with zero, that gets put into the root node. You bump it one and do a recursive call to the children. They bump it one and call THEIR children. Child subtrees may not each be the same depth, so when both children return, you take the deepest level and return that to YOUR caller, so the final answer returned to main is the deepest level. However, that has no bearing on the level stashed in the nodes, which goes up one for each set of children called.

Then, when you do the breadth-first, you start with a reference level value of zero and start printing the nodes. When a node's level value goes above the reference level, you generate a newline and set the reference level to the new level. Then, when a node's level goes above THAT, you generate another newline, and so on.

Sunny and warm here too, but my 2-wood looks suspiciously like a weed eater :-).

Regards.
9. No Profile Picture
Contributing User
Devshed Newbie (0 - 499 posts)

Join Date
Oct 2003
Location
Posts
228
Rep Power
12
Hey there again. Instead of using countLevels(), I just included a level++ in create_tree() and as you can see by running the program, it puts the correct levels on each node (perhaps it would not on an incomplete tree. Regardless, I am still having trouble to output a newline at the end of each new level. It was of course simple for the root, again as you can see in the breadthFirst function, but beyond that, where do I go? Thought I was on a roll since I have the level information in each node now. Suggestions? Help?

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");
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;
}```
Last edited by gtpc; June 8th, 2004 at 01:34 PM.
10. Nothing wrong with putting the level in the node when you generate the tree, if the tree doesn't change. I did it as I did because of tree rearrangements caused by insertions, deletions, re-heaping, and so forth. I'll have a look. Meanwhile, you hit a bucket of balls for me and I'll have a six-pack for you :-).
11. Procedure modified and commented.
Code:
```/* breadth-first traversal for a binary tree */
void breadthFirst (fP tQ, BTREE p)
{
int level; // Keep track of CURRENT level
BTREE trv;
tQ->fUsage = 0;
tQ->fSize = 64;
tQ->fGet = tQ->fPut = &tQ->fData [0];

// We want every level to begin with a new line, so
// set this value to trigger a new line for even the root.
level = -1;

put (tQ, p);
while (tQ->fUsage)
{
trv = get (tQ);
{
// Check to see if the level has changed
if (trv->level > level)
{
// It has changed, print a new line
printf ("\n");
// Store the new level for subsequent comparisons
level = trv->level;
}
// Print the node value; happens regardless of level change
printf ("%d ", trv->d);
// I took out the redundant test for node validity here
if (trv->left) put (tQ, trv->left);
if (trv->right) put (tQ, trv->right);
}
}
}```
Output:
Code:
```Tree printed 'pre-order'
12 (level->1),
7 (level->2),
4 (level->3),
2 (level->4),
6 (level->4),
9 (level->3),
8 (level->4),
11 (level->4),
23 (level->2),
17 (level->3),
15 (level->4),
21 (level->4),
27 (level->3),
24 (level->4),
30 (level->4),

Tree inorder
2 4 6 7 8 9 11 12 15 17 21 23 24 27 30
Number of nodes = 15
Number of Leaf nodes = 8
The tree in breadth-first order...

12
7 23
4 9 17 27
2 6 8 11 15 21 24 30
Press any key to continue```
12. No Profile Picture
Contributing User
Devshed Newbie (0 - 499 posts)

Join Date
Oct 2003
Location
Posts
228
Rep Power
12
OF course, put the newline at the beginning, etc.! I must broaden my mind, and thanks a bunch. That is exactly what I was trying to get.
13. No Profile Picture
Registered User
Devshed Newbie (0 - 499 posts)

Join Date
Nov 2013
Posts
1
Rep Power
0

#### Full Code

Hello, im a beginning on c and i need this Breadth First full code can we send it to me?

When i copy all codes above it say just one thing that i really dont know how to repair.

1 IntelliSense: return value type does not match the function type c:\Users\wilme\Documents\Visual Studio 2012\Projects\ConsoleApplication4\ConsoleApplication4\ConsoleApplication4.cpp 120 11 ConsoleApplication4

can we help me solve it?

follow the location of error in the code.

BTREE new_node()
{
return (malloc(sizeof(NODE)));
}