Binary Search Tree
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189
#include <iostream>
using namespace std;
struct node{
node* left;
node* right;
int value;
};
class BST{
public:
node* Head = NULL;
node* tmp;
BST(int val){
Head = new node;
Head->value = val;
tmp = Head;
}
void insert(int val){
node *ptr = new node;
ptr->value = val;
if(!Head->value){
Head->value = val;
}
if(tmp->right == NULL && tmp->left == NULL){
if(tmp->value > val){ //value is greater
tmp->right = ptr;
ptr = NULL;
delete ptr;
return;
}
if(tmp->value < val){ //value is less
tmp->left = ptr;
ptr = NULL;
delete ptr;
return;
}
} //both sides empty and there is a value there
if(tmp->value > val){
if( tmp->left) //there's a left
{
tmp = tmp->left; //go left
insert(val); //check
}
else{
tmp->left = ptr;//insert on left
return; //end code
}
}//val is less and tmp has children
if(tmp->value < val){
if( tmp->right) //there's a right
{
tmp = tmp->right; //go right
insert(val); //check
}
else{
tmp->right = ptr; //insert at right
return; //end the code
}
}//val greater and tmp has children
} //inserts a value
void lookup(int val){
tmp = Head;
if(tmp->value == val){
cout << "found it!" << endl;
return;
}
while(tmp->value != val){
if(val > tmp->value){
tmp = tmp->right;
} //it's greater, go right
if(val < tmp->value){
tmp = tmp->left;
}//its less, go left
if(tmp == NULL){
cout << "couldn't find it!" << endl;
return;
} //if tmp is NULL that means there's nothing there.
} //will keep going until it's found or if it doesn't exist
cout << "found it!" << endl; //while loop stopped and it found the value!
return;
}//finds a value
void Remove(int val){
if(!Head){
cout << "Empty already";
return;
}//head is empty, end.
node* parent = NULL; //create parent pointer
tmp = Head; //this is what will find the value
while(tmp){
if(val < tmp->value){
parent = tmp;
tmp = tmp->left;
cout << left << endl;
}//go left
if(val > tmp->value){
parent = tmp;
tmp = tmp->right;
cout << left << endl;
} //go right
if(tmp->value == val){ //this means we found it
if(!tmp->right && !tmp->left && !parent){
Head = NULL;
delete tmp;
return;
} //root is being deleted without any children
if(tmp->right && !tmp->left){ //RIGHT VALUE BUT NO LEFT
if(!parent){
Head = Head->right;
delete tmp;
return;
}//gotta remove the root node.
else{
if(parent->value > tmp->value){
parent->left = tmp->right;
delete tmp;
return;
} //it's on the left of parent
else{
parent->right = tmp->right;
delete tmp;
return;
} //it's on the right of the parent
}//not the root node
}//if it has a right value but no left
if(tmp->left && !tmp->right){//LEFT VALUE BUT NO RIGHT
if(!parent){
Head = Head->left;
delete tmp;
return;
}//its the root
if(parent->value > tmp->value){
parent->left = tmp->left;
delete tmp;
return;
}//less than parent, its on the left
if(parent->value < tmp->value){
parent->right = tmp->right;
delete tmp;
return;
}//greater than parent, its on the right
}//if it has a left value but no right
if(tmp->right && tmp->left){
node* repl = tmp->left;
while(repl->right){
repl = repl->right;
}
tmp->value = repl->value;
delete repl;
}//if it has both a right and a left value
}
}
}
};
int main() {
BST Tree(12);
Tree.Remove(12);
cout << "Hello World!";
return 0;
}
Cpp
INFO