// FILE: CityDb.cpp// CLASS IMPLEMENTED: city_db (see CityDb.h for documentation)// INVARIANT of the ADT:// ????//// Documentation for functions client don't have to know:// these are basically tree traversal functions that the city_db member// functions wrap around, so the user doesn't have to muck around with the// implementation details of the city_db object (they don't care that it's a// binary search tree, and they shouldn't need to pass pointers to the// functions, so the member functions take the input from the user and call// these helper functions with an extra argument: the root_ptr of the// city_db class' storage BST.)//// void bst_remove_max(binary_tree_node<city_record>*& root_ptr,// city_record& removed)// Precondition: root_ptr is a root pointer of a non-empty// binary search tree.// Postcondition: The city record with the largest city code// in the binary search tree has been removed, and root_ptr// now points to the root of the new (smaller) binary search// tree. The reference parameter, removed, has been set to a// copy of the removed city record.//// void bst_remove(binary_tree_node<city_record>*& root_ptr,// const city_record& target)// Precondition: root_ptr is a root pointer of a binary search// tree (or may be 0 for the empty tree)// Postcondition: If target was in the tree, then one copy of// target has been removed, and root_ptr now points to the// root of the new (smaller) binary search tree. Otherwise,// if target was not in the tree, then the tree is unchanged.////// void printCodeOrderRecur(binary_tree_node<city_record>* rootPtr)// Precondition: rootPtr is a root pointer of a binary search tree.// Postcondition: the tree is output to the screen in code order// (which is smallest-largest, as evidenced by the provided output,// input01.out, from the instructor.)//// void printCodeOrderRecur(int x,int y, int distance,// binary_tree_node<city_record>* rootPtr)// this is an overloaded version of the above function.// Precondition: rootPtr is a root pointer of a binary search tree.// Postcondition: all items in the binary search tree under rootPtr// that are within the given distance of the x and y parameters// are output to the screen, in the same format as the above function.// // binary_tree_node<city_record>* searchRecur(int CityCode,// binary_tree_node<city_record>* rootPtr)// Precondition: rootPtr is a root pointer of a binary search tree.// Postcondition: if CityCode is in the binary search tree specified by// rootPtr, a pointer to that node is returned. otherwise, a null pointer// is returned.// // binary_tree_node<city_record>* searchRecur(int x, int y,// binary_tree_node<city_record>* rootPtr)// Precondition: rootPtr is a root pointer of a binary search tree.// Postcondition: if a city_record with the given x,y coordinates// is in the binary search tree specified by rootPtr, a pointer to that// node is returned. otherwise, a null pointer is returned.//// void insertRecur(city_record cr,// binary_tree_node<city_record>* rootPtr) // Precondition: rootPtr is a pointer to a binary search tree with// at least one element.// Postcondition: the tree specified by rootPtr now has one more node,// and the storage rule of the BST is maintained. //// for other function documentation please refer to CityDB.h// include relevant header files here#include "CityDb.h"#include "BinTree.h"#include "CityRecord.h"#include <iostream>#include <cmath>namespace cs3358Spring2007Assign08{ // NONMEMBER FUNCTIONS void bst_remove_max(binary_tree_node<city_record>*& root_ptr, city_record& removed) { // we traverse the root_ptr, taking all rights until we find the // largest value. if (root_ptr == 0) return; binary_tree_node<city_record>* cursor = root_ptr; while (cursor->right() != 0 && cursor->right()->right() != 0) cursor = cursor->right(); // two cases: cursor -> right points to the node we need to remove, // or cursor -> right points to null. // If its right points to null, that means cursor is // still root_ptr. In that case, we just set root_ptr to be the // left subtree and remove the note that is cursor. // in the other case, we leave root the same, but we // delete cursor -> right and then set cursor -> right to the left // subtree of cursor -> right. if (cursor->right() == 0) { root_ptr = cursor->left();// will work for null lefts as well. removed = cursor->data(); delete cursor; } else { // cursor -> right is what we want to remove, and we know it's the max // value (so it may have left subtrees under it but it doesn't have // right subtrees.) binary_tree_node<city_record>* temp = cursor->right()->left(); removed = cursor->right()->data(); // we don't care if cursor -> right -> left is 0 or not. delete cursor->right(); cursor->set_right(temp); } } void bst_remove(binary_tree_node<city_record>*& root_ptr, const city_record& target) { if (root_ptr == 0) return; if (root_ptr->data() == target) { // we need to change root pointer here! binary_tree_node<city_record>* left = root_ptr->left(); city_record new_root = city_record(); bst_remove_max(left,new_root);// get rid of city code. if (left != 0)// I.E. it found something { root_ptr->set_left(left); root_ptr->set_data(new_root); } else { //there was no left subtree so root_ptr just gets to be... // the right subtree. //and we need to delete the current item, so we'll use left // to temporarily store that address (since we don't need the // value in left anymore) left = root_ptr; root_ptr = root_ptr->right(); delete left; } return; } else if (root_ptr->data() > target) bst_remove(root_ptr->left(), target); else bst_remove(root_ptr->right(), target); } void printCodeOrderRecur(binary_tree_node<city_record>* rootPtr) { if (rootPtr == 0) return; printCodeOrderRecur(rootPtr->left()); city_record cr = rootPtr->data(); std::cout << cr.get_code() << " (" << cr.get_x() << ", " << cr.get_y() << ")" << std::endl; printCodeOrderRecur(rootPtr->right()); } void printCodeOrderRecur(int x,int y, int distance, binary_tree_node<city_record>* rootPtr) { if (rootPtr == 0) return; city_record cr = rootPtr->data(); int x2 = cr.get_x(), y2 = cr.get_y(); float dist = sqrt(pow(float(x2 - x),2) + pow(float(y2 - y),2)); printCodeOrderRecur(x, y, distance, rootPtr->left()); if (dist <= distance) std::cout << cr.get_code() << " (" << cr.get_x() << ", " << cr.get_y() << ")" << std::endl; printCodeOrderRecur(x,y,distance, rootPtr->right()); } binary_tree_node<city_record>* searchRecur(int CityCode, binary_tree_node<city_record>* rootPtr) { if (rootPtr == 0) return 0; if (rootPtr->data().get_code() == CityCode) return rootPtr; binary_tree_node<city_record>* temp = searchRecur(CityCode, rootPtr->left()); if (temp != 0) return temp; temp = searchRecur(CityCode, rootPtr->right()); if (temp != 0) return temp; return 0; } binary_tree_node<city_record>* searchRecur(int x, int y, binary_tree_node<city_record>* rootPtr) { if (rootPtr == 0) return 0; if (rootPtr->data().get_x() == x && rootPtr->data().get_y() == y) return rootPtr; binary_tree_node<city_record>* temp = searchRecur(x,y, rootPtr->left()); if (temp != 0) return temp; temp = searchRecur(x,y, rootPtr->right()); if (temp != 0) return temp; return 0; } void insertRecur(city_record cr, binary_tree_node<city_record>* rootPtr) { assert(rootPtr != 0); //this should never happen. if (cr.get_code() <= rootPtr->data().get_code()) { if (rootPtr->left() == 0) { rootPtr->set_left(new binary_tree_node<city_record>(cr)); //rootPtr.left.data = cr; } else insertRecur(cr,rootPtr->left()); } else { if (rootPtr->right() == 0) { rootPtr->set_right(new binary_tree_node<city_record>(cr)); } else insertRecur(cr,rootPtr->right()); } } // Member Functions bool city_db::remove(int CityCode) { binary_tree_node<city_record>* result = searchRecur(CityCode,root_ptr); if (result != 0) // we found something to remove. { bst_remove(root_ptr,result->data()); return true; } return false; } bool city_db::remove(int x, int y) { binary_tree_node<city_record>* result = searchRecur(x, y, root_ptr); if (result != 0) // we found something to remove. { bst_remove(root_ptr,result->data()); return true; } return false; } void city_db::insert(city_record cr) { if (root_ptr == 0) // no items, we can do this insert ourselves. root_ptr = new binary_tree_node<city_record>(cr); else { // don't let them insert a non-unique city code. if (searchRecur(cr.get_code(), root_ptr)) return; insertRecur(cr,root_ptr); } } bool city_db::search(int CityCode, city_record& record) { binary_tree_node<city_record>* temp = searchRecur(CityCode,root_ptr); if(temp != 0) { record = temp->data(); return true; } else return false; } bool city_db::search(int x, int y, city_record& record) { binary_tree_node<city_record>* temp = searchRecur(x,y,root_ptr); if(temp != 0) { record = temp->data(); return true; } else return false; } bool city_db::empty() { return (root_ptr == 0); } void city_db::printTree() { print(root_ptr, 0); } void city_db::printCodeOrder() { printCodeOrderRecur(root_ptr); } void city_db::printCodeOrder(int x, int y, int dist) { printCodeOrderRecur(x,y,dist,root_ptr); }}