C - BST

#include <stdio.h>

struct bst
{
    struct bst * parent;
    struct bst * left_node;
    struct bst * right_node;
    int key;
};

int get_height(struct bst *tree)
{
    if(tree == NULL)
        return 0;
    int left_height = get_height(tree->left_node);
    int right_height = get_height(tree->right_node);
    if(left_height > right_height)
        return left_height + 1;
    else
        return right_height + 1;
}

void add_node(struct bst *tree, int key)
{
    short finished = 0;
    struct bst * tmp = tree;
    while(!finished)
    {
        if(key < tmp->key)
        {
            if(tmp->left_node != NULL)
                tmp = tmp->left_node;
            else
            {
                struct bst * new_node = (struct bst *)malloc(sizeof(struct bst));
                new_node->key = key;
                new_node->left_node = new_node->right_node = NULL;
                new_node->parent = tmp;
                tmp->left_node = new_node;
                finished = 1;
            }
        } else if(tmp->key < key) {
            if(tmp->right_node != NULL)
                tmp = tmp->right_node;
            else
            {
                struct bst * new_node = (struct bst *)malloc(sizeof(struct bst));
                new_node->key = key;
                new_node->left_node = new_node->right_node = NULL;
                new_node->parent = tmp;
                tmp->right_node = new_node;
                finished = 1;
            }
        } else {
            printf("Podana wartosc juz znajduje sie w drzewie");
            finished = 1;
        }
    }
}

void draw_vertically(struct bst * Tree, int level)
{
    if(!Tree)return;
    draw_vertically(Tree->left_node, level + 1);
    int i;
    for(i = 0; i < level * 5; i++)
        printf(" ");
    printf("%d\n\n", Tree->key);
    draw_vertically(Tree->right_node, level + 1);
}

int find_node(struct bst *Tree, int key)
{
    if(!Tree)
    {
        printf("Nie znaleziono podanego elementu");
        return -1;
    }
    if(key == Tree->key)
    {
        printf("%d", key);
        return 0;
    } else {
        printf("%d -> ", Tree->key);
        if(key < Tree->key)
            return 1 + find_node(Tree->left_node, key);
        else
            return 1 + find_node(Tree->right_node, key);
    }
}

struct bst * get_node(struct bst * Tree, int key)
{
    if(!Tree)return NULL;
    if(Tree->key == key)
        return Tree;
    if(key < Tree->key)
        return get_node(Tree->left_node, key);
    else
        return get_node(Tree->right_node, key);
}

int leaf_count(struct bst * Tree)
{
    if(!Tree)return 0;
    int x, y;
    if(!Tree->left_node && !Tree->right_node)
        return 1;
    else
    {
        x = leaf_count(Tree->left_node);
        y = leaf_count(Tree->right_node);
        return x + y;
    }
}

float avg_route(struct bst * Tree, int level)
{
    int x, y;
    if(!Tree)return 0;
    if(!Tree->left_node && !Tree->right_node)
        return level;
    else
    {
        x = avg_route(Tree->left_node, level + 1);
        y = avg_route(Tree->right_node, level + 1);
        return x + y;
    }
}

int find_next(struct bst * Tree, int key)
{
    Tree = get_node(Tree, key);
    if(!Tree)return -1;
    if(Tree->right_node)
    {
        struct bst *right = Tree->right_node;
        while(right->left_node)right=right->left_node;
        return right->key;
    }
    struct bst * tmp = Tree->parent;
    while(tmp && Tree == tmp->right_node)
    {
        Tree = tmp;
        tmp = tmp->parent;
    }
    if(tmp)return tmp->key;
    else return -1;
}

int main()
{
    struct bst Tree;
    struct bst * TreePtr = &Tree;
    short empty = 1;
    int option = -1;
    int key;
    int height, i, j, spaces;
    while(option != 0)
    {
        printf("Wybierz opcje:\n");
        printf("1) Dodaj element do drzewa\n");
        printf("2) Rysuj drzewo\n");
        printf("3) Znajdz element\n");
        printf("4) Oblicz ilosc lisci w drzewie\n");
        printf("5) Znajdz nastepnik wybranego elementu\n");
        printf("6) Oblicz srednia dlugosc sciezek z korzenia do lisci\n\n");
        printf("0) Zakoncz program\n\n");
        printf("Wybor: ");
        scanf("%d", &option);
        if(option == 1)
        {
            printf("Podaj wartosc do dodania: ");
            scanf("%d", &key);
            if(empty)
            {
                Tree.key = key;
                Tree.parent = Tree.left_node = Tree.right_node = NULL;
                empty = 0;
            }
            else
                add_node(TreePtr, key);
        }
        else if(option == 2)
        {
            draw_vertically(TreePtr, 0);
        }
        else if(option == 3)
        {
            if(empty)
                printf("\nDrzewo jest puste.");
            else
            {
                int x;
                printf("\nPodaj szukany element: ");
                scanf("%d", &x);
                printf("\nWyszukiwanie wartosci %d: ", x);
                x = find_node(TreePtr, x);
                printf("\nPodana wartosc zostala znaleziona na poziomie %d.", x);
                printf("\n\n");
            }
        } else if(option == 4) {
            int x = leaf_count(TreePtr);
            printf("\nLiczba lisci w drzewie wynosi: %d.\n\n", x);
        } else if(option == 5) {
            int s, y;
            printf("Podaj element: ");
            scanf("%d", &s);
            y = find_next(TreePtr, s);
            printf("\nNastepnik elementu %d jest %d\n\n", s, y);
        } else if(option == 6) {
            float x = avg_route(TreePtr, 0);
            printf("\nSrednia dlugosc sciezek wynosi %f.\n\n", x/leaf_count(TreePtr));
        }
    }
    return 0;
}