BST Tree in C BST Tree in C, creation of binary search tree in c, binary search tree deletion program in c, program to delete a node from binary search tree in c, binary tree insertion, binary search tree c code, insertion into binary tree, binary search tree using c, program on binary search tree using c
#include <stdio.h>
#include <stdlib.h>
struct BSTree{
int key;
struct BSTree *left;
struct BSTree *right;
struct BSTree *parent;
};
typedef struct BSTree node;
void add(node **root, int key){
if((*root)==NULL){
(*root)=(node*)malloc(sizeof(node));
(*root)->key=key;
(*root)->left=NULL;
(*root)->right=NULL;
(*root)->parent=NULL;
}
else{
if(key<(*root)->key){
add(&(*root)->left, key);
(*root)->left->parent=*root;
}
else if (key>(*root)->key){
add(&(*root)->right, key);
(*root)->right->parent=*root;
}
}
}
void delete(node **root, int key){
if(*root){
if(key < (*root)->key)
delete(&(*root)->left,key);
else if (key > (*root)->key)
delete(&(*root)->right, key);
else{
node *del = *root;
if(del->left==NULL){
if(del->right)
del->right->parent=(*root)->parent;
*root=del->right;
free(del);
}
else if (del->right==NULL){
del->left->parent=(*root)->parent;
*root=del->left;
free(del);
}
else{
node *x=NULL;
x=del->left;
node *y=NULL;
y=del;
while(x->right!=NULL){
y=x;
x=x->right;
}
int temp = x->key;
x->key=del->key;
del->key=temp;
if(y->key != del->key){
y->right=x->left;
if(y->right!=NULL)
y->right->parent=x->parent;
}
else{
y->left=x->left;
if(y->left!=NULL)
y->left->parent=x->parent;
}
free(x);
}
}
}
}
void showInOrder(node *root){
if(root){
showInOrder(root->left);
printf("%d ", root->key);
showInOrder(root->right);
}
}
node* find(node *root, int key){
if(root==NULL)
return NULL;
if(key>root->key)
return find(root->right, key);
else if(key<root->key)
return find(root->left, key);
else
return root;
}
node* min(node *root){
if(root==NULL)
return NULL;
if(root->left)
return min(root->left);
else
return root;
}
node* max(node *root){
if(root==NULL)
return NULL;
if(root->right)
return max(root->right);
else
return root;
}
node* successor(node *root, int key){
node *succ = NULL;
succ = find(root, key);
if(succ){
if(succ->right){
return min(succ->right);
}
node *temp=NULL;
temp = succ->parent;
while(temp && temp->left != succ){
succ = temp;
temp = temp->parent;
}
return temp;
}
printf("Podano zla liczbe!\n");
}
node* predecessor(node *root, int key){
node *prede = NULL;
prede = find(root, key);
if(prede){
if(prede->left){
return max(prede->left);
}
node *temp=NULL;
temp = prede->parent;
while(temp && temp->right != prede){
prede = temp;
temp = temp->parent;
}
return temp;
}
printf("Podano zla liczbe!\n");
}
int sum(node *root){
if(root==NULL)
return 0;
return root->key + sum(root->left) + sum(root->right);
}
void menu(){
printf("___________________________________DRZEWO BST__________________________________\n");
printf("Co chcesz zrobic?\n");
printf("1. Wyswietl drzewo\n");
printf("2. Dodaj wezel\n");
printf("3. Usun wezel\n");
printf("4. Wyswietl nastepnika\n");
printf("5. Wyswietl poprzednika\n");
printf("6. Wyszukaj wartosc\n");
printf("Aby zakonczyc wcisnij ESCAPE\n\n");
}
int main(){
int znak;
int option;
node *number=NULL;
node *root=NULL;
node *searched=NULL;
do{
menu();
znak = getch();
int x;
switch(znak){
case '1':
printf("Drzewo wyswietlone w kolejnosci In Order:\n");
showInOrder(root);
printf("\n\n");
break;
case '2':
printf("Podaj wartosc jaka chcesz dodac: ");
scanf("%d", &option);
printf("\n");
add(&root, option);
break;
case '3':
printf("Podaj wartosc jaka chcesz usunac: ");
scanf("%d", &option);
printf("\n");
delete(&root, option);
break;
case '4':
printf("Podaj wartosc, dla ktorej chcesz wyswietlic nastepnika: ");
scanf("%d", &option);
printf("\n");
number = successor(root, option);
if(number)
printf("Nastepnik wynosi: %d\n\n", number->key);
else
printf("Nastepnik nie istnieje!\n\n");
break;
case '5':
printf("Podaj wartosc, dla ktorej chcesz wyswietlic poprzednika: ");
scanf("%d", &option);
printf("\n");
number = predecessor(root, option);
if(number)
printf("Poprzednik wynosi: %d\n\n", number->key);
else
printf("Poprzednik nie istnieje!\n\n");
break;
case '6':
printf("Podaj wartosc, ktora chcesz wyszukac: ");
scanf("%d", &option);
printf("\n");
searched = find(root, option);
if(searched)
printf("Podana wartosc istnieje. Jej adres wynosi: %p\n\n", searched);
else
printf("Podana wartosc nie istnieje!\n\n");
break;
case '7':
x=sum(root);
printf("%d\n\n", x);
break;
}
}
while(znak != 27);
return 0;
}