Now that you ve learned the pieces of the BinarySearchTree class, let s assemble them into a working application. You ll organize the application into three files, BinaryTreeDemo.cpp , BinarySearchTree.h , and BinarySearchTree.cpp . BinaryTreeDemo.cpp is the application file that contains the code that creates and manipulates the tree. BinarySearchTree.h contains the definition of the structure used to build a node and the definition of the BinarySearchTree class. BinarySearchTree.cpp contains the definition of member functions of the BinarySearchTree class. All these files are listed in the next code snippet.
Previously in this chapter, we discussed the structure used to create a node and the BinarySearchTree class definition. In addition, each member function was discussed in the preceding section of this chapter.
All that remains is for you to take a close look at how the application creates and manipulates a tree. To do this, you ll explore the BinaryTreeDemo application, which creates a tree and stores two nodes: IDs (keys) and first names (values). It then manipulates these nodes. Here is the application:
//BinaryTreeDemo.cpp #include <iostream.h> #include <time.h> #include <stdlib.h> #include <string.h> #include <stdio.h> #include "BinarySearchTree.h" void main() { BinarySearchTree* tree = new BinarySearchTree(); char key[SIZE_KEY]; char value[SIZE_VALUE]; int i; cout << "Adding three keys and values into the tree." << endl; for(i=0; i<3; i++) { if (i==0) { strcpy(key,"345"); strcpy(value,"Bob"); } if (i==1) { strcpy(key,"123"); strcpy(value,"Mary"); } if (i==2) { strcpy(key,"999"); strcpy(value,"Sue"); } if (!tree->contains(key)) { cout << "Adding node - key: " << key << " value: " << value << endl; tree->add(key, value); } else { cout << "Generated duplicate key: " << key << endl; } } cout << "\nIn order traversal of tree:" << endl; tree->displayInOrder(); cout << "\nDepth of tree before removing nodes: " << tree->getDepth() << endl; cout << "Size of tree before removing nodes: " << tree->getSize() << endl; cout << "\nRetrieving one value from the tree:" << endl; if(tree->get("123", value)) { cout << " Value: " << value << endl; } cout << "\nRemoving one node from the tree:" << endl; if(tree->contains("123")) { tree->remove("123"); } cout << "\nIn order traversal of tree:" << endl; tree->displayInOrder(); cout << "\nDepth of tree after removing nodes: " << tree->getDepth() << endl; cout << "Size of tree after removing nodes: " << tree->getSize() << endl; cout << "\nDestroying the tree:" << endl; delete tree; }
The application begins by declaring an instance of the BinarySearchTree class and assigns it to a reference called tree . Next, two char arrays are declared and an int is declared. The char arrays are called key and value , and the size of these arrays is established by using the macro defined in the BinarySearchTree.h file. The arrays store an ID and a first name that is assigned to a node on the tree. The int controls the for loop.
The for loop then adds each ID and first name to the tree. For each iteration, the strcpy() function is called to copy a string that contains either an ID or a first name to the key and value array. You use an if statement to determine which set of ID and first name to copy to the arrays.
Once the set of strings is copied to the arrays, the application calls the contains() member function to determine if the key already exists in the tree. Remember that each key must be unique. The contains() function returns a Boolean true if the key is contained in the tree. You reverse the logic with the not operator so that a Boolean true is treated as a Boolean false . This means that statements within the if statement will not execute if the key already exists in the tree.
If the key doesn t exist, then the application displays the key and value on the screen before calling the add() member function to place the key and value on the tree, as shown here:
Adding three keys and values into the tree. Adding node - key: 345 value: Bob Adding node - key: 123 value: Mary Adding node - key: 999 value: Sue
Figure 10-6 illustrates keys and values organized on the tree.
If the key does exist, then a message is displayed on the screen telling everyone that the key is a duplicate key.
After all three IDs and first names are placed on the tree, the application manipulates nodes on the tree. The first manipulation is to call the displayInOrder() member function that displays keys and values of each node, as shown next:
In order traversal of tree: key: 123 value: Mary key: 345 value: Bob key: 999 value: Sue
Next, the application displays the depth and the size of the tree by calling the getDepth() and getSize() member functions. The result is displayed on the screen, as shown here:
Depth of tree before removing nodes 2 Size of tree before removing nodes 3
Remember that the depth of a tree is the number of levels on the tree. In this example, there are two levels. The first level contains the root node, and the second level contains the left child node and the right child node.
Next, the application retrieves the value associated with key 123 by calling the get() member function. The get() member function returns a Boolean value true if the key is found; otherwise , a Boolean false is returned. If the key is found, then the value is displayed on the screen, as shown here. Remember that the first name associated with the key 123 is assigned to the value array by the get() function.
Retrieving one value from the tree: Value Mary
Next, the application removes the node that contains the key 123. First, the contains() function is called to determine if the tree contains a key that has the value 123. If so, a Boolean true is returned; otherwise, a Boolean false is returned. Because there is a node containing 123 as a key, the remove() member function is called and passed the string 123 to remove the node.
The displayInOrder() function is called once again to display the tree after the node is removed. Here s what is displayed on the screen. Notice that the node containing 123 no longer exists in the tree (see Figure 10-7).
Removing one node from the tree: In order traversal of tree: key: 345 value: Bob key: 999 value: Sue
Finally, the application calls the getDepth() and getSize() functions to display the depth and size of the tree after the node is removed. Here s what is displayed:
Depth of tree after removing nodes 2 Size of tree after removing nodes 2
The application finishes removing the tree by calling the delete operator. Remember that the destructor of the BinarySearchTree class calls the removeAllNodes() member function that displays keys and values of nodes that are removed. Here s what is displayed:
Removing node - key: 345 Bob Removing node - key: 999 Sue // BinarySearchTree.h" #include <string.h> #define SIZE_KEY 32 #define SIZE_VALUE 256 typedef struct Metadata { struct Metadata(char* key, char* value) { strcpy(this->key, key); strcpy(this->value, value); left = NULL; right = NULL; } char key[SIZE_KEY]; char value[SIZE_VALUE]; struct Metadata* left; struct Metadata* right; } METADATA; class BinarySearchTree { private: int size; METADATA* root; bool addNode(METADATA** current_node, METADATA* new_node); bool getNode(METADATA* current_node, char* key, char* value); void removeAllNodes(METADATA* node); void processNodesInOrder(METADATA* node); int getTreeDepth(METADATA* node); bool containsNode(METADATA* node, char* key); bool removeNode(METADATA** node, char* key); void removeRootNode(METADATA** node); void moveLeftMostNode(METADATA** node, METADATA* root); public: BinarySearchTree(); virtual ~BinarySearchTree(); bool add(char* key, char* value); bool remove(char* key); void removeAll(); bool get(char* key, char* value); bool contains(char* key); void displayInOrder(); int getSize(); int getDepth(); }; // BinarySearchTree.cpp #include <iostream.h> #include "BinarySearchTree.h" BinarySearchTree::BinarySearchTree() { root = NULL; size = 0; } BinarySearchTree::~BinarySearchTree() { removeAll(); } bool BinarySearchTree::add(char* key, char* value) { if(key == NULL value == NULL strlen(key) > SIZE_KEY-1 strlen(value) > SIZE_VALUE-1) { return false; } METADATA* new_node = new METADATA(key, value); return addNode(&root, new_node); } bool BinarySearchTree::addNode(METADATA** current_node, METADATA* new_node) { if(*current_node == NULL) { *current_node = new_node; size++; return true; } else { if(strcmp(new_node->key, (*current_node)->key) < 0) { return addNode(&((*current_node)->left), new_node); } else if(strcmp(new_node->key, (*current_node)->key) > 0) { return addNode(&((*current_node)->right), new_node); } else { delete new_node; return false; } } } bool BinarySearchTree::remove(char* key) { return removeNode(&root, key); } function bool BinarySearchTree::removeNode(METADATA** node, char* key) { if(*node != NULL) { if (strcmp(key, (*node)->key) == 0) { removeRootNode(node); size--; return true; } else if(strcmp(key, (*node)->key) < 0) { return removeNode(&((*node)->left), key); } else { return removeNode(&((*node)->right), key); } } else { return false; } } void BinarySearchTree::removeRootNode(METADATA** root) { METADATA* temp; if((*root)->left == NULL && (*root)->right == NULL) { delete(*root); *root = NULL; } else if((*root)->right == NULL) { temp = *root; *root = (*root)->left; delete(temp); } else if((*root)->left == NULL) { temp = *root; *root = (*root)->right; delete(temp); } else { moveLeftMostNode(&((*root)->right), *root); } } void BinarySearchTree::moveLeftMostNode(METADATA** node, METADATA* root) { if(*node != NULL && (*node)->left == NULL) { METADATA* temp = *node; strcpy(root->key, (*node)->key); strcpy(root->value, (*node)->value); *node = (*node)->right; delete(temp); } else { moveLeftMostNode(&((*node)->left), root); } } void BinarySearchTree::removeAll() { removeAllNodes(root); root = NULL; size = 0; } void BinarySearchTree::removeAllNodes(METADATA* node) { if(node != NULL) { removeAllNodes(node->left); removeAllNodes(node->right); cout << "Removing node - key: " << node->key << "\t" << node->value << endl; delete node; } } bool BinarySearchTree::get(char* key, char* value) { return getNode(root, key, value); } bool BinarySearchTree::getNode(METADATA* node, char* key, char* value) { if(node == NULL) { value[0] = 'Removing node - key: 345 Bob Removing node - key: 999 Sue // BinarySearchTree.h" #include <string.h> #define SIZE_KEY ‚32 #define SIZE_VALUE 256 typedef struct Metadata { struct Metadata(char* key, char* value) { strcpy(this->key, key); strcpy(this->value, value); left = NULL; right = NULL; } char key[SIZE_KEY]; char value[SIZE_VALUE]; struct Metadata* left; struct Metadata* right; } METADATA; class BinarySearchTree { private: int size; METADATA* root; bool addNode(METADATA** current_node, METADATA* new_node); bool getNode(METADATA* current_node, char* key, char* value); void removeAllNodes(METADATA* node); void processNodesInOrder(METADATA* node); int getTreeDepth(METADATA* node); bool containsNode(METADATA* node, char* key); bool removeNode(METADATA** node, char* key); void removeRootNode(METADATA** node); void moveLeftMostNode(METADATA** node, METADATA* root); public: BinarySearchTree(); virtual ~BinarySearchTree(); bool add(char* key, char* value); bool remove(char* key); void removeAll(); bool get(char* key, char* value); bool contains(char* key); void displayInOrder(); int getSize(); int getDepth(); }; // BinarySearchTree.cpp #include <iostream.h> #include "BinarySearchTree.h" BinarySearchTree::BinarySearchTree() { root = NULL; size = 0; } BinarySearchTree::~BinarySearchTree() { removeAll(); } bool BinarySearchTree::add(char* key, char* value) { if(key == NULL value == NULL strlen(key) > SIZE_KEY-1 strlen(value) > SIZE_VALUE-1) { return false; } METADATA* new_node = new METADATA(key, value); return addNode(&root, new_node); } bool BinarySearchTree::addNode(METADATA** current_node, METADATA* new_node) { if(*current_node == NULL) { *current_node = new_node; size++; return true; } else { if(strcmp(new_node->key, (*current_node)->key) < 0) { return addNode(&((*current_node)->left), new_node); } else if(strcmp(new_node->key, (*current_node)->key) > 0) { return addNode(&((*current_node)->right), new_node); } else { delete new_node; return false; } } } bool BinarySearchTree::remove(char* key) { return removeNode(&root, key); } function bool BinarySearchTree::removeNode(METADATA** node, char* key) { if(*node != NULL) { if (strcmp(key, (*node)->key) == 0) { removeRootNode(node); size--; return true; } else if(strcmp(key, (*node)->key) < 0) { return removeNode(&((*node)->left), key); } else { return removeNode(&((*node)->right), key); } } else { return false; } } void BinarySearchTree::removeRootNode(METADATA** root) { METADATA* temp; if((*root)->left == NULL && (*root)->right == NULL) { delete(*root); *root = NULL; } else if((*root)->right == NULL) { temp = *root; *root = (*root)->left; delete(temp); } else if((*root)->left == NULL) { temp = *root; *root = (*root)->right; delete(temp); } else { moveLeftMostNode(&((*root)->right), *root); } } void BinarySearchTree::moveLeftMostNode(METADATA** node, METADATA* root) { if(*node != NULL && (*node)->left == NULL) { METADATA* temp = *node; strcpy(root->key, (*node)->key); strcpy(root->value, (*node)->value); *node = (*node)->right; delete(temp); } else { moveLeftMostNode(&((*node)->left), root); } } void BinarySearchTree::removeAll() { removeAllNodes(root); root = NULL; size = 0; } void BinarySearchTree::removeAllNodes(METADATA* node) { if(node != NULL) { removeAllNodes(node->left); removeAllNodes(node->right); cout << "Removing node - key: " << node->key << "\t" << node->value << endl; delete node; } } bool BinarySearchTree::get(char* key, char* value) { return getNode(root, key, value); } bool BinarySearchTree::getNode(METADATA* node, char* key, char* value) { if(node == NULL) { value[0] = '\0'; return false; } else { if(strcmp(key, node->key) == 0) { strcpy(value, node->value); return true; } else if(strcmp(key, node->key) < 0) { return getNode(node->left, key, value); } else { return getNode(node->right, key, value); } } } bool BinarySearchTree::contains(char* key) { return containsNode(root, key); } bool BinarySearchTree::containsNode(METADATA* node, char* key) { if(node == NULL) { return false; } else { if(strcmp(key, node->key) == 0) { return true; } else if(strcmp(key, node->key) < 0) { return containsNode(node->left, key); } else { return containsNode(node->right, key); } } } void BinarySearchTree::displayInOrder() { processNodesInOrder(root); } void BinarySearchTree::processNodesInOrder(METADATA* node) { if(node != NULL) { processNodesInOrder(node->left); cout << "key: " << node->key << "\tvalue: " << node->value << endl; processNodesInOrder(node->right); } } int BinarySearchTree::getSize() { return size; } int BinarySearchTree::getDepth() { return getTreeDepth(root); } int BinarySearchTree::getTreeDepth(METADATA* node) { int depth_left; int depth_right; if(node == NULL) { return 0; } else { depth_left = getTreeDepth(node->left); depth_right = getTreeDepth(node->right); if(depth_left > depth_right) { return depth_left + 1; } else { return depth_right + 1; } } }'; return false; } else { if(strcmp(key, node->key) == 0) { strcpy(value, node->value); return true; } else if(strcmp(key, node->key) < 0) { return getNode(node->left, key, value); } else { return getNode(node->right, key, value); } } } bool BinarySearchTree::contains(char* key) { return containsNode(root, key); } bool BinarySearchTree::containsNode(METADATA* node, char* key) { if(node == NULL) { return false; } else { if(strcmp(key, node->key) == 0) { return true; } else if(strcmp(key, node->key) < 0) { return containsNode(node->left, key); } else { return containsNode(node->right, key); } } } void BinarySearchTree::displayInOrder() { processNodesInOrder(root); } void BinarySearchTree::processNodesInOrder(METADATA* node) { if(node != NULL) { processNodesInOrder(node->left); cout << "key: " << node->key << "\tvalue: " << node->value << endl; processNodesInOrder(node->right); } } int BinarySearchTree::getSize() { return size; } int BinarySearchTree::getDepth() { return getTreeDepth(root); } int BinarySearchTree::getTreeDepth(METADATA* node) { int depth_left; int depth_right; if(node == NULL) { return 0; } else { depth_left = getTreeDepth(node->left); depth_right = getTreeDepth(node->right); if(depth_left > depth_right) { return depth_left + 1; } else { return depth_right + 1; } } }