113 lines
2.5 KiB
C++
113 lines
2.5 KiB
C++
#include <iostream>
|
|
|
|
struct node{
|
|
int val;
|
|
struct node* left_child;
|
|
struct node* right_child;
|
|
};
|
|
|
|
node* initialise_BST_node(int val);
|
|
void print_BST(node* root);
|
|
void delete_BST(node* root);
|
|
void insert(node* root, int val);
|
|
void delete_node(node* root, int val, node* prev_node);
|
|
|
|
int main(){
|
|
node* root = initialise_BST_node(5);
|
|
insert(root, 3);
|
|
insert(root, 10);
|
|
insert(root, 4);
|
|
insert(root, 8);
|
|
insert(root, 14);
|
|
insert(root, 1);
|
|
print_BST(root);
|
|
std::cout << std::endl;
|
|
delete_node(root, 8, NULL);
|
|
print_BST(root);
|
|
std::cout << std::endl;
|
|
delete_BST(root);
|
|
}
|
|
|
|
node* initialise_BST_node(int val){
|
|
node* root = new node();
|
|
root->val = val;
|
|
root->left_child = NULL;
|
|
root->right_child = NULL;
|
|
return root;
|
|
}
|
|
|
|
void print_BST(node* root){
|
|
if (root->left_child != NULL)
|
|
print_BST(root->left_child);
|
|
std::cout << root->val << " ";
|
|
if (root->right_child != NULL)
|
|
print_BST(root->right_child);
|
|
}
|
|
|
|
void delete_BST(node* root){
|
|
if (root->left_child != NULL)
|
|
delete_BST(root->left_child);
|
|
if (root->right_child != NULL)
|
|
delete_BST(root->right_child);
|
|
delete root;
|
|
}
|
|
|
|
void insert(node* root, int val){
|
|
if (val == root->val)
|
|
return;
|
|
|
|
if (val < root->val){
|
|
if (root->left_child != NULL)
|
|
insert(root->left_child, val);
|
|
else{
|
|
node* new_node = initialise_BST_node(val);
|
|
root->left_child = new_node;
|
|
}
|
|
}else{
|
|
if (root->right_child != NULL)
|
|
insert(root->right_child, val);
|
|
else{
|
|
node* new_node = initialise_BST_node(val);
|
|
root->right_child = new_node;
|
|
}
|
|
}
|
|
}
|
|
|
|
void delete_node(node* root, int val, node* prev_node){
|
|
if (root->left_child != NULL && val < root->val)
|
|
delete_node(root->left_child, val, root);
|
|
if (root->right_child != NULL && val > root->val)
|
|
delete_node(root->right_child, val, root);
|
|
|
|
if (root->val == val){
|
|
node* replacing_node = NULL;
|
|
if (root->left_child != NULL && root->left_child != NULL){
|
|
replacing_node = root->right_child;
|
|
while (replacing_node->left_child != NULL){
|
|
replacing_node = replacing_node->left_child;
|
|
}
|
|
}
|
|
else if (root->left_child != NULL)
|
|
replacing_node = root->left_child;
|
|
else if (root->right_child != NULL)
|
|
replacing_node = root->right_child;
|
|
|
|
if (replacing_node != NULL){
|
|
replacing_node->left_child = root->left_child;
|
|
replacing_node->right_child = root->right_child;
|
|
}
|
|
|
|
if (prev_node != NULL){
|
|
if (prev_node->left_child == root)
|
|
prev_node->left_child = replacing_node;
|
|
if (prev_node->right_child == root)
|
|
prev_node->right_child = replacing_node;
|
|
}
|
|
delete root;
|
|
}
|
|
}
|
|
|
|
|
|
|
|
|