Solved
Need a function to do a level order traversal of a binary tree
Posted on 1998-08-04
Pretty urgent- I need a class member function to do a level by level traversal of a binary search tree. All the books I have give recursive code for in-, pre- and post-order traversal, but this seems rather different (and is iterative) I found a pseudocode version of a level-order graph traversal, but it leaves out the problem I am having- how to move from the node you are on to the adjacent one and so on down the tree. The pseudocode function I have is:
Assume a binary tree with n levels
Each node contains a boolean variable "visited"
Binary class has a member function to mark visited TRUE
Using a basic queue, which has a NotEmpty function that returns TRUE/FALSE.
Start at the root node
Enqueue the value in the root node
while (Queue not empty)
{
Dequeue first value
for (each unvisited node adjacent to the the current node)
{
Mark node as visited
Enqueue value in current node
} // end for
} // end while
That for loop condition is just a bit vague!! Like I said, my problem is how to move thru the tree. I could hard code for a set number of levels, but obviously this is not acceptable. So I need a fairly specific function, although you are free to use whatever (descriptive) names you want for any member/helper functions or pointers needed. I just need to be able to see what the function would do. I suspect though that it mainly requires pointer manipulations. I have the code for the bst, queue, etc, just need this one function...