#include "BinarySearchTree.h"
BSTNode * BST_CreateNode(Data data)
{
    BSTNode * BST = (BSTNode *)malloc(sizeof(BSTNode)); //최초의 루트노드를 동적메모리 할당하기.
    BST->data = data;
    BST->Left = NULL;
    BST->Right = NULL;
    return BST;  //루트노드 반환.
}
BSTNode * BST_SearchNode(BSTNode * Tree, Data data)
{
    if (Tree == NULL) // 현재노드가 없는 경우, 반환.
        return NULL;

    if (Tree->data > data)  //해당원소가 현재노드보다 작을경우.
        return BST_SearchNode(Tree->Left, data);    //현재노드의 Left로 탐색시작.
    else if (Tree->data < data)    //해당원소가 현재노드 보다 클 경우.
        return BST_SearchNode(Tree->Right, data);   //현재노드의 right로 탐색시작.
    if (Tree->data == data)     //해당 원소를 찾았을 경우,
        return Tree;
    else //찾고자하는 원소가 없는경우, 예외처리
    {
        printf("찾고자하는 원소가 없음 !\n");
        exit(-1);
    }
}
BSTNode * BST_SearchMinNode(BSTNode * Tree)
{
    if (Tree == NULL)   //트리가 존재하지 않는경우..
        return NULL;

    //트리의 가장작은값은 루트노드를 기준으로 제일 왼쪽에 존재하므로, 제일 왼쪽의 원소가 존재한다면 계속해서 호출하기.
    if (Tree->Left != NULL)
        return BST_SearchMinNode(Tree->Left);
    return Tree;
}
BSTNode * BST_RemoveNode(BSTNode * Tree, BSTNode * Parent, Data data)
{
    BSTNode * Removed = NULL;
    if (Tree == NULL)
        return NULL;
    if (Tree->data < data) //제거할 원소가 해당노드보다 클 경우, 오른쪽으로 호출하기.
        return BST_RemoveNode(Tree->Right, Tree, data); //호출 시 오른쪽노드, 오른쪽노드의 부모는 현재 Tree가 되며, 값은 그대로 적기.
    else if (Tree->data > data) //제거할 원소가 해당노드보다 작은경우, 왼쪽으로 호출하기.
        return BST_RemoveNode(Tree->Left, Tree, data); //호출 시 왼쪽노드, 왼쪽노드의 부모는 현재 Tree가 되며, 값은 그대로 적기.
    else  // 제거할 노드를 찾은경우.
    {
        Removed = Tree; //제거할 노드를 마지막에 반환하기 위해 LRemoved 값에 넣어준다.

        if (Tree->Left == NULL && Tree->Right == NULL) //제거할 노드의 자식노드들이 없는경우(단말노드일 경우)
        {
            if (Parent->Left == Tree) //제거할 단말노드가 부모의 Left값 인지 확인하기.
                Parent->Left = NULL; //제거할 단말노드가 부모의 Left값이면, 부모의 Left = NULL이 되어야 함.

            else //제거할 단말노드가 부모의 Right값이면, 부모의 Right = NULL이 되어야 함.
                Parent->Right = NULL; //제거할 단말노드가 부모의 Right값이면, 부모의 RIght = NULL이 되어야 함.
        }
        else // 제거할 노드가 단말노드가 아닐경우,
        {
            if (Tree->Left != NULL && Tree->Right != NULL) //제거할 노드의 자식이 2명인 경우
            {
                BSTNode * delNode = BST_SearchMinNode(Tree->Right); //제거할 노드의 오른쪽 자식에서 최소값인 노드를 찾기.
                delNode = BST_RemoveNode(Tree, NULL, delNode->data);   //delNode에는 오른쪽 노드의 최소값이 제거됨과 동시에 반환된다.
                /*오른쪽 자식중 최소값인 노드를 제거하고, 이노드의 값을 제거할 노드의 데이터에 삽입한다.
                 * (실제로는 제거할노드는 제거되지않으며, 오른쪽 자식의 최소값을 제거하므로써 불필요한 과정을 생략할 수 있다.)
                 * 그러면 이진트리의 규칙(왼쪽자식의 원소 < 오른쪽자식의 원소)을 지킬수있다.
                 */
                 Tree->data = delNode->data;  //최소값을 가진노드의 값을 제거할 노드(실제로는 제거되지 않는 노드임)에 붙여넣기.
                 Removed = NULL;
            }
            else //제거할 노드의 자식이 하나인 경우
            {
                //제거할 노드에 매달린 하나의 자식을 부모의 자식으로 옮기기위해
                //매달린 하나의 노드를 RNode에 삽입
                BSTNode * RNode = Tree;
                if (RNode->Left != NULL) //제거할 노드에 매달린 하나의 자식이 왼쪽노드인경우.
                    RNode = RNode->Left; //제거할 노드에 매달린(Left) 하나의 자식을 Rnode로 삽입.

                else // 제거할 노드에 매달린 하나의 자식이 오른쪽 노드인경우
                    RNode = RNode->Right;  //제거할 노드에 매달린(Right) 하나의 자식을 Rnode로 삽입
                if (Parent->Right == Tree) //제거할 노드가 부모의 오른쪽노드에 해당하는 경우
                    Parent->Right = RNode; //부모의 오른쪽노드에 제거할 노드의 자식값을 삽입하기.
                else   //제거할 노드가 부모의 왼쪽노드에 해당하는 경우
                    Parent->Left = RNode;  //부모의 왼쪽노드에 제거할 노드의 자식값을 삽입하기.
            }
        }
    }
    return Removed;
}
void BST_InsertNode(BSTNode * Tree, BSTNode * Child) //루트노드를 기준으로 삽입된 노드의 위치를 적절히 삽입하기.
{
    if (Tree->data > Child->data) //삽입될 노드가 현재노드의 값보다 작은경우(왼쪽으로 탐색시작)
    {
        if (Tree->Left != NULL) // 현재노드의 왼쪽노드의 값이 존재하는경우, 왼쪽노드를 기준으로 탐색.
            BST_InsertNode(Tree->Left, Child);
        else //현재노드의 왼쪽노드가 존재하지 않는경우, 현재노드의 왼쪽자식으로 삽입.
            Tree->Left = Child;
    }
    else  //삽입될 노드가 현재노드의 값보다 큰경우(오른쪽으로 탐색시작)
    {
        if (Tree->Right != NULL) //현재노드의 오른쪽노드의 값이 존재하는 경우, 오른쪽노드를 기준으로 탐색.
            BST_InsertNode(Tree->Right, Child);
        else //현재노드의 오른쪽 자식이 존재하지 않는 경우, 현재노드의 오른쪽 자식으로 삽입.
            Tree->Right = Child;
    }
}
void BST_DestroyNode(BSTNode * Node)
{
    Node = NULL;  //댕글링 포인터를 방지하기위해서 NULL삽입
    free(Node);  //동적메모리 해제, 포인터변수 Node 는 여전히 해제된 메모리의 시작주소를 가지고있으므로,
    /* 댕글링 포인터란?
     * 댕글링 포인터에 접근하여 가리키는 주소의 데이터를 저장하거나 읽으려고 시도한다면 프로그램은 에러를 내면서 종료
     * 여기서는 BST_InorderPrintTree에서 재귀호출을 통해서 데이터를 읽으려고 시도할 경우, free()함수로 메모리를 할당하지만,
     * 이 Node란 포인터변수는 이미 할당된주소를 가리키므로 NULL값을 채워서 방지해야 한다!
     *
     */
}
void BST_DestroyTree(BSTNode * Tree)
{
    if (Tree == NULL)
        return;
    if (Tree->Left != NULL)
        BST_DestroyTree(Tree->Left);
    if (Tree->Right != NULL)
        BST_DestroyTree(Tree->Right);
    printf("%d제거!\n", Tree->data);
    Tree->Right = NULL;
    Tree->Left = NULL;
    BST_DestroyNode(Tree);
}
void BST_InorderPrintTree(BSTNode * Tree)
{
    if (Tree != NULL)
    {
        BST_InorderPrintTree(Tree->Left);
        printf("%d ", Tree->data);
        BST_InorderPrintTree(Tree->Right);
    }
}