Richard Rasala
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.
- 1.Cline, Marshall P. and Lomow, Greg A., C++ FAQS: Frequently Asked Questions, Addison-Wesley, Reading, MA, 1995. Google Scholar
Digital Library
- 2.Coplien, James O., Advanced C++ Programming Styles and idioms, Addison-Wesley, Reading, MA, 1994. Google ScholarDigital Library
- 3.Eckel, Bruce, Thinking in C++, Prentice Hall, Englewood Cliffs, NJ, 1995. Google ScholarDigital Library
- 4.Ellis, Margaret A. and Stroustrup, Bjarne, The Annotated C++ Reference Manual, ANSI Base Document, Addison-Wesley, Reading, MA, 1990. Google ScholarDigital Library
- 5.Murray, Robert B., C++ Strategies and Tactics, Addison-Wesley, Reading, MA, 1993. Google ScholarDigital Library
- 6.Meyers, Scott, Effective C++: 50 Specific Ways to Improve Your Programs and Designs, Addison-Wesley, Reading, MA, 1992. Google ScholarDigital Library
- 7.Musser, David and Saini, Atul, STL Tutorial a~rl Reference Guide: C++ Programming with the Standard Template Library, Addison-Wesley, Reading, MAt 1996. Google ScholarDigital Library
- 8.Stroustrup, Bjarne, The C++ Programmh~g Language, 2nd Edition, Addison-Wesley, Reading, MA, 1991. Google ScholarDigital Library
- 9.Stroustrup, Bjarne, The Design and Evolution of 6'++, Addison-Wesley, Reading, MA, 1994. Google ScholarDigital Library
Index Terms
- A model C++ tree iterator class for binary search trees
Recommendations
A model C++ tree iterator class for binary search trees
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 ...
Path Length of Binary Search Trees
An algorithm is given for constructing a binary tree of minimum weighted path length and with restricted maximum path length. (Huffman’s tree is a binary tree of minimum weighted path length with no restriction on maximum path length.) When an ...
Self-adjusting binary search trees
The splay tree, a self-adjusting form of binary search tree, is developed and analyzed. The binary search tree is a data structure for representing tables and lists so that accessing, inserting, and deleting items is easy. On an n-node splay tree, all ...
Comments