//binaryTree.h //Header File Binary Search Tree #ifndef H_binaryTree #define H_binaryTree #include #include"orderedLinkedList.h" using namespace std; //Definition of the Node template struct nodeType { elemType info; nodeType *lLink; nodeType *rLink; }; //Definition of the class template class binaryTreeType { public: const binaryTreeType& operator= (const binaryTreeType&); //Overload the assignment operator. bool isEmpty() const; void inorderTraversal() const; void preorderTraversal() const; void postorderTraversal() const; int treeHeight() const; int treeNodeCount() const; int treeLeavesCount() const; void destroyTree(); virtual bool search(const elemType& searchItem) const = 0; virtual void insert(const elemType& insertItem) = 0; virtual void deleteNode(const elemType& deleteItem) = 0; binaryTreeType(const binaryTreeType& otherTree); //Copy constructor binaryTreeType(); //Default constructor ~binaryTreeType(); //Destructor protected: nodeType *root; private: void copyTree(nodeType* &copiedTreeRoot, nodeType* otherTreeRoot); void destroy(nodeType* &p); void inorder(nodeType *p) const; void preorder(nodeType *p) const; void postorder(nodeType *p) const; int height(nodeType *p) const; int max(int x, int y) const; int nodeCount(nodeType *p) const; int leavesCount(nodeType *p) const; }; //Definition of member functions template binaryTreeType::binaryTreeType() { root = nullptr; } template bool binaryTreeType::isEmpty() const { return (root == nullptr); } template void binaryTreeType::inorderTraversal() const { inorder(root); } template void binaryTreeType::preorderTraversal() const { preorder(root); } template void binaryTreeType::postorderTraversal() const { postorder(root); } template int binaryTreeType::treeHeight() const { return height(root); } template int binaryTreeType::treeNodeCount() const { return nodeCount(root); } template int binaryTreeType::treeLeavesCount() const { return leavesCount(root); } template void binaryTreeType::copyTree (nodeType* &copiedTreeRoot, nodeType* otherTreeRoot) { if (otherTreeRoot == nullptr) copiedTreeRoot = nullptr; else { copiedTreeRoot = new nodeType; copiedTreeRoot->info = otherTreeRoot->info; copyTree(copiedTreeRoot->lLink, otherTreeRoot->lLink); copyTree(copiedTreeRoot->rLink, otherTreeRoot->rLink); } } //end copyTree template void binaryTreeType::inorder (nodeType *p) const { if (p != nullptr) { inorder(p->lLink); cout << p->info << " "; inorder(p->rLink); } } template void binaryTreeType::preorder (nodeType *p) const { if (p != nullptr) { cout << p->info << " "; preorder(p->lLink); preorder(p->rLink); } } template void binaryTreeType::postorder (nodeType *p) const { if (p != nullptr) { postorder(p->lLink); postorder(p->rLink); cout << p->info << " "; } } //Overload the assignment operator template const binaryTreeType& binaryTreeType:: operator=(const binaryTreeType& otherTree) { if (this != &otherTree) //avoid self-copy { if (root != nullptr) //if the binary tree is not empty, //destroy the binary tree destroy(root); if (otherTree.root == nullptr) //otherTree is empty root = nullptr; else copyTree(root, otherTree.root); }//end else return *this; } template void binaryTreeType::destroy(nodeType* &p) { if (p != nullptr) { destroy(p->lLink); destroy(p->rLink); delete p; p = nullptr; } } template void binaryTreeType::destroyTree() { destroy(root); } //copy constructor template binaryTreeType::binaryTreeType (const binaryTreeType& otherTree) { if (otherTree.root == nullptr) //otherTree is empty root = nullptr; else copyTree(root, otherTree.root); } //Destructor template binaryTreeType::~binaryTreeType() { destroy(root); } template int binaryTreeType::height (nodeType *p) const { if (p == nullptr) return 0; else return 1 + max(height(p->lLink), height(p->rLink)); } template int binaryTreeType::max(int x, int y) const { if (x >= y) return x; else return y; } template int binaryTreeType::nodeCount(nodeType *p) const { cout << "Write the definition of the function nodeCount." << endl; return 0; } template int binaryTreeType::leavesCount(nodeType *p) const { cout << "Write the definition of the function leavesCount." << endl; return 0; } #endif //bindarySearchTree.h //Header File Binary Search Tree #ifndef H_binarySearchTree #define H_binarySearchTree #include #include "binaryTree.h" #include"orderedLinkedList.h" using namespace std; template class bSearchTreeType : public binaryTreeType { public: bool search(const elemType& searchItem) const; void insert(const elemType& insertItem); void deleteNode(const elemType& deleteItem); private: void deleteFromTree(nodeType* &p); }; template bool bSearchTreeType::search (const elemType& searchItem) const { nodeType *current; bool found = false; if (root == nullptr) cout << "Cannot search an empty tree." << endl; else { current = root; while (current != nullptr && !found) { if (current->info == searchItem) found = true; else if (current->info > searchItem) current = current->lLink; else current = current->rLink; }//end while }//end else return found; }//end search template void bSearchTreeType::insert (const elemType& insertItem) { nodeType *current; //pointer to traverse the tree nodeType *trailCurrent; //pointer behind current nodeType *newNode; //pointer to create the node newNode = new nodeType; newNode->info = insertItem; newNode->lLink = nullptr; newNode->rLink = nullptr; if (root == nullptr) root = newNode; else { current = root; while (current != nullptr) { trailCurrent = current; if (current->info == insertItem) { cout << "The item to be inserted is already "; cout << "in the tree -- duplicates are not " << "allowed." << endl; return; } else if (current->info > insertItem) current = current->lLink; else current = current->rLink; }//end while if (trailCurrent->info > insertItem) trailCurrent->lLink = newNode; else trailCurrent->rLink = newNode; } }//end insert template void bSearchTreeType::deleteNode (const elemType& deleteItem) { nodeType *current; //pointer to traverse the tree nodeType *trailCurrent; //pointer behind current bool found = false; if (root == nullptr) cout << "Cannot delete from an empty tree." << endl; else { current = root; trailCurrent = root; while (current != nullptr && !found) { if (current->info == deleteItem) found = true; else { trailCurrent = current; if (current->info > deleteItem) current = current->lLink; else current = current->rLink; } }//end while if (current == nullptr) cout << "The item to be deleted is not in the tree." << endl; else if (found) { if (current == root) deleteFromTree(root); else if (trailCurrent->info > deleteItem) deleteFromTree(trailCurrent->lLink); else deleteFromTree(trailCurrent->rLink); } else cout << "The item to be deleted is not in the tree." << endl; } } //end deleteNode template void bSearchTreeType::deleteFromTree (nodeType* &p) { nodeType *current; //pointer to traverse the tree nodeType *trailCurrent; //pointer behind current nodeType *temp; //pointer to delete the node if (p == nullptr) cout << "Error: The node to be deleted does not exist." << endl; else if (p->lLink == nullptr && p->rLink == nullptr) { temp = p; p = nullptr; delete temp; } else if (p->lLink == nullptr) { temp = p; p = temp->rLink; delete temp; } else if (p->rLink == nullptr) { temp = p; p = temp->lLink; delete temp; } else { current = p->lLink; trailCurrent = nullptr; while (current->rLink != nullptr) { trailCurrent = current; current = current->rLink; }//end while p->info = current->info; if (trailCurrent == nullptr) //current did not move; //current == p->lLink; adjust p p->lLink = current->lLink; else trailCurrent->rLink = current->lLink; delete current; }//end else } //end deleteFromTree #endif //linkedList.h #ifndef H_LinkedListType #define H_LinkedListType #include #include using namespace std; //Definition of the node template struct nodeType { Type info; nodeType *link; }; template class linkedListIterator { public: linkedListIterator(); linkedListIterator(nodeType *ptr); Type operator*(); linkedListIterator operator++(); bool operator==(const linkedListIterator& right) const; bool operator!=(const linkedListIterator& right) const; private: nodeType *current; //pointer to point to the current //node in the linked list }; template linkedListIterator::linkedListIterator() { current = nullptr; } template linkedListIterator:: linkedListIterator(nodeType *ptr) { current = ptr; } template Type linkedListIterator::operator*() { return current->info; } template linkedListIterator linkedListIterator::operator++() { current = current->link; return *this; } template bool linkedListIterator::operator== (const linkedListIterator& right) const { return (current == right.current); } template bool linkedListIterator::operator!= (const linkedListIterator& right) const { return (current != right.current); } //***************** class linkedListType **************** template class linkedListType { public: const linkedListType& operator= (const linkedListType&); //Overload the assignment operator. void initializeList(); bool isEmptyList() const; void print() const; int length() const; void destroyList(); Type front() const; Type back() const; virtual bool search(const Type& searchItem) const = 0; virtual void insertFirst(const Type& newItem) = 0; virtual void insertLast(const Type& newItem) = 0; virtual void deleteNode(const Type& deleteItem) = 0; linkedListIterator begin(); linkedListIterator end(); linkedListType(); linkedListType(const linkedListType& otherList); ~linkedListType(); protected: int count; //variable to store the number of //elements in the list nodeType *first; //pointer to the first node of the list nodeType *last; //pointer to the last node of the list private: void copyList(const linkedListType& otherList); assigned to this list. }; template bool linkedListType::isEmptyList() const { return(first == nullptr); } template linkedListType::linkedListType() //default constructor { first = nullptr; last = nullptr; count = 0; } template void linkedListType::destroyList() { nodeType *temp; //pointer to deallocate the memory //occupied by the node while (first != nullptr) //while there are nodes in the list { temp = first; //set temp to the current node first = first->link; //advance first to the next node delete temp; //deallocate the memory occupied by temp } last = nullptr; //initialize last to nullptr; first has already //been set to nullptr by the while loop count = 0; } template void linkedListType::initializeList() { destroyList(); //if the list has any nodes, delete them } template void linkedListType::print() const { nodeType *current; //pointer to traverse the list current = first; //set current so that it points to //the first node while (current != nullptr) //while more data to print { cout << current->info << " "; current = current->link; } }//end print template int linkedListType::length() const { return count; } //end length template Type linkedListType::front() const { assert(first != nullptr); return first->info; //return the info of the first node }//end front template Type linkedListType::back() const { assert(last != nullptr); return last->info; //return the info of the last node }//end back template linkedListIterator linkedListType::begin() { linkedListIterator temp(first); return temp; } template linkedListIterator linkedListType::end() { linkedListIterator temp(nullptr); return temp; } template void linkedListType::copyList (const linkedListType& otherList) { nodeType *newNode; //pointer to create a node nodeType *current; //pointer to traverse the list if (first != nullptr) //if the list is nonempty, make it empty destroyList(); if (otherList.first == nullptr) //otherList is empty { first = nullptr; last = nullptr; count = 0; } else { current = otherList.first; //current points to the //list to be copied count = otherList.count; //copy the first node first = new nodeType; //create the node first->info = current->info; //copy the info first->link = nullptr; //set the link field of //the node to nullptr last = first; //make last point to the //first node current = current->link; //make current point to //the next node //copy the remaining list while (current != nullptr) { newNode = new nodeType; //create a node newNode->info = current->info; //copy the info newNode->link = nullptr; //set the link of //newNode to nullptr last->link = newNode; //attach newNode after last last = newNode; //make last point to //the actual last node current = current->link; //make current point //to the next node }//end while }//end else }//end copyList template linkedListType::~linkedListType() //destructor { destroyList(); }//end destructor template linkedListType::linkedListType (const linkedListType& otherList) { first = nullptr; copyList(otherList); }//end copy constructor //overload the assignment operator template const linkedListType& linkedListType::operator= (const linkedListType& otherList) { if (this != &otherList) //avoid self-copy { copyList(otherList); }//end else return *this; } #endif //orderedLinkedList.h #ifndef H_orderedListType #define H_orderedListType #include "linkedList.h" using namespace std; template class orderedLinkedList : public linkedListType { public: bool search(const Type& searchItem) const; void insert(const Type& newItem); void insertFirst(const Type& newItem); void insertLast(const Type& newItem); void deleteNode(const Type& deleteItem); }; template bool orderedLinkedList::search(const Type& searchItem) const { bool found = false; nodeType *current; //pointer to traverse the list current = first; //start the search at the first node while (current != nullptr && !found) if (current->info >= searchItem) found = true; else current = current->link; if (found) found = (current->info == searchItem); //test for equality return found; }//end search template void orderedLinkedList::insert(const Type& newItem) { nodeType *current; //pointer to traverse the list nodeType *trailCurrent; //pointer just before current nodeType *newNode; //pointer to create a node bool found; newNode = new nodeType; //create the node newNode->info = newItem; //store newItem in the node newNode->link = nullptr; //set the link field of the node //to nullptr if (first == nullptr) //Case 1 { first = newNode; last = newNode; count++; } else { current = first; found = false; while (current != nullptr && !found) //search the list if (current->info >= newItem) found = true; else { trailCurrent = current; current = current->link; } if (current == first) //Case 2 { newNode->link = first; first = newNode; count++; } else //Case 3 { trailCurrent->link = newNode; newNode->link = current; if (current == nullptr) last = newNode; count++; } }//end else }//end insert template void orderedLinkedList::insertFirst(const Type& newItem) { insert(newItem); }//end insertFirst template void orderedLinkedList::insertLast(const Type& newItem) { insert(newItem); }//end insertLast template void orderedLinkedList::deleteNode(const Type& deleteItem) { nodeType *current; //pointer to traverse the list nodeType *trailCurrent; //pointer just before current bool found; if (first == nullptr) //Case 1 cout << "Cannot delete from an empty list." << endl; else { current = first; found = false; while (current != nullptr && !found) //search the list if (current->info >= deleteItem) found = true; else { trailCurrent = current; current = current->link; } if (current == nullptr) //Case 4 cout << "The item to be deleted is not in the " << "list." << endl; else if (current->info == deleteItem) //the item to be //deleted is in the list { if (first == current) //Case 2 { first = first->link; if (first == nullptr) last = nullptr; delete current; } else //Case 3 { trailCurrent->link = current->link; if (current == last) last = trailCurrent; delete current; } count--; } else //Case 4 cout << "The item to be deleted is not in the " << "list." << endl; } }//end deleteNode #endif //source.cpp //No changes to be made //Data //68 43 10 56 77 82 61 82 33 56 72 66 99 88 12 6 7 21 -999 #include #include "binarySearchTree.h" #include "orderedLinkedList.h" using namespace std; int main() { bSearchTreeType treeRoot; orderedLinkedList newList; int num; cout << "Enter numbers ending with -999" << endl; cin >> num; while (num != -999) { treeRoot.insert(num); cin >> num; } cout << endl << "Tree nodes in inorder: "; treeRoot.inorderTraversal(); cout << endl; cout << "Tree Height: " << treeRoot.treeHeight() << endl; treeRoot.createList(newList); cout << "newList: "; newList.print(); cout << endl; system("pause"); return 0; } /* i have 2 errors:: error C2039: 'createList' : is not a member of 'bSearchTreeType' error C2953: 'nodeType' : class template has already been defined */