trees
unknown
aql
3 years ago
2.8 kB
3
Indexable
#include<iostream> #include<conio.h> using namespace std; class TNode { public: int data; TNode* left; TNode* right; TNode(); TNode(int); }; class BST { public: TNode* root; BST(); void insert(TNode*, int); //to insert a node of given value void delete_node(TNode*, int); //to search and delete a node of given value bool isEmpty(); //to check if the BST is empty or not TNode* getParent(TNode*, int); //to return the parent of a given node }; TNode::TNode() { this->left = NULL; this->right = NULL; } TNode::TNode(int a) { this->data = a; this->left = NULL; this->right = NULL; } BST::BST() { this->root = NULL; } void BST::insert(TNode* root, int key) { TNode* curr = root; TNode* parent = NULL; if (root == NULL) { this->root = new TNode(key); return; } while (curr != NULL) { parent = curr; if (key < curr->data) curr = curr->left; else curr = curr->right; } if (key < parent->data) { parent->left = new TNode(key); } else { parent->right = new TNode(key); } } void BST::delete_node(TNode* root, int key) { TNode* curr = root; TNode* prev = NULL; while (curr != NULL && curr->data != key) { prev = curr; if (key < curr->data) curr = curr->left; else curr = curr->right; } if (curr == NULL) { cout << "Key " << key << " Not Found In The BST.\n"; return; } if (curr->left == NULL || curr->right == NULL) { TNode* newCurr; if (curr->left == NULL) newCurr = curr->right; else newCurr = curr->left; if (prev == NULL) { this->root = newCurr; return; } if (curr == prev->left) prev->left = newCurr; else prev->right = newCurr; delete curr; } else { TNode* p = NULL; TNode* temp; temp = curr->right; while (temp->left != NULL) { p = temp; temp = temp->left; } if (p != NULL) p->left = temp->right; else curr->right = temp->right; curr->data = temp->data; delete temp; } this->root = root; cout << "Node deleted" << endl; } bool BST::isEmpty() { if(this->root == NULL ) return true ; return false; } TNode* BST::getParent(TNode* root, int key ) { if (root == NULL ) { return NULL ; } TNode* p = root ; if (p ->left == NULL && p ->right == NULL ) return NULL ; if (p ->left != NULL && p ->data > key ) { p = p ->left; if (p ->left ->data == key ) return p; } if (p ->right != NULL && p ->data < key ) { p =p->right; if (p->right->data == key) return p; } if (p->left != NULL && p->right != NULL) { if (p->data < key) p = p->right; else p = p->left; } return p; } int main() { }
Editor is loading...