알고리즘 스터디 3회차 - 이진트리(Binary Tree) 구현

#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
// BinaryTree with LinkedList
 
int size = 0;
 
typedef struct Tree_node *tree_pointer;
 
typedef struct Tree_node {
    int key;
    tree_pointer left;
    tree_pointer right;
}tree_node;
 
typedef struct binarytree {
    Tree_node *Root;
}binarytree;
 
tree_pointer CreateNode(int Key);
 
void Preorder(tree_pointer ptr) {
    if (ptr != NULL) {
        printf(" %d ", ptr->key);
        Preorder(ptr->left);
        Preorder(ptr->right);
    }
}
 
void Inorder(tree_pointer ptr) {
    if (ptr != NULL) {
        Inorder(ptr->left);
        printf(" %d ", ptr->key);
        Inorder(ptr->right);
    }
}
 
void Postorder(tree_pointer ptr) {
    if (ptr != NULL) {
        Postorder(ptr->left);
        Postorder(ptr->right);
        printf(" %d ", ptr->key);
    }
}
 
void NodeCount(tree_pointer ptr) {
    if (ptr != NULL) {
        size++;
        NodeCount(ptr->left);
        NodeCount(ptr->right);
    }
}
 
bool Is_There(binarytree *Target_Tree, int Item) {
    tree_node *cur = Target_Tree->Root;
    size = 0;
    NodeCount(cur);
    for(int i = 0; i<size; i++) {
        if (cur->key == Item) {
            return true;
        }
        if (cur->key < Item) {
            if (cur->left == NULL)
                return false;
            cur = cur->right;
        }
        else {
            if (cur->left == NULL)
                return false;
            cur = cur->left;
        }
    }
    return false;
}
 
void Tree_init(binarytree *Target_tree) {
    Target_tree->Root = NULL;
}
 
void Add_Node(binarytree *Target_tree, int Item) {
    tree_node *NewNode = (tree_node *)malloc(sizeof(tree_node));
    if (Target_tree->Root == NULL)
    {
        Target_tree->Root = NewNode;
        NewNode->left = NULL;
        NewNode->right = NULL;
        NewNode->key = Item;
        return;
    }
    if (Is_There(Target_tree, Item)) {
        printf("%d is exist already.\n", Item);
        return;
    }
    NewNode->left = NULL;
    NewNode->right = NULL;
    NewNode->key = Item;
    tree_node *cur = Target_tree->Root;
    while (1) {
        if (cur->key < Item)
        {
            if (cur->right == NULL) {
                cur->right = NewNode;
                return;
            }
            cur = cur->right;
        }
        else {
            if (cur->left == NULL) {
                cur->left = NewNode;
                return;
            }
            cur = cur->left;
        }
    }
}
 
int Delete_Node(binarytree *Target_tree, int Item) {
    tree_node *cur2 = NULL;
    tree_node *cur = Target_tree->Root;
    tree_node *par_parent = NULL;
    tree_node *parent = NULL;
    tree_node *child = NULL;
    tree_node *left_temp = NULL;
    int key_return = 0;
    if (!Is_There(Target_tree, Item)) {
        printf("%d is not exist\n", Item);
        return 0;
    }
    while (cur->key != Item) {
        if (Item > cur->key) {
            par_parent = parent;
            parent = cur;
            cur = cur->right;
        }
        else {
            par_parent = parent;
            parent = cur;
            cur = cur->left;
        }
    }
 
    // 자식노드가 없을 경우
    if (cur->left == NULL && cur->right == NULL) {
        key_return = cur->key;
        if (parent->left == cur) parent->left = NULL;
        if (parent->right == cur) parent->right = NULL;
        free(cur);
        return key_return;
    }
    // 자식노드가 하나 있을 경우
    if (cur->left == NULL || cur->right == NULL) {
        child = (cur->left != NULL) ? cur->left : cur->right;
 
        if (parent->left == cur) parent->left = child;
        else parent->right = child;
        key_return = cur->key;
        free(cur);
        return key_return;
    }
    // 자식노드가 둘 있을 경우
    if (cur->left != NULL && cur->right != NULL) {
        cur2 = cur;
        cur2 = cur2->right;
        if (cur2->left == NULL) {
            left_temp = cur->left;
            child = cur2;
            if (parent->right == cur) {
                parent->left = child;
                child->left = left_temp;
            }
            else {
                if (parent->left == cur) {
                    parent->left = child;
                    child->left = left_temp;
                }
                key_return = cur->key;
                free(cur);
                return key_return;
            }
            while (cur2->left != NULL) {
                parent = cur2;
                cur2 = cur2->left;
            }
            parent->left = NULL;
            cur->key = cur2->key;
            free(cur2);
        }
        return 0;
    }
}
 
int main(void) {
    int com, key, putin = 0;
 
    tree_pointer travelNode;
    tree_pointer one = CreateNode(1);
    tree_pointer two = CreateNode(2);
    tree_pointer three = CreateNode(3);
    tree_pointer four = CreateNode(4);
    tree_pointer five = CreateNode(5);
    tree_pointer six = CreateNode(6);
    tree_pointer seven = CreateNode(7);
    tree_pointer eight = CreateNode(8);
    tree_pointer nine = CreateNode(9);
 
    travelNode = (tree_node*)malloc(sizeof(tree_node));
 
    five->left = one;
    one->right = two;
    two->right = three;
    three->right = four;
 
    five->right = six;
    six->right = seven;
    seven->right = eight;
    eight->right = nine;
 
    travelNode = five;
 
    binarytree *list = (binarytree *)malloc(sizeof(binarytree));
    list->Root = five;
 
    while (1) {
        printf("\n ::::: Binary Tree :::::\n\n ::::: Travel command >>>\n [1] Preorder Traversal\n [2] Inorder Traversal\n [3] Postorder Traversal\n\n ::::: Modifying command >>>\n [4] Add Node\n [5] Delete Node\n [6] DELETE ALL NODE\n\n ::::: Select number :::::\n\n");
        scanf_s("%d", &com);
 
        switch (com) {
        case 1:
            printf("******\n\n");
            Preorder(travelNode);
            printf("\n\n******\n\n");
            break;
 
        case 2:
            printf("******\n\n");
            Inorder(travelNode);
            printf("\n\n******\n\n");
            break;
 
        case 3:
            printf("******\n\n");
            Postorder(travelNode);
            printf("\n\n******\n\n");
            break;
        case 4:
            printf("****** Please enter new item\n\n");
            scanf_s("%d", &key);
            Add_Node(list, key);
            printf("\n\n******\n\n");
            break;
        case 5:
            printf("****** Please enter delete item\n\n");
            scanf_s("%d", &key);
            Delete_Node(list, key);
            printf("\n\n******\n\n");
            break;
        case 6:
            printf("****** Delete All Node\n\n");
            Tree_init(list);
            break;
        default:
            printf("undefined command\n");
            break;
        }
    }
}
 
tree_pointer CreateNode(int Key) {
    tree_pointer newNode;
    newNode = (tree_node*)malloc(sizeof(tree_node));
 
    newNode->left = NULL;
    newNode->right = NULL;
    newNode->key = Key;
 
    return newNode;
}