Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- BinaryTree.h
- #ifndef BINARYTREE_H
- #define BINARYTREE_H
- #include <iostream>
- using namespace std;
- // This class is a template class that creates a binary
- // tree that can hold values of any data type. It has
- // functions to insert a node, delete a node, display the
- // tree In Order, Pre Order and Post Order, search for a
- // value, count the number of total nodes, left nodes,
- // and a function to determine the height of the tree.
- template <class T>
- class BinaryTree
- {
- private:
- struct TreeNode
- {
- T value; // The value in the node
- TreeNode *left; // Pointer to left child node
- TreeNode *right; // Pointer to right child node
- };
- TreeNode *root; // Pointer to the root node
- // Private member functions
- void insert(TreeNode *&, TreeNode *&);
- void destroySubTree(TreeNode *);
- void deleteNode(T, TreeNode *&);
- void makeDeletion(TreeNode *&);
- void displayInOrder(TreeNode *) const;
- void displayPreOrder(TreeNode *) const;
- void displayPostOrder(TreeNode *) const;
- int counter(TreeNode *);
- int leafCounter(TreeNode *);
- int height(TreeNode *);
- public:
- // Constructor
- BinaryTree()
- { root = NULL; }
- // Destructor
- ~BinaryTree()
- { destroySubTree(root); }
- // Binary tree operations
- void insertNode(T);
- bool searchNode(T);
- void remove(T);
- void displayPreOrder() const
- { displayPreOrder(root); }
- void displayInOrder() const
- { displayInOrder(root); }
- void displayPostOrder() const
- { displayPostOrder(root); }
- // Node counter
- int counter()
- {
- int n = counter(root);
- return n;
- }
- // Leaf counter
- int leafCounter()
- {
- int leaf = leafCounter(root);
- return leaf;
- }
- // Height of the tree
- int height()
- {
- int h = height(root);
- return h;
- }
- };
- //*********************************************************
- // insert function accepts a TreeNode pointer and a *
- // pointer to a node. The function inserts the node into *
- // the tree pointer to by the TreeNode pointer. This *
- // function is call recursively. *
- //*********************************************************
- template <class T>
- void BinaryTree<T>::insert(TreeNode *&nodePtr, TreeNode *&newNode)
- {
- if (nodePtr == NULL)
- nodePtr = newNode; // Insert the node
- else if (newNode->value < nodePtr->value)
- insert(nodePtr->left, newNode); // Search the left branch
- else
- insert(nodePtr->right, newNode);// Search the right branch
- }
- //*********************************************************
- // insertNode creates anew node to hold num as its value *
- // and passes it to the insert function. *
- //*********************************************************
- template <class T>
- void BinaryTree<T>::insertNode(T item)
- {
- TreeNode *newNode; // Pointer to a new node
- // Create anew node and store num in it
- newNode = new TreeNode;
- newNode->value = item;
- newNode->left = newNode->right = NULL;
- // Insert the node
- insert(root, newNode);
- }
- //**********************************************************
- // destroySubTree is called by the destructor. It deletes *
- // all nodes in the tree. *
- //**********************************************************
- template <class T>
- void BinaryTree<T>::destroySubTree(TreeNode *nodePtr)
- {
- if (nodePtr)
- {
- if (nodePtr->left)
- destroySubTree(nodePtr->left);
- if (nodePtr->right)
- destroySubTree(nodePtr->right);
- delete nodePtr;
- }
- }
- //**********************************************************
- // searchNode determines if a value is present in the tree.*
- // If so, the function returns true. Otherwise it returns *
- // false.
- //**********************************************************
- template <class T>
- bool BinaryTree<T>::searchNode(T item)
- {
- TreeNode *nodePtr = root;
- while (nodePtr)
- {
- if (nodePtr->value == item)
- return true;
- else if (item < nodePtr->value)
- nodePtr = nodePtr->left;
- else
- nodePtr = nodePtr->right;
- }
- return false;
- }
- //*********************************************************
- // remove calls deleteNode to delete the node whode value *
- // member is the same as num *
- //*********************************************************
- template <class T>
- void BinaryTree<T>::remove(T item)
- {
- deleteNode(item, root);
- }
- //*********************************************************
- // deleteNode deletes the node whose value member is the *
- // same as num *
- //*********************************************************
- template <class T>
- void BinaryTree<T>::deleteNode(T item, TreeNode *&nodePtr)
- {
- if (item < nodePtr->value)
- deleteNode(item, nodePtr->left);
- else if (item > nodePtr->value)
- deleteNode(item, nodePtr->right);
- else
- makeDeletion(nodePtr);
- }
- //*********************************************************
- // makeDeletion takes a reference to apointer to the node *
- // that is to be deleted. The node is removed and the *
- // branches of the tree below the node are reattached *
- //*********************************************************
- template <class T>
- void BinaryTree<T>::makeDeletion(TreeNode *&nodePtr)
- {
- // Define a temporary pointer to use in reattaching
- // the left subtree
- TreeNode *tempNodePtr;
- if (nodePtr == NULL)
- cout << "Cannot delete empty node.\n";
- else if (nodePtr->right == NULL)
- {
- tempNodePtr = nodePtr;
- nodePtr = nodePtr->left; // Reattach the left child
- delete tempNodePtr;
- }
- else if (nodePtr->left == NULL)
- {
- tempNodePtr = nodePtr;
- nodePtr = nodePtr->right; // Reattach the right child
- delete tempNodePtr;
- }
- }
- //*********************************************************
- // The displayInOrder function displays the values in the *
- // subtree pointed to by nodePtr, via inorder traversal *
- //*********************************************************
- template <class T>
- void BinaryTree<T>::displayInOrder(TreeNode *nodePtr) const
- {
- if (nodePtr)
- {
- displayInOrder(nodePtr->left);
- cout << nodePtr->value.getEmpID() << " "
- << getEmpName() << endl;
- displayInOrder(nodePtr->right);
- }
- }
- //*********************************************************
- // The displayPreOrder function displays the values in the*
- // subtree pointed to by nodePtr, via Preorder traversal *
- //*********************************************************
- template <class T>
- void BinaryTree<T>::displayPreOrder(TreeNode *nodePtr) const
- {
- if (nodePtr)
- {
- cout << nodePtr->value << endl;
- displayInOrder(nodePtr->left);
- displayInOrder(nodePtr->right);
- }
- }
- //*********************************************************
- // displayPostOrder function displays the values in the *
- // subtree pointed to by nodePtr, via Postorder traversal *
- //*********************************************************
- template <class T>
- void BinaryTree<T>::displayPostOrder(TreeNode *nodePtr) const
- {
- if (nodePtr)
- {
- displayInOrder(nodePtr->left);
- displayInOrder(nodePtr->right);
- cout << nodePtr->value << endl;
- }
- }
- //*********************************************************
- // counter counts the number of nodes the tree has *
- //*********************************************************
- template <class T>
- int BinaryTree<T>::counter(TreeNode *nodePtr)
- {
- if (nodePtr == NULL)
- return 0;
- else
- return counter(nodePtr->left) +1+ counter(nodePtr->right);
- }
- //*********************************************************
- // leafCounter counts the number of leaf nodes in the tree*
- //*********************************************************
- template <class T>
- int BinaryTree<T>::leafCounter(TreeNode *nodePtr)
- {
- if (nodePtr == NULL)
- return 0;
- else if (nodePtr->left == NULL && nodePtr->right == NULL)
- return 1;
- else
- return leafCounter(nodePtr->left) + leafCounter(nodePtr->right);
- }
- //*********************************************************
- // height returns the height of the tree *
- //*********************************************************
- template <class T>
- int BinaryTree<T>::height(TreeNode *nodePtr)
- {
- if(nodePtr == NULL)
- return -1;
- if (height(nodePtr->left) <= height(nodePtr->right))
- return (height(nodePtr->right) +1);
- else
- return (height(nodePtr->left) +1);
- }
- #endif
- EmployeeInfo.h
- #ifndef EMPLOYEEINFO_H
- #define EMPLOYEEINFO_H
- #include <string>
- using namespace std;
- // This class has two data members to hold the employee ID
- // and the name of the employee.
- class EmployeeInfo
- {
- private:
- int empID; // To hold employee ID number
- string empName; // To hold employee name
- public:
- // Default Constructor
- EmployeeInfo();
- // Constructor
- EmployeeInfo(int, string);
- // Mutators
- void setEmpID(int);
- void setEmpName(string);
- // Accessors
- int getEmpID();
- string getEmpName();
- bool operator < (const EmployeeInfo &e)
- {
- if (empID < e.empID)
- return true;
- if (empName < e.empName)
- return true;
- return false;
- }
- };
- #endif
- #include "EmployeeInfo.h"
- //*********************************************************
- // Default constructor intializes the data members *
- //*********************************************************
- EmployeeInfo::EmployeeInfo()
- {
- empID = 0;
- empName = "";
- }
- //*********************************************************
- // Constructor sets the data members *
- //*********************************************************
- EmployeeInfo::EmployeeInfo(int ID, string name)
- {
- empID = ID;
- empName = name;
- }
- //*********************************************************
- // setEmpID stores the employee ID number *
- //*********************************************************
- void EmployeeInfo::setEmpID(int ID)
- {
- empID = ID;
- }
- //*********************************************************
- // setEmpName stores the full name of the employee *
- //*********************************************************
- void EmployeeInfo::setEmpName(string name)
- {
- empName = name;
- }
- //*********************************************************
- // getEmpID returns the employee ID number *
- //*********************************************************
- int EmployeeInfo::getEmpID()
- {
- return empID;
- }
- //*********************************************************
- // getEmpName returns the full name of the employee *
- //*********************************************************
- string EmployeeInfo::getEmpName()
- {
- return empName;
- }
- Main
- #include "EmployeeInfo.h"
- #include "BinaryTree.h"
- #include <iostream>
- using namespace std;
- int main()
- {
- // Create an instance of BinaryTree
- BinaryTree<EmployeeInfo> tree;
- // Create an EmployeeInfo object
- EmployeeInfo info;
- EmployeeInfo emp1(1021, "John Williams");
- EmployeeInfo emp2(1057, "Bill Witherspoon");
- // Store the information
- info.setEmpID(1021);
- info.setEmpID(1057);
- info.setEmpName("John Williams");
- info.setEmpName("Bill Witherspoon");
- tree.insertNode(emp1);
- tree.insertNode(emp2);
- // Display in order
- tree.displayInOrder();
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement