«

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,level + 2,1); // one more level for a left child
order(d->right,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!

pembed2003 wrote:
> 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,level + 2,1); // one more level for a left child
> order(d->right,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!

What you want is actually OT for this group, you should look in an algorithms
group. That said, you should also google for "Breadth First Search".
Generally, the answer involves a queue.

e.g.:

[warning -- fragment, not full or tested code]

class Node;

void bfs(const Node* pNode)
{
std::queue<const Node*> q;

q.push(pNode);
while (!q.empty())
{
pNode = q.pop();
if (pNode->left)
q.push(pNode->left);
if (pNode->right)
q.push(pNode->right);
// do something with pNode here
}
}

"pembed2003" <> wrote in message
news: om...

> 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

Do you know the number of elements in the binary tree? If this is the case,
you can pass the location recursively to the print function on the left and
right child.

void print(const node *, int slot); // prints node->value in array[slot]

If the current node prints into slot, the left child prints into 2*slot+1,
and the right child prints into 2*slot+2. This method can work even if the
tree is not perfectly balanced; for example, if the node one 16 does not
exist, then array[2] will be NULL. In the printed string we will ignore
NULL values. The initial array size should be rounded up to the next 2^N-1
(eg. 4,5,6,7 rounds up to 7).

> 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,level + 2,1); // one more level for a left child
> order(d->right,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!

For breadth first search, one can use a queue. Push the left and right
child into the queue. As long as the queue has elements in it, pop the
element and print the node value, and push the node's children. So you push
level one 5, push level one 16, pop level one 5, print 5, push level two 3,
push level two 7, pop level one 16, print 16, push level two 9, push level
two 22. Use std::queue<const node *>.

If you have to use depth first search for some reason, you can use priority
queue. The depth level is the priority, and the lowest priority should be
popped first. Call the print function recursively on the left then right
node. You'll need std:riority_queue<struct> where struct contains the
depth level and node value. You'll push level zero 8, level one 5, level
two 3, ..., level one 16, etc. Popping, you'll get level zero 8, level one
5, level one 16, etc. It's conceptually similar to your original algorithm,
and the priority queue is like your sorted array.

"red floyd" <> wrote in message news:iEJgc.24133

> void bfs(const Node* pNode)
> {
> std::queue<const Node*> q;
>
> q.push(pNode);
> while (!q.empty())
> {
> pNode = q.pop();

In order to be strongly exception safe, the standard required pop to return
void. Use front to get a reference to the top element, and after processing
call pop.

> if (pNode->left)
> q.push(pNode->left);
> if (pNode->right)
> q.push(pNode->right);
> // do something with pNode here
> }

Call pop here.

> }

Siemel Naran wrote:
> "red floyd" <> wrote in message news:iEJgc.24133
> [Siemel's comments redacted]

Note that I did say it was fragmentary and not tested. It was
essentially an algorithmic description, not intended to be used as
production code.

"red floyd" <> wrote in message
news:iEJgc.24133$. com...
> pembed2003 wrote:
> > 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:
>
> [warning -- fragment, not full or tested code]
>
> class Node;
>
> void bfs(const Node* pNode)
> {
> std::queue<const Node*> q;
>
> q.push(pNode);
> while (!q.empty())
> {
> pNode = q.pop();
> if (pNode->left)
> q.push(pNode->left);
> if (pNode->right)
> q.push(pNode->right);
> // do something with pNode here
> }
> }

Maybe I'm being a bit thick here but can someone please point out to me
where the recursion is, here? How does bfs() search through an entire tree,
breadth first or otherwise?

"Anonymous" <> wrote in message news:qtVgc.1547
> "red floyd" <> wrote in message

> > void bfs(const Node* pNode)
> > {
> > std::queue<const Node*> q;
> >
> > q.push(pNode);
> > while (!q.empty())
> > {
> > pNode = q.pop();
> > if (pNode->left)
> > q.push(pNode->left);
> > if (pNode->right)
> > q.push(pNode->right);
> > // do something with pNode here
> > }
> > }
>
> Maybe I'm being a bit thick here but can someone please point out to
me
> where the recursion is, here? How does bfs() search through an entire
tree,
> breadth first or otherwise?

Pushing the node's children into the queue and repeating the while loop
covers the entire tree. When processing each of those nodes, you'll repeat
the body of the while loop which says to push that node's children into the
queue.

bfs() is not recursive. Any recursive algorithm would always proceed depth
first.

Also, many (if not all) recursive loops can be written as while.

unsigned fibonacci(unsigned x) {
if (x<=2u) return 1u;
return fibonacci(x-1)+fibonacci(x-2);
}

unsigned fibonacci(unsigned x) {
unsigned result = 1u;
unsigned prevresult = 1u;
for ( ; x>2u; --x) {
unsigned newresult = result+prevresult;
prevresult = result;
result = newresult;
}
return result;
}

red floyd <> wrote in message news:<iEJgc.24133$ .com>...
> pembed2003 wrote:
> > 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.

[snip]

>
> What you want is actually OT for this group, you should look in an algorithms
> group. That said, you should also google for "Breadth First Search".
> Generally, the answer involves a queue.
>
> e.g.:
>
> [warning -- fragment, not full or tested code]
>
> class Node;
>
> void bfs(const Node* pNode)
> {
> std::queue<const Node*> q;
>
> q.push(pNode);
> while (!q.empty())
> {
> pNode = q.pop();
> if (pNode->left)
> q.push(pNode->left);
> if (pNode->right)
> q.push(pNode->right);
> // do something with pNode here
> }
> }

Hi,
I tried your solution and it works fine. Thanks for the help!