Announcements | Last Post | |
---|---|---|
SoC Curricula | 09/30/2017 01:08PM | |
Demarcation or scoping of examinations and assessment | 02/13/2017 07:59AM | |
School of Computing Short Learning Programmes | 11/24/2014 08:37AM | |
Unisa contact information | 07/28/2011 01:28PM |
[Linker error] ?? July 29, 2009 04:57PM |
Registered: 18 years ago Posts: 560 Rating: 2 |
Language: C++//Defining a Binary Tree as an ADT //CHAPTER 11 #include <iostream> using namespace std; //Definition of the node template<class elemType> struct nodeType { elemType info; nodeType<elemType> *llink; nodeType<elemType> *rlink; }; //Definition of the class template<class elemType> class binaryTreeType { public: const binaryTreeType<elemType>& operator= (const binaryTreeType<elemType>&); //Overload the assignment operator bool isEmpty(); //Function to determine whether the binary tree is empty /* Postcondition: Returns true if the binary tree is empty; otherwise , returns false. */ void inorderTraversal(); //Function to do an inorder traversal of the binary tree. /* Postcondition: The nodes of the binary tree are output in the inorder sequence. */ void preorderTraversal(); //Function to do a preorder traversal of the binary tree. /* Postcondition: The nodes of the binary tree are output in the preorder sequence. */ void postorderTraversal(); //Function to do a postorder traversal of the binary tree. /* Postcondition: The nodes of the binary tree are output in the postorder sequence. */ int treeHeight(); //Function to determine the height of the binary tree. //Postcondition: The height of the binary tree is returned. int treeNodeCount(); //Function to determine the number of nodes in the binary tree. //Postcondition: The number of nodes in the binary tree is returned. int treeLeavesCount(); //Function to determine the number of leaves in the binary tree. //Postcondition: The number of leaves in the binary tree is returned. void destroyTree(); //Deallocates the memory space occupied by the binary tree. //Postcondition: root = NULL binaryTreeType(const binaryTreeType<elemType>& otherTree); //copy constructor binaryTreeType(); //constructor ~binaryTreeType(); //destructor protected: nodeType<elemType> *root; private: void copyTree(nodeType<elemType>* &copiedTreeRoot,nodeType<elemType>* otherTreeRoot); //Function to make a copy of the binary tree to which otherTreeRoot points /* Postcondition: The pointer copiedTreeRoot points to the root of the copied binary tree */ void destroy(nodeType<elemType>* &p); //Function to destroy the binary tree to which p points. /* Postcondition: The nodes of the binary tree to which p points are deallocated; p = NULL */ void inorder(nodeType<elemType> *p); //Function to do an inorder traversal of the binary tree to which p points /* Postcondition: The nodes of the binary tree to which p points are output in the inorder sequence */ void preorder(nodeType<elemType> *p); //Function to do a preorder traversal of the binary tree to which p points /* Postcondition: The nodes of the binary tree to which p points are output in the preorder sequence */ void postorder(nodeType<elemType> *p); //Function to do a postorder traversal of the binary tree to which p points /* Postcondition: The nodes of the binary tree to which p points are output in the postorder sequence */ int height(nodeType<elemType> *p); //Function to determine the height of the binary tree to which p points //Postcondition: The height of the binary tree to which p points is returned. int max(int x, int y); //Function to determine the larger of x and y; //Postcondition: The larger of x and y is returned. int nodeCount(nodeType<elemType> *p); //Function to determine the number of nodes in the binary tree to which p points //Postcondition: The number of nodes in the binary tree to which p points is returned int leavesCount(nodeType<elemType> *p); //Function to determine the number of leaves in the binary tree to which p points //Postcondition: The number of leaves in the binary tree to which p points is returned }; // -------------------------- Definition of member functions -------------------- // template<class elemType> bool binaryTreeType<elemType>::isEmpty() { return (root == NULL); } template<class elemType> void binaryTreeType<elemType>::inorderTraversal() { inorder(root); } template<class elemType> void binaryTreeType<elemType>::preorderTraversal() { preorder(root); } template<class elemType> void binaryTreeType<elemType>::postorderTraversal() { postorder(root); } template<class elemType> int binaryTreeType<elemType>::treeHeight() { return Height(root); } template<class elemType> int binaryTreeType<elemType>::treeLeavesCount() { return leavesCount(root); } template<class elemType> void binaryTreeType<elemType>::inorder(nodeType<elemType> *p) { if (p != NULL) { inorder(p->llink); cout << p->info << " "; inorder(p->rlink); } } template<class elemType> void binaryTreeType<elemType>::preorder(nodeType<elemType> *p) { if (p != NULL) { cout << p->info << " "; preorder(p->llink); preorder(p->rlink); } } template<class elemType> void binaryTreeType<elemType>::postorder(nodeType<elemType> *p) { if (p != NULL) { postorder(p->llink); postorder(p->rlink); cout << p->info << " "; } } template<class elemType> int binaryTreeType<elemType>::height(nodeType<elemType> *p) { if (p == NULL) return 0; else return 1 + max ( height(p->llink), height(p->rlink) ); } template<class elemType> int binaryTreeType<elemType>::max(int x, int y) { if (x > y) return x; else return y; } template<class elemType> void binaryTreeType<elemType>::copyTree(nodeType<elemType>* &copiedTreeRoot, nodeType<elemType>* otherTreeRoot) { if (otherTreeRoot == NULL) copiedTreeRoot = NULL; else { copiedTreeRoot = new nodeType<elemType>; copiedTreeRoot->info = otherTreeRoot->info; copyTree(copiedTreeRoot->llink,otherTreeRoot->llink); copyTree(copiedTreeRoot->rlink,otherTreeRoot->rlink); } } // end copyTree template<class elemType> void binaryTreeType<elemType>::destroy(nodeType<elemType>* &p) { if (p != NULL) { destroy(p->llink); destroy(p->llink); delete p; p = NULL; } } template<class elemType> void binaryTreeType<elemType>::destroyTree() { destroy(root); } //copy constructor template<class elemType> binaryTreeType<elemType>::binaryTreeType(const binaryTreeType<elemType>& otherTree) { if (otherTree.root == NULL) // otherTree is empty root = NULL; else copyTree(root, otherTree.root); } //destructor template<class elemType> binaryTreeType<elemType>::~binaryTreeType() { destroy(root); } //Overload the assignment operator template<class elemType> const binaryTreeType<elemType>& binaryTreeType<elemType>::operator= (const binaryTreeType<elemType>& otherTree) { if (this != &otherTree) //avoid self copy { if (root != NULL) //if the binary tree is not empty destroy the binary tree destroy(root); if (otherTree.root == NULL) //otherTree is empty root = NULL; else copyTree(root, otherTree.root); } //end else return *this; }
Language: C++//Binary search trees #include <iostream> #include <cassert> #include "BinaryTree.h" template<class elemType> class bSearchTreeType: public binaryTreeType<elemType> { public: bool search(const elemType& searchItem); //Function to determine whether searchItem is in the binary search tree /* Postcondition: Returns true if searchItem is found in the binary search tree; otherwise, returns false */ void insert(const elemType& insertItem); //Function to insert an item in the binary search tree /* Postcondition: If no node in the binary search tree has the same info as insertItem, a node with the info insertItem is created and inserted in the binary search tree. */ void deleteNode(const elemType& deleteItem); //Function to delete an item in the binary search tree /* Postcondition: If a node with the same info as deleteItem is found, it is deleted from the binary search tree */ private: void deleteFromTree(nodeType<elemType>* &p); //Function to delete the node, to which p points, from the binary search tree //Postcondition: The node to which p points is deleted from the binary search tree }; // -------------------------- Definition of member functions -------------------- // template<class elemType> bool bSearchTreeType<elemType>::search(const elemType& searchItem) { nodeType<elemType> *current; //temporary pointer to traverse the binary search tree bool found = false; if (this->root == NULL) cerr << "Cannot search an empty tree." << endl; else { current = this->root; while (current != NULL && !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<class elemType> void bSearchTreeType<elemType>::insert(const elemType& insertItem) { nodeType<elemType> *current; //pointer to traverse the tree nodeType<elemType> *trailCurrent; //pointer behind current nodeType<elemType> *newNode; //pointer to create the node newNode = new nodeType<elemType>; assert(newNode != NULL); newNode->info = insertItem; newNode->llink = NULL; newNode->rlink = NULL; if (this->root == NULL) this->root = newNode; else { current = this->root; while(current != NULL) { trailCurrent = current; if (current->info == insertItem) { cerr << "The insert item is already in the list - "; cerr << "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<class elemType> void bSearchTreeType<elemType>::deleteFromTree(nodeType<elemType>* &p) { nodeType<elemType> *current; //pointer to traverse the tree nodeType<elemType> *trailCurrent; //pointer just behind current nodeType<elemType> *temp; //pointer to delete the node if (p == NULL) cerr << "Error: The node to be deleted is NULL." << endl; else if (p->llink == NULL && p->rlink == NULL) { temp = p; p = NULL; delete temp; } else if (p->llink == NULL) { temp = p; p = temp->rlink; delete temp; } else if (p->rlink == NULL) { temp = p; p = temp->llink; delete temp; } else { current = p->llink; trailCurrent = NULL; while (current->rlink != NULL) { trailCurrent = current; current = current->rlink; } //end while p->info = current->info; if (trailCurrent == NULL) /* current did not move current = p->llink; adjust p */ p->llink = current->llink; else trailCurrent->rlink = current->llink; delete current; } //end else } //end deleteFromTree
Language: C++//Binary search tree -- MAIN PROGRAM ----- #include <iostream> #include "binarySearchTree.h" using namespace std; int main() { bSearchTreeType<int> treeRoot; int num; cout << "Enter numbers ending with -999" << endl; cin >> num; while (num != -999) { treeRoot.insert(num); cin >> num; } return 0; }
Re: [Linker error] ?? July 29, 2009 08:27PM |
Registered: 18 years ago Posts: 1,424 Rating: 0 |
Language: C++void destroyTree(); //Deallocates the memory space occupied by the binary tree. //Postcondition: root = NULL binaryTreeType(const binaryTreeType<elemType>& otherTree); //copy constructor binaryTreeType(); "HERE';S YOUR CONSTRUCTOR DECLARATION" //constructor ~binaryTreeType(); //destructor protected: nodeType<elemType> *root;
Language: C++template<class elemType> void binaryTreeType<elemType>::destroyTree() { destroy(root); } //copy constructor template<class elemType> binaryTreeType<elemType>::binaryTreeType(const binaryTreeType<elemType>& otherTree) { if (otherTree.root == NULL) // otherTree is empty root = NULL; else copyTree(root, otherTree.root); } "YOUR DEFAULT CONSTRUCTOR SHOULD BE HERE" //destructor template<class elemType> binaryTreeType<elemType>::~binaryTreeType() { destroy(root); } //Overload the assignment operator template<class elemType> const binaryTreeType<elemType>& binaryTreeType<elemType>::operator= (const binaryTreeType<elemType>& otherTree) { if (this != &otherTree) //avoid self copy { if (root != NULL) //if the binary tree is not empty destroy the binary tree destroy(root); if (otherTree.root == NULL) //otherTree is empty root = NULL; else copyTree(root, otherTree.root); } //end else return *this; }
Language: C++//Defining a Binary Tree as an ADT //CHAPTER 11 #include <iostream> using namespace std; // <<<<<<<<<<<<<< Don';t do this in a header
Language: C++template<class elemType> void binaryTreeType<elemType>::postorder(nodeType<elemType> *p) { if (p != NULL) { postorder(p->llink); postorder(p->rlink); cout << p->info << " "; } }
Language: C++template<class elemType> void binaryTreeType<elemType>::postorder(nodeType<elemType> *p) { if (p != NULL) { postorder(p->llink); postorder(p->rlink); std::cout << p->info << " "; // use the fully qualified name including the namespace name followed by the scope operator } }
Re: [Linker error] ?? July 30, 2009 12:17PM |
Registered: 18 years ago Posts: 560 Rating: 2 |