level order binary search 
Author Message
 level order binary search

What is the algorithm for a level order search of a binary tree?
Knuth leaves it as an "exercise for the reader".  Peachy.

Thanks, Ed



Tue, 15 Sep 1998 03:00:00 GMT  
 level order binary search

Quote:

>What is the algorithm for a level order search of a binary tree?
>Knuth leaves it as an "exercise for the reader".  Peachy.

>Thanks, Ed

A level order traverse (or search) looks at the root, then all
nodes at level 2, then all nodes at level 3, and so on. In general
a node at level k is processed after all nodes at level k-1 and
before all nodes at level k+1.

The algorithm to do this is the following:

   Put the root node in a queue.
   while the queue is not empty
      remove a node from the queue and process it.
      put the children of the node just processed in the queue.
   end while

This is similar to the usual pre, in, and post order traversals
except that a queue is used instead of a stack.



Tue, 15 Sep 1998 03:00:00 GMT  
 
 [ 2 post ] 

 Relevant Pages 

1. Level order Traversal of a Binary Tree ??

2. Binary Search and Sequential Search

3. how can search binary code in binary file?

4. Building Tree for list of nodes in level order

5. Level Order Travesal

6. Level Ordered Btree Problem

7. the definitive ordering of -l searches

8. Importlib search order

9. Need to make compiler search directories in specific order

10. Include Search Order

11. link search order with /nodefaultlib

12. Include File Search Order

 

 
Powered by phpBB® Forum Software