sorted_binary_tree.c

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

typedef struct node {
    int value;
    struct node *left;
    struct node *right;
    struct node *parent;
} Node;


Node *make_node(int value, Node *left, Node *right, Node *parent){
    Node *Temp = malloc(sizeof(Node));

    Temp->value = value;
    Temp->left = left;
    Temp->right = right;
    Temp->parent = parent;

    return Temp;
}


typedef struct {
    Node *root;
    size_t size;
} Tree;


Tree *make_tree(Node *root){
    Tree *Temp = malloc(sizeof(Tree));

    Temp->root = root;
    root->parent = root;
    Temp->size = 1;

    return Temp;
}

void tree_add(Tree *T, Node *N){
    N->left = NULL;
    N->right = NULL;

    if(T->root == NULL){
        T->root = N;
        T->size = 1;
        return;
    }

    Node *Temp = T->root;

    while(1){

        if(N->value > Temp->value){
            if(Temp->right == NULL){
                Temp->right = N;
                N->parent = Temp;
                break;
            }

            Temp = Temp->right;

        } else {
            if(Temp->left == NULL){
                Temp->left = N;
                N->parent = Temp;
                break;
            }

            Temp = Temp->left;
        }
    }

    T->size++;
}


Node *tree_find(Tree *T, Node *N){

    Node *Temp = T->root;

    while(1){
        if(Temp == NULL)
            return NULL;

        int res = N->value - Temp->value;

        if(res == 0)
            return Temp;
        else if(res > 0)
            Temp = Temp->right;
        else
            Temp = Temp->left;
    }
}

void print_subtrees(Node *N){

    if(N->left != NULL)
        print_subtrees(N->left);

    printf("%d ", N->value);

    if(N->right != NULL)
        print_subtrees(N->right);
}



void remove_subtrees(Node *N){

    if(N->left != NULL)
        remove_subtrees(N->left);
    if(N->right != NULL)
        remove_subtrees(N->right);

    if(N->parent->left == N) N->parent->left = NULL;
    else if(N->parent->right == N) N->parent->right = NULL;

    free(N);
}




int main(){

    Node *N = make_node(10, NULL, NULL, NULL);
    Tree *T = make_tree(N);

    srand(time(0));

    for(int i = 5 ; i < 15; i++)
        tree_add(T, make_node(rand()%50, NULL, NULL, NULL));


    Node *N1 = tree_find(T, &(Node){.value=123, .left=NULL, .right=NULL, .parent=NULL});

    if(N1 == NULL)
        printf("Not Found!\n----\n");

    Node *N2 = tree_find(T, &(Node){.value=10, .left=NULL, .right=NULL, .parent=NULL});

    if(N2 != NULL)
        printf("Found!\nvalue: %d\nleft: %d\nright: %d\nparent: %d\n----\n",
               N2->value, N2->left->value, N2->right->value, N2->parent->value);

    print_subtrees(T->root);
    printf("\n");


    remove_subtrees(T->root);

    return 0;

}