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