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

typedef struct treeNode {
      char key;                     // 데이터 필드
      struct treeNode *left;        // 왼쪽 서브 트리 링크 필드
      struct treeNode *right;       // 오른쪽 서브 트리 링크 필드
}treeNode;

typedef char element;   // char을 이진 탐색 트리 element의 자료형으로 정의

treeNode* insertNode(treeNode *p, char x)
{     // 포인터 p가 가리키는 노드와 비교화여 노드 x을 삽이하는 연산
      treeNode *newNode;
      if(p == null){
            newNode = (treeNode*)malloc(sizeof(treeNode));
            newNode -> key = x;
            newNode -> left = NULL;
            newNode -> right = NULL;
            return newNode;
      }
      else if(x < p-> key) p -> left = insetNode(p->left,x);
      else if(x > p-> key) p -> right = insertNode(p->right,x);
      else print("\n 이미 같은 키가 있습니다! \n");

      return p;
}

void deleteNode(treeNode *root, element key)
{     // root 노드부터 탐색하여 key 값과 같은 노드를 찾아 삭제하는 연산
      treeNode *parent, *p, *succ, *succ_parent;
      treeNode *child;

      parent = NULL:
      p = root;
      while((p != null) && (p-> key != key)){  // 삭제할 노드의 위치 탐색
            parent = p;
            if(key < p->key) p = p-> left;
            else p = p-> right;
      }
      if(p == NULL){    // 삭제할 노드가 없는 경우
            printf("\n 찾는 키가 이진 트리에 없습니다.");
            return;
      }

      // 삭제할 노드가 단말 노드인 경우
      if((p->left == NULL) && (p->right == NULL)){
            if(parent != NULL){
                  if(parent->left == p) parent->left = NULL;
                  else parent-> right = NULL;
            }
            else root = NULL;
      }

      // 삭제할 노드가 한개의 자식 노드를 가진 경우
      else if((p->left == NULL) || (p->right == NULL)){
            if(p->left != NULL) child = p->left;
            else child = p->right;

            if(parent != NULL){
                  if(parent->left == p) parent ->left = child;
                  else parent->right = child;
            }
            else root = child;
      }

      // 삭제할 노드가 두개의 자식을 가진 경우
      else{
            succ_parent = p;
            succ = p->left;
            while(succ->right != NULL){
                  succ_parent = succ;
                  succ = succ->right;
            }
            if(succ_parent->left == succ) succ_parent->left = succ->left;
            else succ_parent->right = succ->left;
            p->key = succ->key;
            p = succ;
      }
      free(p);
}

      treeNode* searchBST(treeNode* root, char x)
      {     // 이진 탐색 트리에서 키값이 x인 노드의 위치를 탐색하는 연산
            treeNode* p;
            p = root;
            while(p != null){
                  if(x < p->key) p = p->left;
                  else if (x == p->key) return p;
                  else p = p->right;
            }
            printf("\n 찾는 키가 없습니다.");
            return p;
      }
      void displayInorder(treeNode* root)
      {     // 이진 탐색 트리에서 중위 순회 화면서 출력하는 연산
            if(root){
                  displayInorder(root -> left);
                  displayInorder(root -> right);
            }
      }