Here is a really basic binary tree class, it just includes the basics of creating, inserting, erasing, and returning size. In later posts I will talk about printing and traversals.
This class also uses the Node.h talked about in this earlier post. You’ll notice that I really like to use recursion, I think this is cleaner than looping.
#include <assert.h> #include "Node.h" using namespace std; class Bst { public: //constructor for when a head Node is provided and when it is not Bst() { root = nullptr; } Bst(Node *np) { root = np; } //destroy the tree, we need to go through and destroy each node ~Bst() { destroyTree(root); } //get the number of nodes in the tree int size() { return size(root); } //erase a value in the tree void erase(int item) { erase(item, root); } //insert a Node in the tree void insert(int item) { insert(item, root); } private: Node* root; //Go through each branch and recursively destroy all Nodes void destroyTree(Node*& n) { if (n != nullptr) { destroyTree(n->left); destroyTree(n->right); delete n; } } //For each Node return the number of left and right nodes //Add it up recursively to get the total size int size(Node* n) { if (n != nullptr) { int left = size(n->left); int right = size(n->right); int self = 1; return left + self + right; } return 0; } //Find the minimum Node value Node* findMin(Node* n){ assert(n != nullptr); if (n->left != nullptr) { return findMin(n->left); } return n; } //this one is a beast //look through all the nodes recursively //once you find the node value there are numerous cases we need to look for //If the current node does not have left and right nodes, just delete it //If it does have a left or right node, set the child to the parent //If it has both left and right, we need to work some magic. First we find //the smallest value and set the node we want to delete to that value (removing it) void erase(int item, Node*& n) { if (n != nullptr) { if (item == n->data) { if (n->right == nullptr && n->left == nullptr) { delete n; n = nullptr; } else if (n->right == nullptr) { Node* temp = n; n = n->left; delete n; } else if (n->left == nullptr){ Node* temp = n; n = n->right; delete n; } else { Node *temp = findMin(n->right); n->data = temp->data; erase(item, n->right); } } else if (item < n->data) { erase(item, n->left); } else { erase(item, n->right); } } } //look through all the nodes //insert the node on the correct node, it will be added to the left if the value is less //added to the right if the value is greater void insert(int item, Node*& n) { if (n != nullptr) { if (item < n->data) { insert(item, n->left); } else { insert(item, n->right); } } else { n = new Node(item); } } };
Let me know if you have any improvements or comments!