Task4.h

#pragma once



#include<iostream>
#include<string>
#include<vector>


namespace mytree
{
	struct Student
	{
		//This is the data in node for BST 
		int unique_key;
		std::string student_name;
		int birth_date;
		std::string home_address;
		int student_sid;
		int date_of_enrolment;
		std::string student_status;

		Student()
		{
			// need to reset the data in node
			unique_key = 0;
			student_name = "";
			birth_date = 0;
			student_sid = 0;
			home_address = "";
			date_of_enrolment = 0;
			student_status = "";

		}

		Student(int key, std::string name, int b_date,
			std::string address, int sid, int enrolment,
			std::string status)
		{
			unique_key = key;
			student_name = name;
			birth_date = b_date;
			student_sid = sid;
			home_address = address;
			date_of_enrolment = enrolment;
			student_status = status;
		}

	};
	struct Node
	{
		//This is the Node struct it has Left, Right and Student( it has data for nodes)
		Student mStudent;



		Node* mpLeft;	//It can make access with node's left child node
		Node* mpRight;	//It can make access with node's Right child node

		Node(Student& student, Node* pLeft, Node* pRight)
		{

			mStudent = Student(student);

			mpRight = pRight;
			mpLeft = pLeft;
		}


	};




	class BinaryTree
	{
	public:
		BinaryTree()
		{

		}

		Node* CreateNode(Student& student) // Its a Creation function to make a new Node and return the new Node.
		{
			return new Node(student, nullptr, nullptr);	//Create new node which has struct student values. First node does not have child so mpLeft and mpRight is nullptr.
		}

		//In BST, Node's Left has smaller value than parents and Right has bigger value node. For example, if Root_Node is 5, Left child node can be 4,3,2 and 1 and Right child can be bigger than 5 (ex 6, 7, 8, 9 ,,,,)
		Node* InsertBST(Node* node, Student& student)
		{
			if (node == nullptr)
			{
				return CreateNode(student);
			}
			if (student.unique_key < node->mStudent.unique_key)	//Insert smaller value to parent's Left side
			{
				node->mpLeft = InsertBST(node->mpLeft, student);	// node->mpLeft =  InsertBST(node->mpLeft, student), beacuse to connect the new Node with Node
			}
			else if (student.unique_key > node->mStudent.unique_key) //insert bigger value parent's Right side
			{
				node->mpRight = InsertBST(node->mpRight, student);
			}
			return node;
		}
		// If users insert Root = (8), (3) and (10), (3) goes Root(8)'s Left side because (3) is smaller than (8) and (10) goes Right side. If user insert (6), it goes (8)'s Left side and (3)'s Right side



		void Visit(Node* node) // Visit function is that visits the node and print node's struct student data.
		{
			std::cout << "Unique_Key : " << node->mStudent.unique_key << " , "
				<< " Name : " << node->mStudent.student_name << " , "
				<< " Date of Birth : " << node->mStudent.birth_date << " , "
				<< " Home address : " << node->mStudent.home_address << " , "
				<< " Student ID : " << node->mStudent.student_sid << " , "
				<< " Date of Enrolment : " << node->mStudent.date_of_enrolment << " , "
				<< " Status " << node->mStudent.student_status;
			std::cout << std::endl;
		}




		void Preorder(Node* node)	//This is the Preorder function. Based on this function, can visit all nodes in tree
		{							// Pre Order is Root_Node -> Left Sub_Tree -> Right Sub_Tree
			if (node == nullptr)	// In Order is Left Sub_Tree -> Root_Node -> Right Sub_Tree
			{						// Post Order  Left Sub_Tree -> Right Sub_Tree -> Root_Node
				return;
			}
			Visit(node);
			Preorder(node->mpLeft);
			Preorder(node->mpRight);
		}
		void Inorder(Node* node)
		{
			if (node == nullptr)
			{
				return;
			}
			Inorder(node->mpLeft);
			Visit(node);
			Inorder(node->mpRight);
		}


		// This is KEY_SERACH function. Used Pre Order function to traversal the tree. 
		// If user put int keyV which match with unique_key, user can change the node's value because it returns &node->mStudent so users can access with node data
		Student* KEY_SEARCH(Node* node, int keyV)
		{
			if (node == nullptr)
			{
				return nullptr;	//It means tree is empty so return the nullptr
			}

			if (node->mStudent.unique_key == keyV)
			{

				return &node->mStudent;
			}

			else if (node->mStudent.unique_key > keyV)
			{
				KEY_SEARCH(node->mpLeft, keyV);

			}
			else
			{
				KEY_SEARCH(node->mpRight, keyV);

			}
		}


		//  Used In Order function to traversal the tree. If node has same value with sidV, the node is stored in vector so user can print students data which is stored in vector
		void ListbyClass(Node* node, std::vector<std::string>& vector, int sidV)
		{
			if (node == nullptr)	// node == nullptr, it means the tree is empty
			{
				std::cout << " The tree is empty " << std::endl;
				return;
			}

			if (node->mpLeft != nullptr)
			{
				ListbyClass(node->mpLeft, vector, sidV);
			}
			if (node->mStudent.student_sid == sidV)
			{
				vector.push_back(node->mStudent.student_name);
			}
			if (node->mpRight != nullptr)
			{
				ListbyClass(node->mpRight, vector, sidV);
			}
		}

