#include #include /*********************************************** Binary Search Tree with some basic feature ***********************************************/ /* Note: - The code are little bit laggy in here - Recommended to set the font size to small */ class BST // Binary Search Tree { private: struct node { int key; node* right; node* left; }; node* root; void AddLeafPrivate(int key, node* ptr); void PrintInOrderPrivate(node* ptr); void RemoveNodePrivate(int key, node* parent); node* ReturnNodePrivate(int key, node* ptr); int FindSmallestPrivate(node* ptr); void RemoveRootMatch(); void RemoveMatch(node* parent, node* match, bool left); public: BST() : root(nullptr) {} node* CreateLeaf(int key); node* ReturnNode(int key); void AddLeaf(int key); void PrintInOrder(); void PrintChildren(int key); void RemoveNode(int key); int ReturnRootKey(int key); int FindSmallest(); }; int main() { int treeKeys[16] = { 50, 76, 21, 4, 32, 64, 15, 52, 14, 100, 83, 2, 3, 70, 87, 80 }; BST myTree; int input = 0; //////////// Printing and adding Node //////////// std::cout << "Print the tree before we adding it with numbers\n"; myTree.PrintInOrder(); std::cout << "The smallest key in the tree is " << myTree.FindSmallest() << "\n"; for (int i = 0; i < 16; i++) { myTree.AddLeaf(treeKeys[i]); } std::cout << std::endl; std::cout << "Print the tree after we adding it with numbers\n"; myTree.PrintInOrder(); std::cout << std::endl; std::cout << "The smallest key in the tree is " << myTree.FindSmallest() << "\n"; std::cout << std::endl; /////// Print parent and their children ////// std::cout << "Print Children and their Parent\n"; for (int i = 0; i < 16; i++) { myTree.PrintChildren(treeKeys[i]); } std::cout << std::endl; //////////// Delete some Nodes //////////// std::cout << "Delete 3 Node (3, 50, 83)\n"; myTree.RemoveNode(3); std::cout << std::endl; myTree.RemoveNode(50); std::cout << std::endl; myTree.RemoveNode(83); std::cout << std::endl; ////// Print nodes after deletion section ////// std::cout << "Print all nodes in the tree\n"; myTree.PrintInOrder(); std::cout << std::endl; std::cout << "The smallest key in the tree is " << myTree.FindSmallest() << "\n"; std::cout << std::endl; std::cin.get(); } BST::node* BST::CreateLeaf(int key) { node* n = new node; n->key = key; n->right = nullptr; n->left = nullptr; return n; } void BST::AddLeaf(int key) { AddLeafPrivate(key, root); } void BST::AddLeafPrivate(int key, node* ptr) { if (root == nullptr) { root = CreateLeaf(key); } else if (key < ptr->key) { if (ptr->left == nullptr) { ptr->left = CreateLeaf(key); } else { AddLeafPrivate(key, ptr->left); } } else if (key > ptr->key) { if (ptr->right == nullptr) { ptr->right = CreateLeaf(key); } else { AddLeafPrivate(key, ptr->right); } } else { std::cout << "Key " << key << " has already been added to the Tree\n"; } } void BST::PrintInOrder() { PrintInOrderPrivate(root); } void BST::PrintInOrderPrivate(node* ptr) { if (root == nullptr) { std::cout << "The tree is empty\n"; } else { if (ptr->left != nullptr) { PrintInOrderPrivate(ptr->left); } std::cout << ptr->key << " "; if (ptr->right != nullptr) { PrintInOrderPrivate(ptr->right); } } } BST::node* BST::ReturnNode(int key) { return ReturnNodePrivate(key, root); } BST::node* BST::ReturnNodePrivate(int key, node* ptr) { if (root == nullptr) { std::cout << "The tree is empty\n"; return nullptr; } else if (ptr == nullptr) { return nullptr; } else { if (key == ptr->key) { return ptr; } else { if (key < ptr->key && ptr->left != nullptr) { return ReturnNodePrivate(key, ptr->left); } else if (key > ptr->key && ptr->right != nullptr) { return ReturnNodePrivate(key, ptr->right); } else { return nullptr; } } } } int BST::ReturnRootKey(int key) { if (root == nullptr) { std::cout << "The root didn't point to anything\n"; return 0; } else { return root->key; } } void BST::PrintChildren(int key) { node* ptr = BST::ReturnNode(key); if (ptr == nullptr) { std::cout << "The key " << key << " is not on the tree\n"; } else { std::cout << "Parent node = " << ptr->key << std::endl; ptr->left == nullptr ? std::cout << "Left child = NULL\n" : std::cout << "Left child = " << ptr->left->key << "\n"; ptr->right == nullptr ? std::cout << "Right child = NULL\n" : std::cout << "Right child = " << ptr->right->key << "\n"; } } int BST::FindSmallest() { return FindSmallestPrivate(root); } int BST::FindSmallestPrivate(node* ptr) { if (root == nullptr) { std::cout << "The Tree is empty\n"; return 0; } else { if (ptr->left != nullptr) { return FindSmallestPrivate(ptr->left); } else { return ptr->key; } } } void BST::RemoveNode(int key) { RemoveNodePrivate(key, root); } void BST::RemoveNodePrivate(int key, node* parent) { if (root == nullptr) { std::cout << "Cannot remove the node, The tree is empty\n"; } else { if (key == parent->key) { RemoveRootMatch(); } else { if (key < parent->key && parent->left != nullptr) { key == parent->left->key ? RemoveMatch(parent, parent->left, true) : RemoveNodePrivate(key, parent->left); } else if (key > parent->key && parent->right != nullptr) { key == parent->right->key ? RemoveMatch(parent, parent->right, false) : RemoveNodePrivate(key, parent->right); } else { std::cout << "The key " << key << " was not found in the tree\n"; } } } } void BST::RemoveRootMatch() { if (root == nullptr) { std::cout << "Cannot remove the node, The tree is empty\n"; } else { node* delPtr = root; int rootKey = root->key; int smallestInRightSubTree; // delete a leaf node if (root->left == nullptr && root->right == nullptr) { root = nullptr; delete delPtr; //delPtr = nullptr; } // delete a parent that have 1 child else if (root->left == nullptr && root->right != nullptr) { root = root->right; delPtr->right = nullptr; delete delPtr; delPtr = nullptr; std::cout << "The node with key " << rootKey << " was deleted\n"; std::cout << "the new root contains key " << root->key << "\n"; } else if (root->left != nullptr && root->right == nullptr) { root = root->left; delPtr->left = nullptr; delete delPtr; delPtr = nullptr; std::cout << "The node with key " << rootKey << " was deleted\n"; std::cout << "The new node contains key " << root->key << "\n"; } // delete a parent that have 2 children else { smallestInRightSubTree = FindSmallestPrivate(root->right); RemoveNodePrivate(smallestInRightSubTree, root); root->key = smallestInRightSubTree; std::cout << "The node that contain key " << rootKey << " was overwritten with key " << root->key << "\n"; } } } void BST::RemoveMatch(node* parent, node* match, bool left) { if (root == nullptr) { std::cout << "Cannot remove the match, the tree is empty\n"; } else { int matchKey = match->key; int smallestInRightSubTree; // delete a leaf node if (match->left == nullptr && match->right == nullptr) { left == true ? parent->left = nullptr : parent->right = nullptr; delete match; match = nullptr; std::cout << "The node containing key " << matchKey << " was removed\n"; } // delete a parent that have 1 child else if (match->left == nullptr && match->right != nullptr) { left == true ? parent->left = match->right : parent->right = match->right; match->right = nullptr; delete match; match = nullptr; std::cout << "The node containing key " << matchKey << " was removed\n"; } else if (match->left != nullptr && match->right == nullptr) { left == true ? parent->left = match->left : parent->right = match->left; match->left = nullptr; delete match; match = nullptr; std::cout << "The node containing key " << matchKey << " was removed\n"; } // delete a parent that have 2 children else { smallestInRightSubTree = FindSmallestPrivate(match->right); RemoveNodePrivate(smallestInRightSubTree, match); match->key = smallestInRightSubTree; std::cout << "The node that contain key " << matchKey << " was overwritten with key " << match->key << "\n"; } } }

BST (Binary Search Tree)