// From the software distribution accompanying the textbook // "A Practical Introduction to Data Structures and Algorithm Analysis, // Third Edition (C++)" by Clifford A. Shaffer. // Source code Copyright (C) 2007-2011 by Clifford A. Shaffer. // This file includes all of the pieces of the BST implementation // Include the node implementation #include "BSTNode.h" // Include the dictionary ADT #include "dictionary.h" // Binary Search Tree implementation for the Dictionary ADT template class BST : public Dictionary { private: BSTNode* root; // Root of the BST int nodecount; // Number of nodes in the BST // Private "helper" functions void clearhelp(BSTNode*); BSTNode* inserthelp(BSTNode*, const Key&, const E&); BSTNode* deletemin(BSTNode*); BSTNode* getmin(BSTNode*); BSTNode* removehelp(BSTNode*, const Key&); E findhelp(BSTNode*, const Key&) const; void printhelp(BSTNode*, int) const; public: BST() { root = NULL; nodecount = 0; } // Constructor ~BST() { clearhelp(root); } // Destructor void clear() // Reinitialize tree { clearhelp(root); root = NULL; nodecount = 0; } // Insert a record into the tree. // k Key value of the record. // e The record to insert. void insert(const Key& k, const E& e) { root = inserthelp(root, k, e); nodecount++; } // Remove a record from the tree. // k Key value of record to remove. // Return: The record removed, or NULL if there is none. E remove(const Key& k) { E temp = findhelp(root, k); // First find it if (temp != NULL) { root = removehelp(root, k); nodecount--; } return temp; } // Remove and return the root node from the dictionary. // Return: The record removed, null if tree is empty. E removeAny() { // Delete min value if (root != NULL) { E temp = root->element(); root = removehelp(root, root->key()); nodecount--; return temp; } else return NULL; } // Return Record with key value k, NULL if none exist. // k: The key value to find. */ // Return some record matching "k". // Return true if such exists, false otherwise. If // multiple records match "k", return an arbitrary one. E find(const Key& k) const { return findhelp(root, k); } // Return the number of records in the dictionary. int size() { return nodecount; } void print() const { // Print the contents of the BST if (root == NULL) cout << "The BST is empty.\n"; else printhelp(root, 0); } }; // Clean up BST by releasing space back free store template void BST:: clearhelp(BSTNode* root) { if (root == NULL) return; clearhelp(root->left()); clearhelp(root->right()); delete root; } // Insert a node into the BST, returning the updated tree template BSTNode* BST::inserthelp( BSTNode* root, const Key& k, const E& it) { if (root == NULL) // Empty tree: create node return new BSTNode(k, it, NULL, NULL); if (k < root->key()) root->setLeft(inserthelp(root->left(), k, it)); else root->setRight(inserthelp(root->right(), k, it)); return root; // Return tree with node inserted } // Delete the minimum value from the BST, returning the revised BST template BSTNode* BST:: getmin(BSTNode* rt) { if (rt->left() == NULL) return rt; else return getmin(rt->left()); } template BSTNode* BST:: deletemin(BSTNode* rt) { if (rt->left() == NULL) // Found min return rt->right(); else { // Continue left rt->setLeft(deletemin(rt->left())); return rt; } } // Remove a node with key value k // Return: The tree with the node removed template BSTNode* BST:: removehelp(BSTNode* rt, const Key& k) { if (rt == NULL) return NULL; // k is not in tree else if (k < rt->key()) rt->setLeft(removehelp(rt->left(), k)); else if (k > rt->key()) rt->setRight(removehelp(rt->right(), k)); else { // Found: remove it BSTNode* temp = rt; if (rt->left() == NULL) { // Only a right child rt = rt->right(); // so point to right delete temp; } else if (rt->right() == NULL) { // Only a left child rt = rt->left(); // so point to left delete temp; } else { // Both children are non-empty BSTNode* temp = getmin(rt->right()); rt->setElement(temp->element()); rt->setKey(temp->key()); rt->setRight(deletemin(rt->right())); delete temp; } } return rt; } // Find a node with the given key value template E BST::findhelp(BSTNode* root, const Key& k) const { if (root == NULL) return NULL; // Empty tree if (k < root->key()) return findhelp(root->left(), k); // Check left else if (k > root->key()) return findhelp(root->right(), k); // Check right else return root->element(); // Found it } // Print out a BST template void BST:: printhelp(BSTNode* root, int level) const { if (root == NULL) return; // Empty tree printhelp(root->left(), level+1); // Do left subtree for (int i=0; ikey() << "\n"; // Print node value printhelp(root->right(), level+1); // Do right subtree }