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