Binary Search Tree

#include <iostream> using namespace std; class Node { public: int data; Node * left; Node * right; Node(int key); Node(); ~Node(); }; Node::Node(int key) { this->data = key; this->left = NULL; this->right = NULL; } Node::Node() { } Node::~Node() { } class BST { public: Node * root; BST(); ~BST(); void insertBST(int value); void deleteBST(int value); }; BST::BST() { this->root = NULL; } void recursiveInsert(Node *& root, Node * newPtr) { if (root == NULL) { root = newPtr; } else { if (newPtr->data < root->data) { recursiveInsert(root->left, newPtr); } else { recursiveInsert(root->right, newPtr); } } } void BST::insertBST(int value) { Node *newPtr = new Node(value); recursiveInsert(this->root, newPtr); } void recursiveDelete(Node *& root, int value) { if (root == NULL) { return; } else { if (value < root->data) { recursiveDelete(root->left, value); } else if (value > root->data) { recursiveDelete(root->right, value); } else { // Deleted node found - Test for leaf node if (root->left == NULL) { Node * dltPtr = root; root = root->right; delete dltPtr; } else if (root->right == NULL) { Node * dltPtr = root; root = root->left; delete dltPtr; } else { // Deleted node is not a leaf. // Find largest node on left subtree Node * dltPtr = root->left; while (dltPtr->right != NULL) { dltPtr = dltPtr->right; } // Node found. Move data and delete leaf node root->data = dltPtr->data; recursiveDelete(root->left, dltPtr->data); } } } } void BST::deleteBST(int value) { recursiveDelete(this->root, value); } void preOrder(Node * root) { if (root != NULL) { cout << root->data << " "; preOrder(root->left); preOrder(root->right); } } int main() { cout << "Binary Search Tree" << endl; BST * myTree = new BST(); myTree->insertBST(15); myTree->insertBST(7); myTree->insertBST(1); myTree->insertBST(11); myTree->insertBST(9); myTree->insertBST(13); myTree->insertBST(20); preOrder(myTree->root); cout << endl; myTree->deleteBST(7); preOrder(myTree->root); cout << endl; return 0; }