Breadth-First search in trees?

[nAzGiRl2005]

What is a good formula for doing Breadth-first search in a binary tree?

I know how to do in-order traversal, with the following function:

void rprint(BT_NODE *p)
{
if(p==NULL)
return;

rprint(p->left);
printf("%s, %s\n", p->name, p->phone);
rprint(p->right);
}

and I've been trying to change this, in order to perform breadth-first search; but I don't seem to find a good formula for it.

How do you think I can go about this?

[liorean]

The target code here is simpler than the target in the article Fabulous Adventures In Coding: Breadth is sometimes better than depth (http://blogs.msdn.com/ericlippert/archive/2004/09/27/234826.aspx) (by Eric Lippert, one of the blogging softies that it really pays off reading), but I think the principle is the same. See if that maybe gives you some idea.

[nAzGiRl2005]

So, I still can't seem to find a good formula for Breadth-first search.
I know that I should treat my binary tree like a queue. But I'm not sure how to go about this level by level, so I can have:
root,
root->left
root->right
root->left->left
root->left->right
root->right->left
root->right->right
...
Let's say my tree looks something like this:

N
F S
A K P T
I need to do this in a way so it gives me: N F S A K P T

Is there a way I can write this program recursively in C?

[liorean]

Is there a way I can write this program recursively in C?Well, read that article. Then think a little about the stack.

Recursive handling basically means you are executing a tree of functions, a tree that will always be depth-first. So recursive handling will natively always result in depth-first. You CAN jump through hoops and make the beadth first search recursively (essentially what you need to do is relegate the next level for each tree to the last sibling), but it's something that recursion is ill suited for.

Instead make the stack explicit, just like Eric did. For each level in the tree, iterate through all elements and add them in order to the list of parents to expand in the next level. Or keep a single list for the entire tree.