/*
        이원탐색 트리
        레벨 순회 구현
        노드 삭제 - 자식이 1개 또는 0개인 노드만을 삭제

        레벨 순회를 위해 이원탐색 트리와 트리를 가리키는 포인터 배열 구조 동시에 입력

        데이터 입력 58 60 43 28 47 79 84 32 59
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#define _MAX_IDX_ 50
#define _DE puts("A");

typedef struct _node{
        int data;
        struct _node *left;
        struct _node *right;
}treeNode;

typedef struct _tarray{
        treeNode *key;
}tarray;

treeNode *insertKey(treeNode *p, tarray *ps, int n, int loc){
        treeNode *newNode = NULL;
        if(p == NULL){
                newNode=(treeNode*)malloc(sizeof(treeNode));
                newNode->data=n;
                newNode->left=NULL;
                newNode->right=NULL;
                puts("");
                int childLoc = loc;
                int parentLoc = childLoc/2;
                if(loc == 1){
                        printf("Root : %d\n", newNode->data);
                        (ps+1)->key=newNode;
                        return newNode;
                }
                else if(loc%2 == 0){
                        printf("Parent : %d\n", (ps+parentLoc)->key->data);
                        printf("%d's left child %d\n", (ps+parentLoc)->key->data, newNode->data);
                        (ps+loc)->key=newNode;
                        return newNode;
                }
                else{
                        printf("Parent : %d\n", (ps+parentLoc)->key->data);
                        printf("%d's right child %d\n", (ps+parentLoc)->key->data, newNode->data);
                        (ps+loc)->key=newNode;
                        return newNode;
                }
        }
        else if(n < p->data){
                loc*=2;
                p->left=insertKey(p->left, ps, n, loc);
                return p;
        }
        else if(n > p->data){
                loc=loc*2+1;
                p->right=insertKey(p->right, ps, n, loc);
                return p;
        }
        else{
                puts("Duplicated key value\n중복된 데이터가 존재합니다");
                return p;
        }
}

void insert(treeNode **root, tarray **ps, int n){
        *root=insertKey(*root, *ps, n, 1);
}

int wLeftMax(treeNode *p){
        if(p == NULL)
                return 0;
        int a = p->data;
        int b = wLeftMax(p->left);
        a<b?a=b:b;
        b = wLeftMax(p->right);
        return a<b?b:a;
}

void deleteNode(tarray *ps, int n, treeNode **root){
        for(int i = 0; i<_MAX_IDX_; ++i){       
                if((ps+i)->key != NULL){
                        if((ps+i)->key->data == n){
                                if((ps+(i*2))->key != NULL && (ps+(i*2+1))->key != NULL){
                                        // printf("(%d<-%d->%d)\n",(ps+(i*2))->key->data, (ps+i)->key->data, (ps+(i*2+1))->key->data);
                                        // puts("Error : Invalid Command\n자식이 두개인 노드 삭제 금지");
                                        int leftMax = wLeftMax((ps+i)->key->left);
                                        deleteNode(ps, leftMax, root);
                                        (ps+i)->key->data = leftMax;
                                        return;
                                }
                                else if((ps+(i*2))->key != NULL || (ps+(i*2+1))->key != NULL){
                                        if((ps+(i*2))->key != NULL){
                                                printf("%d's left child %d -> change location\n", (ps+i)->key->data, (ps+(i*2))->key->data);
                                                puts("Delete!");
                                                *(ps+i)->key=*(ps+(i*2))->key;
                                                (ps+(i*2))->key=NULL;

                                                if((ps+i)->key == (ps+1)->key){
                                                        printf("\nRoot : %d\n", (ps+i)->key->data);
                                                        return;
                                                }
                                                else{
                                                        (ps+(i/2))->key->left=(ps+i)->key;
                                                        printf("\nParent : %d\n", (ps+(i/2))->key->data);
                                                        printf("%d's left child %d\n", (ps+(i/2))->key->data, (ps+i)->key->data);
                                                }
                                        }
                                        else{
                                                printf("%d's right child %d -> change location\n", (ps+i)->key->data, (ps+(i*2+1))->key->data);
                                                puts("Delete!");
                                                *(ps+i)->key=*(ps+(i*2+1))->key;
                                                (ps+(i*2+1))->key=NULL;

                                                if((ps+i)->key == (ps+1)->key){
                                                        printf("\nRoot : %d\n", (ps+i)->key->data);
                                                        return;
                                                }
                                                else{
                                                        printf("\nParent : %d\n", (ps+(i/2))->key->data);
                                                        printf("%d's left child %d\n", (ps+(i/2))->key->data, (ps+i)->key->data);
                                                }
                                        }
                                        if((i/2)%2 == 0)
                                                (ps+(i/2))->key->left=(ps+(i*2))->key;
                                        else
                                                (ps+(i/2))->key->right=(ps+(i*2))->key;
                                        return;
                                }

                                else if(i == 1){
                                        printf("%d is root\n", (ps+i)->key->data);
                                        puts("Delete!");
                                        (ps+i)->key->data=NULL;
                                        (ps+i)->key=NULL;
                                        *root=NULL;
                                        puts("Tree is empty.");
                                        return;
                                }
                                else{
                                        printf("%d is leaf node\n", (ps+i)->key->data);
                                        (ps+i)->key->data=NULL;
                                        (ps+i)->key=NULL;
                                        if(i%2 == 0){
                                                (ps+(i/2))->key->left=NULL;
                                                printf("Parent : %d\n", (ps+(i/2))->key->data);
                                                printf("%d's left child NULL\n", (ps+(i/2))->key->data);
                                        }
                                        else{
                                                (ps+(i/2))->key->right=NULL;
                                                printf("Parent : %d\n", (ps+(i/2))->key->data);
                                                printf("%d's right child NULL\n", (ps+(i/2))->key->data);
                                        }
                                        return;
                                }
                        }
                }
        }
        puts("No such key value is found\n트리에 존재하지 않는 노드");
}

treeNode *find(treeNode *root, int n){
        treeNode *p = root;
        int cnt = 0;
        int prev = 0;
        int isRight = 0;

        while(p != NULL){
                ++cnt;
                if(n < p->data){
                        prev=p->data;
                        p=p->left;
                        isRight=0;
                }
                else if(n == p->data){
                        printf("\n%d회 검색 후 발견!\n", cnt);
                        if(prev == 0)
                                printf("Root %d\n", p->data);
                        else if(isRight == 1)
                                printf("%d's right child %d\n", prev, p->data);
                        else
                                printf("%d's left child %d\n", prev, p->data);
                        return p;
                }
                else{
                        prev=p->data;
                        p=p->right;
                        isRight=1;
                }
        }
        puts("No such key value is found\n트리에 존재하지 않는 노드");
        return p;
}

void printNode(treeNode *p){
        if(p != NULL){
                printf("(");
                printNode(p->left);
                printf("%d", p->data);
                printNode(p->right);
                printf(")");
        }
}

void printTree(treeNode *root){
        printf("LDR ");
        printNode(root);
        puts("");
}

int isLevel(tarray *ps){
        int currentLevel = 1;
        int depth = 0;
        int pre = 0;

        for(int i = 0; i<_MAX_IDX_; ++i){       
                if((ps+i)->key)
                        depth=currentLevel;
                if(i==(2*pre+1)){
                        ++currentLevel;
                        pre=i;
                }
        }

        return depth;   
}

void printTree_g(tarray *ps){
        int levelDepth = isLevel(ps);
        //
        int key = 1;
        int t = 0;
        int j = 0;
        int k = levelDepth;
        //

        for(int i = 1; i<=levelDepth; ++i, --k){
                for(t=0; t<pow(2.0,k); ++t){
                        printf("  ");
                }
                for(j=0; j<pow(2.0,i-1); ++j, ++key){
                        if((ps+key)->key)
                                printf("%d", (ps+key)->key->data);
                        else
                                printf("  ");
                        for(t=1; t<pow(2.0,k)*2; ++t){
                                printf("  ");
                        }
                }
                puts("");
        }
}


void printLevelPath(tarray *ps){
        int length = 0;

        for(int i = 0; i<_MAX_IDX_; ++i){
                if((ps+i)->key != NULL)
                        ++length;
        }
        printf("\nStart Level Path\n");
        printf("BST's size : %d\n", length);
        printf("(root)");
        for(i=0; i<_MAX_IDX_; ++i){     
                if((ps+i)->key != NULL){
                        if(--length == 0){
                                printf("%d",(ps+i)->key->data);
                                break;
                        }
                        else
                                printf("%d->",(ps+i)->key->data);
                }
        }
        puts("");
}

int main(void){
        treeNode *root = NULL;
        tarray *ps = NULL;
        unsigned int slct = 0;

        ps=(tarray*)malloc(sizeof(tarray*)*(int)_MAX_IDX_);
        for(int i = 0; i<_MAX_IDX_; ++i){
                (ps+i)->key = NULL;
        }
        (ps+0)->key=root;
//
        int key = NULL;
//

        while(slct!=5)
        {
                puts("\nMenu"); // Menu
                puts("=================");
                puts("1. Insert of BST's Node");
                puts("2. Delete of BST's Node");
                puts("3. Search of BST's Node");
                puts("4. Level Path");
                puts("5. Quit of Program");
                puts("=================");
                printf("Select : ");
                scanf("%d",&slct);

                switch(slct){
                        case 1: // 1. Insert of BST's Node
                                printf("Enter of Data : ");
                                scanf("%d", &key);
                                insert(&root, &ps, key); 
                                break;
                        case 2: // 2. Delete of BST's Node
                                printf("Enter of Data : ");
                                scanf("%d", &key);
                                deleteNode(ps, key, &root); 
                                break;
                        case 3: // 3. Search of BST's Node
                                printf("Enter of Data : ");
                                scanf("%d", &key);
                                find(root, key);
                                break;
                        case 4: // 4. Level Path
                                printTree(root);
                                printTree_g(ps);
                                printLevelPath(ps);
                                break;
                        case 5: // 5. Quit of Program
                                break;
                        default: 
                                puts("Error : Invalid command.");
                                break;
                }
        }

        return 0;
}