how to walk a binary tree

P

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,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!
 
R

red floyd

pembed2003 said:
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
}
}
 
S

Siemel Naran

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.
 
S

Siemel Naran

red floyd said:
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.
 
R

red floyd

Siemel said:
[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.
 
A

Anonymous

red floyd said:
pembed2003 said:
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?
 
S

Siemel Naran

Anonymous said:
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;
}
 
P

pembed2003

red floyd said:
pembed2003 said:
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!
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,744
Messages
2,569,484
Members
44,903
Latest member
orderPeak8CBDGummies

Latest Threads

Top