1: /**< @file bst2.cpp
2: Contains the (partial) implementation of a BinarySearchTree template class.
3: */
5: //These are the member functions in the class interface.
6: //Auxiliary helper functions are grouped below in the anonymous namespace.
7: //========================================================================
8: template<typename DataType>
9: BinarySearchTree<DataType>::BinarySearchTree()
10: {
11: rootPtr = nullptr;
12: }
15: template<typename DataType>
16: void BinarySearchTree<DataType>::insert
17: (
18: DataType data //in
19: )
20: {
21: //Call (recursive) helper function to perform the actual insertion.
22: InsertNode(rootPtr, data);
23: }
26: template<typename DataType>
27: void BinarySearchTree<DataType>::display
28: (
29: ostream& outStream //inout
30: ) const
31: {
32: if (rootPtr == nullptr)
33: cout << "\nThe tree is empty and there are no values to display.";
34: else
35: //Call (recursive) helper function to actually display the values.
36: DisplayTree(rootPtr, outStream);
37: }
40: //Anonymous namepace to contain and "isolate" the class helper functions.
41: namespace
42: {
44: template<typename DataType>
45: void InsertNode
46: (
47: TreeNode<DataType>*& treePtr, //inout
48: DataType data //in
49: )
50: /**<
51: Add a new value to the BST.
52: @param treePtr A pointer to the BST to receive the value.
53: @param data The value to be inserted into the BST.
54: @pre treePtr and data have been initialized.
55: @post data is now in the BST and the BST property has been maintained.
56: */
57: {
58: if (treePtr == nullptr) //then we have found the place to insert, so ...
59: {
60: if (tracingOn)
61: {
62: cout << "Now inserting node containing " << data << ".\n";
63: Pause();
64: }
65: treePtr = new TreeNode<DataType>;
66: treePtr->rightPtr = nullptr;
67: treePtr->leftPtr = nullptr;
68: treePtr->data = data;
69: }
70: else if (data < treePtr->data)
71: {
72: if (tracingOn)
73: {
74: cout << "Now going left at node containing "
75: << treePtr->data << ".\n";
76: Pause();
77: }
78: //Inserting into left subtree.
79: InsertNode(treePtr->leftPtr, data);
80: }
81: else
82: {
83: if (tracingOn)
84: {
85: cout << "Now going right at node containing "
86: << treePtr->data << ".\n";
87: Pause();
88: }
89: //Inserting into right subtree.
90: InsertNode(treePtr->rightPtr, data);
91: }
92: }
95: template<typename DataType>
96: void DisplayTree
97: (
98: TreeNode<DataType>* treePtr, //in
99: ostream& outStream //inout
100: )
101: /**<
102: Display all values in a BST on a specified output stream.
103: @param treePtr A pointer to the root of a tree to be displayed.
104: @param outStream The destination stream for display of the tree values.
105: @pre treePtr has been initialized and outStream is open. Also, operator<<
106: is overloaded for DataType.
107: @post All data values in the tree have been displayed on outStream in
108: ascending order, with adjacent values separated by a blank space, and
109: outStream is still open.
110: */
111: {
112: if (treePtr != nullptr)
113: {
114: //Display left subtree ...
115: DisplayTree(treePtr->leftPtr, outStream);
116: //Display current node value, then a space ...
117: outStream << treePtr->data << " ";
118: //Display right subtree ...
119: DisplayTree(treePtr->rightPtr, outStream);
120: }
121: }
123: } //End of anonymous namespace