Create a gist now

Instantly share code, notes, and snippets.

anonymous /.cpp
Created Jun 18, 2017

What would you like to do?
#ifndef BINARYTREE_H
#define BINARYTREE_H
#include <iostream>
template <class T>
class BinTree {
private:
struct TreeNode {
T value;
TreeNode *left;
TreeNode *right;
};
TreeNode *root;
//private member functions
void insert(TreeNode *&, TreeNode*&);
void deleteNode(T, TreeNode *&);
void makeDeletion(TreeNode *&);
//display functions
void displayInOrder(TreeNode *) const;
void displayPreOrder(TreeNode *) const;
void displayPostOrder(TreeNode *) const;
//count functions
int getNodeCount(TreeNode *root);
int getLeafCount(TreeNode *nodePtr);
int getHeight(TreeNode *nodePtr);
public:
//constructor
BinTree(){
root = nullptr;
}
//modification functions
void insertNode(T);
bool searchNode(T);
void remove(T);
//display functions
void displayInOrder() const {
displayInOrder(root);
}
void displayPreOrder() const {
displayPreOrder(root);
}
void displayPostOrder() const {
displayPostOrder(root);
}
//count functions
int countNodes(){
return getNodeCount(root);
}
int countLeafs(){
return getLeafCount(root);
}
int countHeight(){
return getHeight(root);
}
};
//constructor
//template <class T>
//BinTree<T>(){
//root = nullptr; }
//functions for node insertion
template <class T>
void BinTree<T>::insertNode(T num) {
TreeNode *newNode = nullptr;
newNode = new TreeNode;
newNode->value = num;
newNode->left = newNode->right = nullptr;
insert(root, newNode);
}
template <class T>
void BinTree<T>::insert(TreeNode *&nodePtr, TreeNode *&newNode)
{
if (nodePtr == nullptr)
nodePtr = newNode;
else if (newNode->value < nodePtr->value)
insert(nodePtr->left, newNode);
else
insert(nodePtr->right, newNode);
}
//functions for node deletion
template <class T>
void BinTree<T>::remove(T num) {
deleteNode(num, root);
}
template <class T>
void BinTree<T>::deleteNode(T num, TreeNode *&nodePtr) {
if (num < nodePtr->value)
deleteNode(num, nodePtr->left);
else if (num > nodePtr->value)
deleteNode(num, nodePtr->right);
else
makeDeletion(nodePtr);
}
template <class T>
void BinTree<T>::makeDeletion(TreeNode *& nodePtr) {
TreeNode *tempPtr = nullptr;
if (nodePtr == nullptr)
std::cout << "Cannot delete an empty node";
else if (nodePtr->right == nullptr) {
tempPtr = nodePtr;
nodePtr = nodePtr->left;
delete tempPtr;
}
else if (nodePtr->left == nullptr) {
tempPtr = nodePtr;
nodePtr = nodePtr->right;
delete tempPtr;
}
else {
tempPtr = nodePtr->right;
while (tempPtr->left)
tempPtr = tempPtr->left;
tempPtr->left = nodePtr->left;
tempPtr = nodePtr;
nodePtr = nodePtr->right;
delete tempPtr;
}
}
//display functions
template <class T>
void BinTree<T>::displayInOrder(TreeNode *nodePtr) const{
if (nodePtr) {
displayInOrder(nodePtr->left);
std::cout << nodePtr->value << std::endl;
displayInOrder(nodePtr->right);
}
}
template <class T>
void BinTree<T>::displayPreOrder(TreeNode *nodePtr) const {
if (nodePtr) {
std::cout << nodePtr->value << std::endl;
displayPreOrder(nodePtr->left);
displayPreOrder(nodePtr->right);
}
}
template <class T>
void BinTree<T>::displayPostOrder(TreeNode *nodePtr) const {
if (nodePtr) {
displayPostOrder(nodePtr->left);
displayPostOrder(nodePtr->right);
std::cout << nodePtr->value << std::endl;
}
}
//search function
template <class T>
bool BinTree<T>::searchNode(T num) {
TreeNode *nodePtr = root;
while (nodePtr) {
if (nodePtr->value == num)
return true;
else if (nodePtr->value > num)
nodePtr = nodePtr->left;
else
nodePtr = nodePtr->right;
}
return false;
}
template <class T>
int BinTree<T>::getNodeCount(TreeNode *nodePtr) {
//int nodeCount = 0;
if (nodePtr)
return 1 + getNodeCount(nodePtr->left) + getNodeCount(nodePtr->right);
return 0;
}
template <class T>
int BinTree<T>::getLeafCount(TreeNode *nodePtr) {
if (!nodePtr)
return 0;
if (nodePtr->left == nullptr && nodePtr->right == nullptr)
return 1;
else
return getLeafCount(nodePtr->left) + getLeafCount(nodePtr->right);
}
template <class T>
int BinTree<T>::getHeight(TreeNode *nodePtr) {
if (!nodePtr)
return 0;
else {
int leftDepth = getHeight(nodePtr->left);
int rightDepth = getHeight(nodePtr->right);
if (leftDepth > rightDepth)
return leftDepth + 1;
else return rightDepth + 1;
}
}
#endif // !BINARYTREE_H
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment