UNKNOWN //************************************** // Name: Binary search tree // Description:This is a simple implementation of Binary search tree. // By: Puneet Jindal // // // Inputs:None // // Returns:None // //Assumes:None // //Side Effects:None //This code is copyrighted and has limited warranties. //Please see http://www.Planet-Source-Code.com/xq/ASP/txtCodeId.13837/lngWId.3/qx/vb/scripts/ShowCode.htm //for details. //************************************** #include<iostream> using namespace std; class BST { private: struct node { int data; node *left,*right,*parent; }*p; node *make(int data = 0) { node *q = new(nothrow) node; q->data = data; q->left = q->right = q->parent = NULL; return q; } void in_order(node *q) { if(q == NULL) return ; else { in_order(q->left); cout<<q->data<<" "; in_order(q->right); } } void pre_order(node *q) { if(q == NULL) return ; else { cout<<q->data<<" "; pre_order(q->left); pre_order(q->right); } } void post_order(node *q) { if(q == NULL) return; else { post_order(q->left); post_order(q->right); cout<<q->data<<" "; } } public: BST() { p = NULL; } bool Insert(int data) { if(p == NULL) { p = make(data); return true; } else { node *q = p; while(true) { if(data < q->data) if(q->left == NULL) { q->left = make(data); q->left->parent = q; break; } else q = q->left; else if(data > q->data) if(q->right == NULL) { q->right = make(data); q->right->parent = q; break; } else q = q->right; else return false; } return true; } } void Display(int a = 0) { switch(a) { case 0: in_order(p); break; case 1: pre_order(p); break; case 2: post_order(p); break; default: cerr<<"Unknown procedure requested for Display()"<<endl; break; } } bool Delete(int data = 0,node *d = NULL)// Condition to delete root node is pending { node *q = NULL; if(d == NULL) { q = p; while(q != NULL && q->data != data) { if(q->data < data) q = q->right; else if(q->data > data) q = q->left; } } else q = d; if(q == NULL) return false; else { if(q->data == data) { if(q->left == NULL && q->right != NULL) { node *r = q->right; while(r->left != NULL) r = r->left; q->data = r->data; Delete(r->data,r); return true; } else if(q->left == NULL && q->right == NULL) { if(q->parent == NULL) p = NULL; else if(q == q->parent->left) q->parent->left = NULL; else if(q == q->parent->right) q->parent->right = NULL; delete q; return true; } else if(q->right == NULL && q->left != NULL) { if(q->parent == NULL) p = NULL; else if(q->parent->left == q) { q->parent->left = q->left; q->left->parent = q->parent; } else { q->parent->right = q->left; q->left->parent = q->parent; } delete q; return true; } else if(q->right != NULL && q->left != NULL) { node *r = q->right; while(r->left != NULL) r = r->left; q->data = r->data; Delete(r->data,r); return true; } } } return false; } }; int main() { BST t; t.Insert(5); t.Insert(3); t.Insert(2); t.Insert(4); t.Insert(7); t.Insert(6); t.Insert(8); t.Display(0); cout<<"\nNow "<<endl; t.Delete(5); t.Delete(3); t.Delete(2); t.Delete(4); t.Delete(7); t.Delete(6); t.Delete(8); t.Display(0); return 0; }