BST.rar_BST树_BZP8_skillxod_thinecb_use7ck

#include<iostream> #include<fstream> #include<string> #include "math.h" using namespace std; class City { //friend ifstream& operator>>(ifstream& file, City& acity){file>>acity.x_coordinate; file>>acity.y_coordinate;return file;} friend ifstream& operator>>(basic_istream<char>& file, City& acity) { return (ifstream&)(file >> acity.x_coordinate >> acity.y_coordinate); } friend ostream& operator<<(ostream& os, City& acity) { return (ostream&)(os << " x = " << acity.x_coordinate << " y = " << acity.y_coordinate); } //friend ostream& operator<<(ostream& os, City& acity){ //os << " x = ";os << acity.x_coordinate;os<< " y = ";os << acity.y_coordinate;return os;} private: int x_coordinate; int y_coordinate; public: City() { x_coordinate = 0; y_coordinate = 0; } City(string name, int x, int y): x_coordinate(x), y_coordinate(y) {} City(const City& acity) { x_coordinate = acity.x_coordinate; y_coordinate = acity.y_coordinate; } virtual ~City() {}; bool operator==(const City& right) { return x_coordinate == right.y_coordinate; } bool operator!=(const City& right) { return !(x_coordinate == right.y_coordinate); } bool distanceWithin(int distance) { return sqrt(x_coordinate * x_coordinate + y_coordinate * y_coordinate) < distance; } int distanceQuared() { return x_coordinate * x_coordinate + y_coordinate * y_coordinate; } }; const City NULL_("NULL", -1, -1); template <typename Key, typename E> class Dictionary { private: void operator =(const Dictionary&) {} Dictionary(const Dictionary&) {} public: Dictionary() {} // Default constructor virtual ~Dictionary() {} // Base destructor // Reinitialize dictionary virtual void clear() = 0; // Insert a record // k: The key for the record being inserted. // e: The record being inserted. virtual void insert(const Key& k, const E& e) = 0; // Remove and return a record. // k: The key of the record to be removed. // Return: A maching record. If multiple records match // "k", remove an arbitrary one. Return NULL if no record // with key "k" exists. virtual E remove(const Key& k) = 0; // Remove and return an arbitrary record from dictionary. // Return: The record removed, or NULL if none exists. virtual E removeAny() = 0; // Return: A record matching "k" (NULL if none exists). // If multiple records match, return an arbitrary one. // k: The key of the record to find virtual E find(const Key& k) const = 0; // Return the number of records in the dictionary. virtual int size() = 0; }; template <typename E> class BinNode { public: virtual ~BinNode() {} // Base destructor // Return the node's value virtual E& element() = 0; // Set the node's value virtual void setElement(const E&) = 0; // Return the node's left child virtual BinNode* left() const = 0; // Set the node's left child virtual void setLeft(BinNode*) = 0; // Return the node's right child virtual BinNode* right() const = 0; // Set the node's right child virtual void setRight(BinNode*) = 0; // Return true if the node is a leaf, false otherwise virtual bool isLeaf() = 0; }; // Simple binary tree node implementation template <typename Key, typename E> class BSTNode : public BinNode<E> { friend ifstream& operator>>(ifstream& file, BSTNode& node) { file >> node.k; file >> node.it; return file; } friend ostream& operator<<(ostream& os, BSTNode& node) { return os << node.k << node.it; } private: Key k; // The node's key E it; // The node's value BSTNode* lc; // Pointer to left child BSTNode* rc; // Pointer to right child public: // Two constructors -- with and without initial values BSTNode() { lc = rc = NULL; } BSTNode(Key K, E e, BSTNode* l = NULL, BSTNode* r = NULL) { k = K; it = e; lc = l; rc = r; } ~BSTNode() {} // Destructor // Functions to set and return the value and key E& element() { return it; } void setElement(const E& e) { it = e; } Key& key() { return k; } void setKey(const Key& K) { k = K; } // Functions to set and return the children inline BSTNode* left() const { return lc; } void setLeft(BinNode<E>* b) { lc = (BSTNode*)b; } inline BSTNode* right() const { return rc; } void setRight(BinNode<E>* b) { rc = (BSTNode*)b; } // Return true if it is a leaf, false otherwise bool isLeaf() { return (lc == NULL) && (rc == NULL); } bool operator==(const BSTNode& right) { return *this == right; } bool operator!=(const BSTNode& right) { return (*this != right); } }; template <typename Key, typename E> class BST :public Dictionary<Key, E> { private: BSTNode<Key, E>* root; // Root of the BST int nodecount; // Number of nodes in the BST // Private "helper" functions void clearhelp(BSTNode<Key, E>*); BSTNode<Key, E>* inserthelp(BSTNode<Key, E>*, const Key&, const E&); BSTNode<Key, E>* deletemin(BSTNode<Key, E>*); BSTNode<Key, E>* getmin(BSTNode<Key, E>*); BSTNode<Key, E>* removehelp(BSTNode<Key, E>*, const Key&); E findhelp(BSTNode<Key, E>*, const Key&) const; void printhelp(BSTNode<Key, E