// 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. // Two-three tree implementation for the Dictionary ADT template class TTTree : public Dictionary { private: TTNode* root; // Root of the tree int reccount; // Number of records stored // Private "helper" functions void clearhelp(TTNode*) // Helper functions { cout << "Clearhelp not yet defined\n"; } TTNode* inserthelp(TTNode*, const Key, const E); TTNode* add(TTNode*); E findhelp(TTNode*, Key) const; void printhelp(TTNode*, int) const; public: TTTree() { root = NULL; reccount = 0; } ~TTTree() { clearhelp(root); } void clear() { clearhelp(root); root = NULL; reccount = 0; } // Insert element "it" with Key "k" into the dictionary. void insert(const Key& k, const E& e) { root = inserthelp(root, k, e); reccount++; } E remove(const Key& k) { cout << "Remove not implemented\n"; return false; } // Remove and return the record with smallest key value // from the dictionary and return in "it". Return true if // some record is removed, false otherwise. E removeAny() { cout << "RemoveAny not implemented\n"; return false; } // Return a copy in "it" of 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 reccount; } void print() const { cout << "Print tree: \n"; if (root == NULL) cout << "The 2-3 Tree is empty.\n"; else printhelp(root, 0); } };