Kolokwium2_Drzewo_BST

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

struct tree_node{
    int key;
    char value;
    struct tree_node *left_child, *right_child;
};

void add_node_recursive(struct tree_node **root, int key, char value)
{
    if(*root == NULL){
        *root = (struct tree_node*)malloc(sizeof(struct tree_node));
        if(*root){
            (*root)->key = key;
            (*root)->value = value;
            (*root)->left_child = (*root)->right_child = NULL;
        }
    }
    else{
        if((*root)->key >= key)
            add_node_recursive(&(*root)->left_child, key, value);
        else
            add_node_recursive(&(*root)->right_child, key, value);
    }
}

void add_node_with_iteration(struct tree_node **root, int key, int value)
{
    while(*root != NULL){
        if((*root)->key >= key)
            root = &(*root)->left_child;
        else
            root = &(*root)->right_child;
    }
    *root = (struct tree_node*)malloc(sizeof(struct tree_node));

    if(*root){
        (*root)->key = key;
        (*root)->value = value;
        (*root)->left_child = (*root)->right_child = NULL;
    }
}

struct tree_node *isolate_predecessor(struct tree_node **root)
{
    while(*root && (*root)->left_child)
        root = &(*root)->right_child;
    struct tree_node *predececssor = *root;
    if(*root)
        *root = (*root)->left_child;
    return predececssor;
};

void delete_node(struct tree_node **root, int key)
{
    while(*root && (*root)->key != key){
        if((*root)->key > key)
            root = &(*root)->left_child;
        if((*root)->key < key)
            root = &(*root)->right_child;
    }
    if(*root){
        struct tree_node *node = *root;
        if(!node->left_child)
            *root = (*root)->right_child;
        else if(!node->right_child)
            *root = (*root)->left_child;
        else{
            node = isolate_predecessor(&(*root)->left_child);
            (*root)->key = node->key;
            (*root)->value = node->value;
        }
        free(node);
    }
}

void print_preorder(struct tree_node *root)
{
    if(root){
        printf("%d->%c  ", root->key, root->value);
        print_preorder(root->left_child);
        print_preorder(root->right_child);
    }
}

void print_inorder(struct tree_node *root)
{
    if(root){
        print_inorder(root->left_child);
        printf("%d->%c  ", root->key, root->value);
        print_inorder(root->right_child);
    }
}

void print_postorder(struct tree_node *root)
{
    if(root){
        print_postorder(root->left_child);
        print_postorder(root->right_child);
        printf("%d->%c  ", root->key, root->value);
    }
}

struct tree_node *find_minimum_recursive(struct tree_node *root)
{
    if(root && root->left_child)
        return find_minimum_recursive(root->left_child);
    else
        return root;
}

struct tree_node *find_minimum_with_iteration(struct tree_node *root)
{
    while(root && root->left_child)
        root = root->left_child;
    return root;
};

struct tree_node *find_maximum_recursive(struct tree_node *root)
{
    if(root && root->right_child)
        return find_maximum_recursive(root->right_child);
    else
        return root;
}

struct tree_node *find_maximum_with_iteration(struct tree_node *root)
{
    while(root && root->right_child)
        root = root->right_child;
    return root;
};

struct tree_node *find_node_recursive(struct tree_node *root, int key)
{
    if(root && root->key > key)
        return find_node_recursive(root->left_child, key);
    else if(root && root->key < key)
        return find_node_recursive(root->right_child, key);
    else
        return root;
}

struct tree_node *find_node_with_iteration(struct tree_node *root, int key)
{
    while(root){
        if(root->key == key)
            return root;
        if(root->key > key)
            root = root->left_child;
        else
            root = root->right_child;
    }
    return root;
};

void remove_tree_nodes(struct tree_node **root)
{
    if(*root){
        remove_tree_nodes(&(*root)->left_child);
        remove_tree_nodes(&(*root)->right_child);
        free(*root);
        *root = NULL;
    }
}

void external_or_internal(struct tree_node *root, int key)
{
    root = find_node_recursive(root, key);
    if(root->left_child || root->right_child)
        printf("Wezel o kluczu %d jest wezlem wewnetrznym\n", key);
    else
        printf("Wezel o kluczu %d jest wezlem zewnetrznym\n", key);
}

unsigned int height(struct tree_node *root)
{
    if(root == NULL)
        return 0;

    unsigned int left_height = height(root->left_child);
    unsigned int right_height = height(root->right_child);

    if(left_height > right_height)
        return left_height+1;
    else
        return right_height+1;
}

bool full_tree(struct tree_node *root)
{
    if(root == NULL)
        return true;
    if(root->left_child == NULL && root->right_child == NULL)
        return true;
    if(root->left_child && root->right_child)
        return (full_tree(root->left_child) && full_tree(root->right_child));
    return false;
}

int main(void)
{
    struct tree_node *root = NULL;

    add_node_recursive(&root, 3, 'A');
    add_node_with_iteration (&root, 1, 'B');
    add_node_recursive(&root, 7, 'C');
    add_node_with_iteration (&root, 8, 'D');

    puts("Preorder:");
    print_preorder(root);
    printf("\n");

    puts("Preorder:");
    print_inorder(root);
    printf("\n");

    puts("Postorder:");
    print_postorder(root);
    printf("\n\n");

    printf("Minimalny klucz: %d\n", find_minimum_recursive(root)->key);
    printf("Maksymalny klucz: %d\n", find_maximum_with_iteration(root)->key);
    printf("\n");

    external_or_internal(root, 3);
    external_or_internal(root, 1);
    printf("\n");

    printf("Wysokosc drzewa: %u\n", height(root));
    printf("\n");

    if(full_tree(root))
        puts("Drzewo jest pelne");
    else
        puts("Drzewo nie jest pelne");
    printf("\n");

    puts("Usuwanie '1':");
    delete_node(&root, 3);
    print_inorder(root);
    printf("\n");

    remove_tree_nodes(&root);
    return 0;
}