473,216 Members | 1,323 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,216 software developers and data experts.

walking 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,out,level + 2,1); // one more level for a left child
order(d->right,out,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!
Nov 14 '05 #1
5 9528
On 2004-04-19, pembed2003 <pe********@yahoo.com> wrote:

[snip question about printing a binary tree in level order]
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!


You don't have a C question. Try comp.programming.

-- James
Nov 14 '05 #2
On 18 Apr 2004 21:47:29 -0700, pe********@yahoo.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


Forget the queue.

Walk the entire tree repeatedly each time printing the nodes at
a certain depth. Increment the depth between each walk and stop
when there are no more child nodes at the current depth.

Nick.

Nov 14 '05 #3
"pembed2003" <pe********@yahoo.com> wrote:
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.


I would have two separate functions. The outer tree print function just
loops through each level of the tree (in this case 0 to 4 inclusive) calling
the inner function for each level. The inner function is designed to print
out all the values on a specified level of the tree. The inner function can
call itself recursively with a parameter to keep track of the current level;
as soon as the specified level is reached it will print the data.

/* If reached specified level, print data, else continue to children */
void print_level(struct tree *tree, int spec_level, int cur_level)
{
if(spec_level == cur_level)
printf("%d ", tree->data);
else
{
if(tree->left) print_level(tree->left, spec_level, cur_level + 1);
if(tree->right) print_level(tree->right, spec_level, cur_level + 1);
}
}

/* For each level in turn, print the values on that level */
void print_tree(struct tree *tree)
{
int i;
for(i = 0; i < 5; i++)
{
print_level(tree, i, 0);
}
}

Note the magic number 5 for the number of levels in the whole tree; that
could be eliminated with another function to simply count the number of
levels:

int num_levels(struct tree *tree)
{
int left, right;
if(tree == NULL)
return 0;
left = num_levels(tree->left) + 1;
right = num_levels(tree->right) + 1;
return left > right ? left : right;
}

I hope this helps -- even though I didn't use a queue or sorting.

--
Simon.
Nov 14 '05 #4

"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

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


use the queue to hold pointers to all the nodes in the current level of the
tree
when you retrieve/remove the first element from the queue print its contents
and add its non emtpy children to the queue

if non empty root add the root to the q
while the q isn't empty
retrieve/remove the front q element
print the elements data
if non empty left child add left child to the q
if non empty right child add right child to the q
Nov 14 '05 #5
Don't know if you still need it, but look on wikipedia under their article on binary trees, theres some pretty good suedo-code on level order (using a queue).
May 1 '06 #6

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

1
by: Jerry Khoo | last post by:
hello, everybody, i am kinda new here, nice to meet u all. Now, i am > cs students and are now facing difficult problems in understanding > what a binary tree is, how it works, and the algorithm...
8
by: Jerry Khoo | last post by:
hello, everybody, i am kinda new here, nice to meet u all. Now, i am cs students and are now facing difficult problems in understanding what a binary tree is, how it works, and the algorithm to...
11
by: jova | last post by:
Is there a difference between a Binary Tree and a Binary Search Tree? If so can someone please explain. Thank You.
4
by: Tarique Jawed | last post by:
Alright I needed some help regarding a removal of a binary search tree. Yes its for a class, and yes I have tried working on it on my own, so no patronizing please. I have most of the code working,...
15
by: Foodbank | last post by:
Hi all, I'm trying to do a binary search and collect some stats from a text file in order to compare the processing times of this program (binary searching) versus an old program using linked...
1
by: Zachary Hartnett | last post by:
I was trying to write a routine this morning that would open a given assembly, walk the inheritance tree of classes in the assembly, and provide a list of classes in the assembly that inherit from...
4
by: Ken | last post by:
I have a binary tree in VB NET and insertions seem to be slow. The program receives data from one source and inserts it into the tree. The program receives data from another source and...
1
by: hn.ft.pris | last post by:
I have the following code: Tree.h defines a simple binary search tree node structure ########## FILE Tree.h ################ #ifndef TREE_H #define TREE_H //using namespace std; template...
7
by: Vinodh | last post by:
Started reading about Binary Trees and got the following questions in mind. Please help. Definition of a Binary Tree from "Data Structures using C and C++ by Tanenbaum" goes like this, "A...
0
by: veera ravala | last post by:
ServiceNow is a powerful cloud-based platform that offers a wide range of services to help organizations manage their workflows, operations, and IT services more efficiently. At its core, ServiceNow...
0
by: VivesProcSPL | last post by:
Obviously, one of the original purposes of SQL is to make data query processing easy. The language uses many English-like terms and syntax in an effort to make it easy to learn, particularly for...
3
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 3 Jan 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). For other local times, please check World Time Buddy In...
0
by: jianzs | last post by:
Introduction Cloud-native applications are conventionally identified as those designed and nurtured on cloud infrastructure. Such applications, rooted in cloud technologies, skillfully benefit from...
0
by: mar23 | last post by:
Here's the situation. I have a form called frmDiceInventory with subform called subfrmDice. The subform's control source is linked to a query called qryDiceInventory. I've been trying to pick up the...
2
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 7 Feb 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:30 (7.30PM). In this month's session, the creator of the excellent VBE...
0
by: fareedcanada | last post by:
Hello I am trying to split number on their count. suppose i have 121314151617 (12cnt) then number should be split like 12,13,14,15,16,17 and if 11314151617 (11cnt) then should be split like...
0
Git
by: egorbl4 | last post by:
Скачал я git, хотел начать настройку, а там вылезло вот это Что это? Что мне с этим делать? ...
1
by: davi5007 | last post by:
Hi, Basically, I am trying to automate a field named TraceabilityNo into a web page from an access form. I've got the serial held in the variable strSearchString. How can I get this into the...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.