/*
NodeCount.cpp
Ryan Schumacher
Version 1.0
3-31-20
Program checks to add certain inventory selections to a queue. The user will be prompted and asked if they want to add something to a queue and if they select yes then they will be allowed to enter into different portions of the inventory.
If they select no, then the program will ask if they want to remove something instead. If yes, the program will initiate the dequeue function to remove the topmost item in the queue. If the user inputs no, then the program will display final queue results
and then simply end.
*/
#include <iostream>
#ifndef INTBINARYTREE_H
#define INTBINARYTREE_H
using namespace std;
class IntBinaryTree
{
private:
	struct TreeNode
	{
		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 *&);
	void makeDeletion(TreeNode *&);
	int  countNodesrecursive(TreeNode *);
	int  countNodes(IntBinaryTree *);
	void displayInOrder(TreeNode *) const;
	void displayPreOrder(TreeNode *) const;
	void displayPostOrder(TreeNode *) const;
public:
	// Constructor
	IntBinaryTree()
	{
		root = nullptr;
	}
	// Destructor
	~IntBinaryTree()
	{
		destroySubTree(root);
	}
	// Binary tree operations
	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)
{
	unsigned 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)
{
	unsigned int count = 0;
	if (tree->root != NULL) {
		count = countNodesrecursive(tree->root);
	}
	return count;
}


//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(5);
	tree.insertNode(8);
	tree.insertNode(3);
	tree.insertNode(12);
	tree.insertNode(19);
	tree.displayInOrder();
	system("pause");
}