		// Also Used In Order for traversal. It is a function which can store all nodes name in vector during the traversal. For printing, users can put out the vector's index
		void AllNames(Node* node, std::vector<std::string>& vector)
		{
			if (node == nullptr)
			{
				std::cout << " The tree is empty " << std::endl;
				return;
			}
			if (node->mpLeft != nullptr)
			{
				AllNames(node->mpLeft, vector);
			}
			vector.push_back(node->mStudent.student_name);
			if (node->mpRight != nullptr)
			{
				AllNames(node->mpRight, vector);
			}

		}
		// This function is that traversal all nodes and if there are nodes which has same status with input, the node data is stored in vector.
		void Graduated_List(Node* node, std::vector<std::string>& vector, std::string statusV)
		{
			if (node == nullptr)
			{
				std::cout << " The tree is empty " << std::endl;
				return;
			}

			if (node->mpLeft != nullptr) // If node's Left is exist, traversal to node's Left side
			{
				Graduated_List(node->mpLeft, vector, statusV);
			}
			if (node->mStudent.student_status == statusV)
			{
				vector.push_back(node->mStudent.student_name);
			}
			if (node->mpRight != nullptr)
			{
				Graduated_List(node->mpRight, vector, statusV);
			}
		}
		// Traversal all nodes and if there are nodes which has same status and sidV input, the node' data is stored in vector.
		void UnGradue_Class(Node* node, std::vector<std::string>& vector, std::string statusV, int sidV)
		{
			if (node == nullptr)
			{
				std::cout << " The tree is empty " << std::endl;
				return;
			}

			if (node->mpLeft != nullptr)
			{
				UnGradue_Class(node->mpLeft, vector, statusV, sidV);
			}
			if (node->mStudent.student_status == statusV && node->mStudent.student_sid == sidV)
			{
				vector.push_back(node->mStudent.student_name);	// This is the function to push the node data in vector
			}
			if (node->mpRight != nullptr)
			{
				UnGradue_Class(node->mpRight, vector, statusV, sidV);
			}
		}




		Node* Remove_Key(Node* node, int keyV)
		{
			if (node == nullptr)
			{
				return nullptr;
			}
			// This is the search function to find keyV's node.
			// Users need input for keyV.
			if (node->mStudent.unique_key > keyV)
			{
				node->mpLeft = Remove_Key(node->mpLeft, keyV);	//If node's unique_key value is bigger than keyV, need to go Left node because Left side child node has smaller value than its parents node
			}
			else if (node->mStudent.unique_key < keyV)	// If keV is bigger than unique_key, it means keyV's node is placed current node's Right side because in BST, bigger is Right and smaller is Left
			{
				node->mpRight = Remove_Key(node->mpRight, keyV);
			}
			else if (node->mStudent.unique_key == keyV)// It means that find a keyV's node
			{
				// node has 0 child	// If keyV's node has 0 child , we can delete the node directly because it does not have child node so dont need consider the tree's shape.
				if (node->mpLeft == nullptr && node->mpRight == nullptr)
				{

					delete node;
					node = nullptr;
				}
				// node has 1 child	// If node has only 1 child, need to check the child node's position. If child node node's Right is empty, need to go Left side. If node's Left side is empty, go Right side.
				else if (node->mpRight == nullptr) // 
				{
					Node* space = node->mpLeft;
					delete node;
					return space;
				}
				else if (node->mpLeft == nullptr)	// to maintain the tree's shape, need to make space. space is can be current node's left child or right child node
				{									// for deleting node which has 1 child node, need to make a connect between current node's parent node and current node's child node.
					Node* space = node->mpRight;	// If we make connection between this 2 nodes, we can delete current node.
					delete node;
					return space;
				}

				// node has 2 child
				else if (node->mpLeft != nullptr && node->mpRight != nullptr)	//	If node has 2 child, need to swap 2 nodes. One is node( want to delete) the other is Max node so we need to make Find max node function
				{																// Find max node is that node(which want to delete)'s Left sub tree's biggest value. It means, max node is leaf node(easily delete)
																				// and it is bigger than node(which want to delete)'s Left child and smaller than Right child.
					Node* space = Find_MaxNode(node->mpLeft);
					node->mStudent = space->mStudent;
					node->mpLeft = Remove_Key(node->mpLeft, node->mStudent.unique_key);
				}

			}
			return node; // It return Root node so if Root node is chaneged users do not need to change the Root node;
		}
		Node* Find_MaxNode(Node* node)	// This is the Find_MaxNode function to find out a node which can swap the node which has 2 child.
		{
			if (node == nullptr)
			{
				return nullptr;
			}
			if (node->mpRight == nullptr)
			{
				return node;
			}
			while (node->mpRight != nullptr)
			{
				node = node->mpRight;
			}
			return node;
		}

		void Graduated_List_2(Node* node, std::vector<int>& vector, std::string statusV)	// Use traversal to visit all nodes and if the node's student status has same data with statusV("Graduated")
		{																					// node's unique_key value is stored in vector and ,in cpp, using for Loop, vectors index which has unique_key value goes in Remove_Key's parameter(int keyV)
			if (node == nullptr)
			{
				return;
			}

			if (node->mpLeft != nullptr)
			{
				Graduated_List_2(node->mpLeft, vector, statusV);
			}
			if (node->mStudent.student_status == statusV)
			{
				vector.push_back(node->mStudent.unique_key);
			}
			if (node->mpRight != nullptr)
			{
				Graduated_List_2(node->mpRight, vector, statusV);
			}
		}

	};
}