468,242 Members | 1,605 Online
Bytes | Developer Community
New Post

Home Posts Topics Members FAQ

Post your question to a community of 468,242 developers. It's quick & easy.

how to walk a binary tree

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!
Jul 22 '05 #1
7 3190
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
}
}
Jul 22 '05 #2
"pembed2003" <pe********@yahoo.com> wrote in message
news:db**************************@posting.google.c 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::priority_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.
Jul 22 '05 #3
"red floyd" <no*****@here.dude> 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.
}

Jul 22 '05 #4
Siemel Naran wrote:
"red floyd" <no*****@here.dude> 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.
Jul 22 '05 #5

"red floyd" <no*****@here.dude> wrote in message
news:iE*******************@newssvr27.news.prodigy. 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?

Jul 22 '05 #6
"Anonymous" <ih*******@nowhere.com> wrote in message news:qtVgc.1547
"red floyd" <no*****@here.dude> 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;
}
Jul 22 '05 #7
red floyd <no*****@here.dude> wrote in message news:<iE*******************@newssvr27.news.prodigy .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!
Jul 22 '05 #8

This discussion thread is closed

Replies have been disabled for this discussion.

Similar topics

11 posts views Thread by rbt | last post: by
1 post views Thread by Jerry Khoo | last post: by
8 posts views Thread by Jerry Khoo | last post: by
4 posts views Thread by Tarique Jawed | last post: by
22 posts views Thread by delraydog | last post: by
7 posts views Thread by KraftDiner | last post: by
9 posts views Thread by silverburgh.meryl | last post: by
7 posts views Thread by Vinodh | last post: by
reply views Thread by NPC403 | last post: by
reply views Thread by kermitthefrogpy | last post: by
By using this site, you agree to our Privacy Policy and Terms of Use.