A model C++ tree iterator class for binary search trees

ABSTRACT

In object-oriented design, the concept of a container class that holds a collection of similar objects is fundamental. To use a container class most effectively, it is helpful to define one or more associated iterator classes that can return the objects in the container class in a specified order. An iterator is a bridge that permits the caller to use the objects in a container without knowledge of the details of how the objects are stored in the container. Although the concept of iterator is discussed in a number of books on C++ and/or object-oriented design, it is difficult to find a complete example that is both elegant and sophisticated. In this article, we provide such an example by developing an iterator class for binary search trees that is capable of doing all standard traversals: inorder, preorder, and postorder.

REFERENCES

• 1: Marshall P. Cline , Greg A. Lomow, C++ FAQs: Frequently Asked Questions, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1994
• 2: James O. Coplien, Advanced C++ programming styles and idioms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1991
• 3: Bruce Eckel, Thinking in C++, Prentice-Hall, Inc., Upper Saddle River, NJ, 1995
• 4: Margaret A. Ellis , Bjarne Stroustrup, The annotated C++ reference manual, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
• 5: Robert B. Murray, C++ strategies and tactics, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1993
• 6: Scott Meyers, Effective C++: 50 specific ways to improve your programs and designs, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1992
• 7: David R. Musser , Gilmer J. Derge , Atul Saini, STL tutorial and reference guide, second edition: C++ programming with the standard template library, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 2001
• 8: Bjarne Stroustrup, The C++ programming language (2nd ed.), Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1991
• 9: Bjarne Stroustrup, The design and evolution of C++, ACM Press/Addison-Wesley Publishing Co., New York, NY, 1995

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications

          Nouns: C++

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Graph and tree search strategies

  K. Computing Milieux
  K.3 COMPUTERS AND EDUCATION
      K.3.2 Computer and Information Science Education
          Subjects: Curriculum

General Terms:
Design, Human Factors, Languages, Management, Performance, Theory