이진트리(바이너리트리) 구현 예제

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

typedef struct Node
{
    struct Node *left;
    int num;
    struct Node *right;
}Node;

int menu(void);
void add(Node **root);
void del(Node **root);
void inorder(Node *root);
Node* search(Node *root, int num);
void insertNode(Node **root, int num);
void deleteNode(Node **root, int num);

int main(void)
{
    Node *root = NULL;

    while(1)
    {
        switch(menu())
        {
        case 1 :
            add(&root);
            break;
        case 2 :
            inorder(root);
            break;
        case 3 :
            del(&root);
            break;
        case 4 :
            return 0;
        }
    }

    return 0;
}

int menu(void)
{
    int n;

    printf("1. Addn");
    printf("2. Printn");
    printf("3. Deleten");
    printf("4. Quitn");
    printf("Input : ");
    scanf("%d", &n);

    return n;
}

void add(Node **root)
{
    int num;

    printf("Input Number : ");
    scanf("%d", &num);

    insertNode(root, num);
}

void del(Node **root)
{
    int num;

    printf("Input Number : ");
    scanf("%d", &num);

    deleteNode(root, num);
}

void inorder(Node *root)
{
    if(root)
    {
        inorder(root -> left);
        printf("%dn", root -> num);
        inorder(root -> right);
    }
}

Node* search(Node *root, int num)
{
    while(root)
    {
        if((root -> num) == num)
            return root;
        else if((root -> num) > num)
            root = root -> left;
        else
            root = root -> right;
    }
    return NULL;
}

void insertNode(Node **root, int num)
{
    Node *node1 = NULL;
    Node *node2 = *root;
    Node *newNode;

    while(node2)
    {
        if((node2 -> num) == num)
        {
            printf("Data exists alreadyn");
            return;
        }
        node1 = node2;
        if((node2 -> num) > num)
            node2 = node2 -> left;
        else
            node2 = node2 -> right;
    }

    newNode = (Node*)malloc(sizeof(Node));
    newNode -> num = num;
    (newNode -> left) = (newNode -> right) = NULL;

    if(node1)
    {
        if((node1 -> num) > num)
            node1 -> left = newNode;
        else
            node1 -> right = newNode;
    }
    else
        *root = newNode;
}

void deleteNode(Node **root, int num)
{
    Node *node1 = NULL;
    Node *node2 = *root;

    while(node2 && ((node2 -> num) != num))
    {
        node1 = node2;
        if((node2 -> num) > num)
            node2 = node2 -> left;
        else
            node2 = node2 -> right;
    }

    if(!node2)
    {
        puts("Data no foundn");
        return;
    }

    if(!(node2 -> left) && !(node2 -> right))
    {
        if(node1)
        {
            if((node1 -> left) == node2)
                node1 -> left = NULL;
            else
                node1 -> right = NULL;
        }
        else
            *root = NULL;
    }
    else if(!(node2 -> left) || !(node2 -> right))
    {
        Node *temp = (node2 -> left) ? (node2 -> left) : (node2 -> right);

        if(node1)
        {
            if((node1 -> left) == node2)
                node1 -> left = temp;
            else
                node1 -> right = temp;
        }
        else
            *root = temp;
    }
    else
    {
        Node *temp1 = node2;
        Node *temp2 = node2 -> right;

        while(temp2 -> left)
        {
            temp1 = temp2;
            temp2 = temp2 -> left;
        }

        if(temp1 -> left == temp2)
            temp1 -> left = temp2 -> right;
        else
            temp1 -> right = temp2 -> right;

        node2 -> num = temp2 -> num;
        node2 = temp2;
    }
    free(node2);
}