Fixed Something Something

/*
NodeCount.cpp
Ryan Schumacher
Version 1.0
3-31-20
Program will be utilizing the IntBinaryTree class provided via the professor and in class. Utilizing this class I added in a couple sets of member functions to either count all the nodes in the tree and to count all the leaf nodes in the tree. These functions added were
the countNodes and its recursive counterpart as well as countLeafNodes and its recursive counterpart. These classes will have the address of a class object sent to them that holds all the nodes already inserted into the tree. From there it will check the nodes down the
list to see if they contain the NULL value or not. If they are not NULL, the function will then increment the counter and move on to the next node. Similar cases will occur for the leaf node counter but instead, each root will essentially check its left and right nodes
to see whether they are NULL or not. If both left and right point to NULL, then the counter is incremented thus adding one more to the leaf node counter.
*/
#include <iostream>
#ifndef INTBINARYTREE_H
#define INTBINARYTREE_H
using namespace std;
class IntBinaryTree
{
private:
	struct TreeNode
	{
	public:
		int 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(int, TreeNode *&);
	int countNodesrecursive(TreeNode *);
	int countLeafNodesrecursive(TreeNode *);
	void makeDeletion(TreeNode *&);
	void displayInOrder(TreeNode *) const;
	void displayPreOrder(TreeNode *) const;
	void displayPostOrder(TreeNode *) const;
public:
	// Constructor
	IntBinaryTree()
	{
		root = nullptr;
	}
	// Destructor
	~IntBinaryTree()
	{
		destroySubTree(root);
	}
	// Binary tree operations
	int maxHeight(TreeNode *);
	int height(IntBinaryTree *);
	void newNode(int);
	int countNodes(IntBinaryTree *);
	int countLeafNodes(IntBinaryTree *);
	void insertNode(int);
	bool searchNode(int);
	void remove(int);
	void displayInOrder() const
	{
		displayInOrder(root);
	}
	void displayPreOrder() const
	{
		displayPreOrder(root);
	}
	void displayPostOrder() const
	{
		displayPostOrder(root);
	}

};
#endif



//insert Member Function inserts a node
void IntBinaryTree::insert(TreeNode *&nodePtr, TreeNode *&newNode)
{
	if (nodePtr == nullptr)
		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 Member Function calls insert function
void IntBinaryTree::insertNode(int num)
{
	TreeNode *newNode = nullptr;    // Pointer to a new node.
	// Create a new node and store num in it.
	newNode = new TreeNode;
	newNode->value = num;
	newNode->left = newNode->right = nullptr;
	// Insert the node.
	insert(root, newNode);
}

//destrySubTree Member Function
void IntBinaryTree::destroySubTree(TreeNode *nodePtr)
{
	if (nodePtr)
	{
		if (nodePtr->left)
			destroySubTree(nodePtr->left);
		if (nodePtr->right)
			destroySubTree(nodePtr->right);
		delete nodePtr;
	}
}

//Search tree member function
bool IntBinaryTree::searchNode(int num)
{
	TreeNode *nodePtr = root;
	while (nodePtr)
	{
		if (nodePtr->value == num)
			return true;
		else if (num < nodePtr->value)
			nodePtr = nodePtr->left;
		else
			nodePtr = nodePtr->right;
	}
	return false;
}

//remove Member Function calls deleteNode Member Function
void IntBinaryTree::remove(int num)
{
	deleteNode(num, root);
}

//deleteNode Member Function
void IntBinaryTree::deleteNode(int num, TreeNode *&nodePtr)
{
	if (num < nodePtr->value)
		deleteNode(num, nodePtr->left);
	else if (num > nodePtr->value)
		deleteNode(num, nodePtr->right);
	else
		makeDeletion(nodePtr);
}


void IntBinaryTree::makeDeletion(TreeNode *&nodePtr)
{
	// Define a temporary pointer to use in reattaching
	// the left subtree.
	TreeNode *tempNodePtr = nullptr;
	if (nodePtr == nullptr)
		cout << "Cannot delete empty node.\n";
	else if (nodePtr->right == nullptr)
	{
		tempNodePtr = nodePtr;
		nodePtr = nodePtr->left;   // Reattach the left child
		delete tempNodePtr;
	}
	else if (nodePtr->left == nullptr)
	{
		tempNodePtr = nodePtr;
		nodePtr = nodePtr->right;  // Reattach the right child
		delete tempNodePtr;
	}
	// If the node has two children.
	else
	{
		// Move one node the right.
		tempNodePtr = nodePtr->right;
		// Go to the end left node.
		while (tempNodePtr->left)
			tempNodePtr = tempNodePtr->left;
		// Reattach the left subtree.
		tempNodePtr->left = nodePtr->left;
		tempNodePtr = nodePtr;
		// Reattach the right subtree.
		nodePtr = nodePtr->right;
		delete tempNodePtr;
	}
}

// Recursive node counting member function
int IntBinaryTree::countNodesrecursive(TreeNode *root)
{
	int count = 1;
	if (root->left != NULL)
	{
		count += countNodesrecursive(root->left);
	}
	if (root->right != NULL)
	{
		count += countNodesrecursive(root->right);
	}
	return count;
}
//countNode Member Function to check for root then calls the recursive counting function
int IntBinaryTree::countNodes(IntBinaryTree *tree)
{
	int count = 0;
	if (tree->root != NULL) {
		count = countNodesrecursive(tree->root);
	}
	return count;
}

// Recursive leaf node counting member function
int IntBinaryTree::countLeafNodesrecursive(TreeNode *root)
{
	int count = 0;
	if (root->left == NULL && root->right == NULL) {
		count = 1;
	}
	else {
		if (root->left != NULL) {
			count += countLeafNodesrecursive(root->left);
		}
		if (root->right != NULL) {
			count += countLeafNodesrecursive(root->right);
		}
	}
	return count;
}
//countNode Member Function to check for root then calls the recursive counting function
int IntBinaryTree::countLeafNodes(IntBinaryTree *tree)
{
	int count = 0;
	if (tree->root != NULL) {
		count = countLeafNodesrecursive(tree->root);
	}
	return count;
}

//depth/height member function
int IntBinaryTree::height(IntBinaryTree* tree) {
	int count = 0;
	if (tree->root != NULL) {
		count = maxHeight(tree->root);
	}
	return count;
}

int IntBinaryTree::maxHeight(TreeNode *root) {
	int lCounter = 0, rCounter = 0;
	if (root->left != NULL) {
		int lDepth = maxHeight(root->left);
		lCounter++;
	}
	if (root->right != NULL) {
		int rDepth = maxHeight(root->right);
		rCounter++;
	}

	return (lCounter > rCounter) ? (lCounter + 1) : (rCounter + 1);
}

/* Helper function that allocates a new node with the
given data and NULL left and right pointers. */
void IntBinaryTree::newNode(int data)
{
	TreeNode* Node = new TreeNode();
	Node->value = data;
	Node->left = NULL;
	Node->right = NULL;
}

//Display Traversal InOrder
void IntBinaryTree::displayInOrder(TreeNode *nodePtr) const
{
	if (nodePtr)
	{
		displayInOrder(nodePtr->left);
		cout << nodePtr->value << endl;
		displayInOrder(nodePtr->right);
	}
}


//Display Traversal PreOrder
void IntBinaryTree::displayPreOrder(TreeNode *nodePtr) const
{
	if (nodePtr)
	{
		cout << nodePtr->value << endl;
		displayPreOrder(nodePtr->left);
		displayPreOrder(nodePtr->right);
	}
}

//Display Traversal PostOrder
void IntBinaryTree::displayPostOrder(TreeNode *nodePtr) const
{
	if (nodePtr)
	{
		displayPostOrder(nodePtr->left);
		displayPostOrder(nodePtr->right);
		cout << nodePtr->value << endl;
	}
}

int main()
{
	IntBinaryTree tree;
	tree.insertNode(41);
	tree.insertNode(20);
	tree.insertNode(65);
	tree.insertNode(11);
	tree.insertNode(29);
	tree.insertNode(32);
	tree.insertNode(50);
	tree.insertNode(91);
	tree.insertNode(73);
	tree.insertNode(99);
	tree.displayInOrder();
	cout << "Number of nodes in the tree: " << tree.countNodes(&tree) << endl;
	cout << "Number of leaf nodes in the tree: " << tree.countLeafNodes(&tree) << endl;
	cout << "Max height of the tree: " << tree.height(&tree) << endl;
	system("pause");
}