walking a binary tree

[pembed2003]

Hi,
I have a question about how to walk a binary tree. Suppose that I have
this binary tree:

8
/ \
5 16
/ \ / \
3 7 9 22
/ \ / \ / \
1 4 6 10 17 34
/
0

and I want to print out the binary tree like:

8 5 16 3 7 9 22 1 4 6 10 17 34 0

That's, print all the nodes out in level order. Currently, I have the
following:

void order(node* d,int level,int child){
if(d){
int w = level + child;
printf("%d [%d]\n",d->data,w);
order(d->left,out,level + 2,1); // one more level for a left child
order(d->right,out,level + 2,2); // one more level for a right child
}
}

My plan is that each node has a weight which is equal to the level the
node is at and whether it's a left or right child. The idea is that
the deeper the node, the "heavier" it's and left child is always
heavier than the right child. Instead of a printf statement, I can put
the nodes into an array, and then I can sort the array (using a stable
sort) according to their weight and print out each nodes. Although
this seems to work, the book that I am reading suggest using a queue
to solve the problem, but I don't know how a queue can help. Can
someone give me a little help? I am NOT looking for actual code, just
some hints on how a queue can help me manage this level-order walk of
the binary tree? Thanks!

 

[James Hu]

[snip question about printing a binary tree in level order]

Can someone give me a little help? I am NOT looking for actual code,
just some hints on how a queue can help me manage this level-order
walk of the binary tree? Thanks!

You don't have a C question. Try comp.programming.

-- James

 

[Nick Austin]

Hi,
I have a question about how to walk a binary tree. Suppose that I have
this binary tree:

8
/ \
5 16
/ \ / \
3 7 9 22
/ \ / \ / \
1 4 6 10 17 34
/
0

and I want to print out the binary tree like:

8 5 16 3 7 9 22 1 4 6 10 17 34 0

Forget the queue.

Walk the entire tree repeatedly each time printing the nodes at
a certain depth. Increment the depth between each walk and stop
when there are no more child nodes at the current depth.

Nick.

 

[Simon Biber]

I have a question about how to walk a binary tree. Suppose that I
have this binary tree:

8
/ \
5 16
/ \ / \
3 7 9 22
/ \ / \ / \
1 4 6 10 17 34
/
0

and I want to print out the binary tree like:

8 5 16 3 7 9 22 1 4 6 10 17 34 0

That's, print all the nodes out in level order.

I would have two separate functions. The outer tree print function just
loops through each level of the tree (in this case 0 to 4 inclusive) calling
the inner function for each level. The inner function is designed to print
out all the values on a specified level of the tree. The inner function can
call itself recursively with a parameter to keep track of the current level;
as soon as the specified level is reached it will print the data.

/* If reached specified level, print data, else continue to children */
void print_level(struct tree *tree, int spec_level, int cur_level)
{
if(spec_level == cur_level)
printf("%d ", tree->data);
else
{
if(tree->left) print_level(tree->left, spec_level, cur_level + 1);
if(tree->right) print_level(tree->right, spec_level, cur_level + 1);
}
}

/* For each level in turn, print the values on that level */
void print_tree(struct tree *tree)
{
int i;
for(i = 0; i < 5; i++)
{
print_level(tree, i, 0);
}
}

Note the magic number 5 for the number of levels in the whole tree; that
could be eliminated with another function to simply count the number of
levels:

int num_levels(struct tree *tree)
{
int left, right;
if(tree == NULL)
return 0;
left = num_levels(tree->left) + 1;
right = num_levels(tree->right) + 1;
return left > right ? left : right;
}

I hope this helps -- even though I didn't use a queue or sorting.

 

[Peter Slootweg]

Hi,
I have a question about how to walk a binary tree. Suppose that I have
this binary tree:

8
/ \
5 16
/ \ / \
3 7 9 22
/ \ / \ / \
1 4 6 10 17 34
/
0

and I want to print out the binary tree like:

8 5 16 3 7 9 22 1 4 6 10 17 34 0

That's, print all the nodes out in level order. Currently, I have the
following:

void order(node* d,int level,int child){
if(d){
int w = level + child;
printf("%d [%d]\n",d->data,w);
order(d->left,out,level + 2,1); // one more level for a left child
order(d->right,out,level + 2,2); // one more level for a right child
}
}

My plan is that each node has a weight which is equal to the level the
node is at and whether it's a left or right child. The idea is that
the deeper the node, the "heavier" it's and left child is always
heavier than the right child. Instead of a printf statement, I can put
the nodes into an array, and then I can sort the array (using a stable
sort) according to their weight and print out each nodes. Although
this seems to work, the book that I am reading suggest using a queue
to solve the problem, but I don't know how a queue can help. Can
someone give me a little help? I am NOT looking for actual code, just
some hints on how a queue can help me manage this level-order walk of
the binary tree? Thanks!

use the queue to hold pointers to all the nodes in the current level of the
tree
when you retrieve/remove the first element from the queue print its contents
and add its non emtpy children to the queue

if non empty root add the root to the q
while the q isn't empty
retrieve/remove the front q element
print the elements data
if non empty left child add left child to the q
if non empty right child add right child to the q