Logo Data Structures and Algorithms with Object-Oriented Design Patterns in C++
next up previous contents index

Traversing a Search Tree

 

In Section gif, the inorder traversal of a binary tree is defined as follows:

  1. Traverse the left subtree; and then
  2. visit the root; and then
  3. traverse the right subtree.
It should not come as a surprise that when an inorder traversal   of a binary search tree is done, the nodes of the tree are visited in order!

In an inorder traversal the root of the tree is visited after the entire left subtree has been traversed and in a binary search tree everything in the left subtree is less than the root. Therefore, the root is visited only after all the keys less than the root have been visited.

Similarly, in an inorder traversal the root is visited before the right subtree is traversed and everything in the right subtree is greater than the root. Hence, the root is visited before all the keys greater than the root are visited. Therefore, by induction, the keys in the search tree are visited in order.

Inorder traversal is not defined for arbitrary N-ary trees--it is only defined for the case of N=2. Essentially this is because the nodes of N-ary trees contain only a single key. On the other hand, if a node of an M-way search tree has n subtrees, then it must contain n-1 keys, such that tex2html_wrap_inline64782. Therefore, we can define inorder traversal of an M-way tree  as follows:

To traverse a node of an M-way tree having n subtrees,

Traverse tex2html_wrap_inline63638; and then
visit tex2html_wrap_inline64392; and then
traverse tex2html_wrap_inline63404; and then
visit tex2html_wrap_inline64394; and then
traverse tex2html_wrap_inline63406; and then
tex2html_wrap_inline64802
2n-2.
visit tex2html_wrap_inline64396; and then
2n-1.
traverse tex2html_wrap_inline64388.


next up previous contents index

Bruno Copyright © 1997 by Bruno R. Preiss, P.Eng. All rights reserved.