class BinarySearchTree
1: /** @file bst2.h
2: Contains the (partial) specification of a BinarySearchTree template class.
3: */
5: #ifndef BST2_H
6: #define BST2_H
8: template<typename DataType>
9: struct TreeNode
10: {
11: TreeNode* leftPtr;
12: DataType data;
13: TreeNode* rightPtr;
14: };
15: /**<
16: The underlying node type for storing nodes of a binary search tree.
17: We assume that DataType is a type for which both operator< and
18: operator== are defined (either an appropriate built-in type, or
19: a class that overloads these operators).
20: */
23: template<typename DataType>
24: class BinarySearchTree
25: {
26: public:
27: BinarySearchTree();
28: /**<
29: The default constructor. Creates an empty BST.
30: */
32: void insert
33: (
34: DataType data //in
35: );
36: /**<
37: Insert a new value into the BST.
38: @param data The value to be inserted into the BST.
39: @pre data has been initialized.
40: @post data has been inserted into the BST, and the BST property
41: has been maintained.
42: */
44: void display
45: (
46: ostream& outStream //inout
47: ) const;
48: /**<
49: Display all data values from the BST in ascending order.
50: @param outStream The stream on which the values will appear.
51: @pre outStream is open.
52: @post All values from the BST have been displayed on outStream,
53: with adjacent values separated by a blank space, and outStream
54: is still open.
55: */
57: private:
58: TreeNode<DataType>* rootPtr;
59: };
61: #endif