이 진 트 리 (데이터 구조)

/*************************************************************************
    > File Name: tree.c
    > Author: mrhjlong
    > Mail: [email protected] 
    > Created Time: 2016 05 07      09 57 04 
 ************************************************************************/

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

typedef int type_t;

typedef struct node
{
    type_t data;

    struct node *left;
    struct node *right;
}Node;

//    
Node *node_create(type_t data)
{
    Node *p = (Node *)malloc(sizeof(Node));

    p->data = data;
    p->left = NULL;
    p->right = NULL;

    return p;
}

//    
void tree_in_order(Node *tree)
{
    if(tree == NULL)
        return;
    else
    {
        tree_in_order(tree->left);
        printf("in: %d
", tree->data);
        tree_in_order(tree->right);
    }
}

//    
void tree_pre_order(Node *tree)
{
    if(tree == NULL)
        return;
    else
    {
        printf("pre: %d
", tree->data);

        tree_pre_order(tree->left);
        tree_pre_order(tree->right);
    }
}

//    
void tree_post_order(Node *tree)
{
    if(tree == NULL)
        return;
    else
    {
        tree_post_order(tree->left);
        tree_post_order(tree->right);
        printf("next: %d
", tree->data);
    }
}

void node_insert_by_recursion(Node **pTree, Node *pNode)
{
    if(*pTree == NULL)
    {
        *pTree = pNode;
    }
    else if((*pTree)->data >= pNode->data)
    {
        node_insert_by_recursion(&((*pTree)->left), pNode);
    }
    else
    {
        node_insert_by_recursion(&((*pTree)->right), pNode);
    }
}

void node_insert(Node **pTree, Node *pNode)
{
    if(*pTree == NULL)
    {
        *pTree = pNode;
    }
    else
    {
        Node *p = *pTree;
        Node *pre = p;
        while(p != NULL)
        {
            pre = p;
            if(pNode->data <= p->data)
                p = p->left;
            else
                p = p->right;
        }

        if(pNode->data <= pre->data)
        {
            pre->left = pNode;
        }
        else
        {
            pre->right = pNode;
        }
    }
}

//    
Node *tree_search_by_recursion(Node *tree, type_t data)
{
    if(tree == NULL)
    {
        printf("%d is not found!
", data);
        return NULL;
    }
    else if(tree->data == data)
    {
        return tree;
    }
    else if(data <= tree->data)
    {
        tree_search_by_recursion(tree->left, data);
    }
    else
    {
        tree_search_by_recursion(tree->right, data);
    }
}

Node *tree_search(Node *tree, type_t data)
{
    Node *p = tree;
    while(p != NULL)
    {
        if(p->data == data)
            return p;
        else if(data <= p->data)
            p = p->left;
        else
            p = p->right;
    }

    return p;
}

//      
int tree_height(Node *tree)
{
    int left = 0;
    int right = 0;

    if(tree == NULL)
        return 0;
    else
    {
        left = 1 + tree_height(tree->left);
        right = 1 + tree_height(tree->right);
        return (left > right ? left : right);
    }
}

//     
void tree_destroy(Node **pTree)
{
    if(*pTree == NULL)
        return;
    else
    {
        tree_destroy(&((*pTree)->left));
        tree_destroy(&((*pTree)->right));
        free(*pTree);
        *pTree = NULL;
    }
}

//    
void node_delete(Node **pTree,type_t data)
{
    Node *pFind = *pTree;
    Node *pParent = NULL;

    //             
    while(pFind != NULL)
    {
        if(pFind->data == data)
            break;
        else if(data < pFind->data)
        {
            pParent = pFind;
            pFind = pFind->left;
        }
        else
        {
            pParent = pFind;
            pFind = pFind->right;
        }
    }

    if(pFind == NULL)
        return;
    else if(pFind->left == NULL || pFind->left->right == NULL)
    {
        if(pParent == NULL)
        {
            *pTree = pFind->right;
        }
        else
        {
            if(pParent->left == pFind)
                pParent->left = pFind->right;
            else
                pParent->right = pFind->right;
        }
        free(pFind);
        return;
    }
    else
    {
        pParent = pFind->left;
        Node *pos = pParent->right;
        while(pos->right != NULL)
        {
            pParent = pos;
            pos = pos->right;
        }
        pParent->right = pos->left;
        pFind->data = pos->data;
        free(pos);
        return;
    }


}


int main()
{
    Node *tree = NULL;
    int a[] = {45, 23, 65, 100, 29, 55, 89, 10, 3, 43, 36};
    int i = 0;
    Node *p = NULL;

    for(i = 0; i < sizeof(a) / sizeof(a[0]); i++)
    {
        p = node_create(a[i]);
        node_insert(&tree, p);
    }

//  tree_destroy(&tree);
    Node *pSea = tree_search(tree, 36);
    if(pSea != NULL)
    {
        printf("search: %d
", pSea->data);
        printf("pSea: %p
", pSea);
        printf("pNode: %p
", p);
    }
    printf("height: %d
", tree_height(tree));

    node_delete(&tree, 29); 

    tree_in_order(tree);
    printf("
");
    tree_pre_order(tree);
    printf("
");
    tree_post_order(tree);

    return 0;
}