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 levelorder walk of
the binary tree? Thanks! 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 levelorder 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" <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^N1
(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 levelorder 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.
"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.
}
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.
"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?
"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(x1)+fibonacci(x2);
}
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 <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! 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

1 post
views
Thread by hn.ft.pris 
last post: by

9 posts
views
Thread by silverburgh.meryl 
last post: by

7 posts
views
Thread by Vinodh 
last post: by
          