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

// 노드의 구조
typedef struct treeNode *treePointer;
typedef struct treeNode {
 char data;
 treePointer left, right;
} treeNode;

 

//* data를 만족하는 node와 그 노드의 부모 노드까지 찾아라.
//*
//* @param  node   현재 node
//* @param  data   찾고자 하는 data
//* @param  parent 현재 node의 부모 node - tree 중간에 insert가 된다면 필요.
//* @return        못찾으면 NULL, 찾으면 node 반환.
treePointer search(treePointer node, char data, treePointer* parent)
{
 if (node == NULL) {
  return NULL;
 }
 else {
  if (node->data == data) {
   return node;
  }
 }

 {
  treeNode *temp;

  *parent = node;
  if ((temp = search(node->left, data, parent))) {
   return temp;
  }
  *parent = node;
  if ((temp = search(node->right, data, parent))) {
   return temp;
  }
 }
}

//* preorder 출력함수
void preorder(treePointer node)
{
 if (node == NULL)
  return;
 printf("%c", node->data);
 preorder(node->left);
 preorder(node->right);
}

treePointer malloc_node(char data, treePointer left, treePointer right)
{
 treePointer node = (treePointer)malloc(sizeof(treeNode));
 if (node == NULL) {
  fprintf(stderr, "ERROR: fails to malloc\n");
  exit(0);
 }
 node->data = data;
 node->left = left;
 node->right = right;
 return node;
}

//* 삽입연산 함수
//*
//* data를 이진 탐색 트리 root에 삽입한다.
//* data가 이미 root안에 있으면 삽입되지 않는다.
//* 입력받는 3가지 경우 : [CASE1] 현재 노드가 비었다. [CASE2] data1노드x, data2노드o, 현재노드o. [CASE3] data1노드o, 현재노드o
void insert_node(treePointer* root, char data1, char key, char data2)
{
 treePointer current;
 treePointer parent = NULL;

 assert(key == 'F' || key == 'M');

 current = search(*root, data1, &parent);
 if (current) {
  // 자식을 검색해서 아빠, 엄마를 추가한다. [CASE3]
  //
  treePointer node = malloc_node(data2, NULL, NULL);
  current->left = key == 'F' ? node : current->left;
  current->right = key == 'M' ? node : current->right;
  return;
 }

 parent = NULL;
 current = search(*root, data2, &parent);
 if (current) {
  // 아빠, 엄마를 검색해서 자식을 추가한다. [CASE2]
  //  - 자식을 추가해야 하는 경우는 root가 부모일때.
  *root = malloc_node(data1, key == 'M' ? current : NULL, key == 'F' ? current : NULL);
  return;
 }

 // 둘다 검색안되면 tree가 빈 경우거나, 조건에 맞는 데이터가 없는 경우인데
 // 여기서는 tree가 빈 경우로만 생각한다. [CASE1]
 //
 {
  treePointer node = malloc_node(data2, NULL, NULL);
  *root = malloc_node(data1, key == 'F' ? node : NULL, key == 'M' ? node : NULL);
 }
}

 

//* 공통조상 노드를 찾아라.
treePointer find_sameparent(treePointer node, char data1, char data2, treePointer temp)
{
 if (node == NULL)
  return NULL;

 if (search(node->left, data1, &temp) && search(node->right, data2, &temp))
  return node;
 if (search(node->left, data2, &temp) && search(node->right, data1, &temp))
  return node;

 find_sameparent(node->left, data1, data2, &temp);
 find_sameparent(node->right, data1, data2, &temp);

}

 

//* data1과 data2의 관계를 출력하라
//* 콘솔창 : data1 - ? - data2를 입력받음
//* find_relation1 = data->조상노드 관계출력 , find_relation2 = 조상노드->data 관계출력
void find_relation(treePointer root, char data1, char data2)
{
 treePointer same_parent = NULL;
 treePointer temp = NULL;

 same_parent = find_sameparent(root, data1, data2, temp);

 if (search(same_parent->left, data1, temp))                 // 공통조상노드에서 왼쪽에 data1 오른쪽에 data2
 {
  find_relation1(same_parent, data1,&temp); // data1에서 조상노드까지 관계구하는 함수.
  find_relation2(same_parent, same_parent->data, data2); // 조상노드에서 data2까지 관계구하는 함수
 }

 if (search(same_parent->right, data1, temp))                // 공통조상노드에서 왼쪽에 data2 오른쪽에 data1
 {
  find_relation1(same_parent, data2, &temp); // data1에서 조상노드까지 관계구하는 함수
  find_relation2(same_parent, data1); // 조상노드에서 data1까지 관계구하는 함수
 }

}

//* data에서 조상노드까지의 관계 출력하라
//* 콘솔창 : S,D,C관계로 출력된다.
//* @param parent : 공통조상노드
//* @param start : parent 자식노드
//* @param temp : start 부모노드
void find_relation1(treePointer parent, treePointer start, treePointer temp)
{
 if (search(parent, start->data, &temp) != NULL && temp != parent) { // start 찾고 temp(start의 부모노드)가 공통조상이 아니다.
  pritnf("%c", start->data);
  start = parent;

  if (search(parent, start->data, parent) && (parent->left) == start)
   printf("-S-");
  else
   printf("-D-");
 }

 if (search(parent, start->data, &parent) && parent == parent) { // start 찾고 temp(start의 부모노드)가 공통조상이다.
  printf("%c", start->data);
  return;
 }

 find_relation1(parent, start, &parent);
}

 

 

 

 

/*

//* 조상노드에서 data2의 관계 출력하라
//* 콘솔창 : M,F관계로 출력된다.
void find_relation2(treePointer root, char data1, char data2)

{

 treePointer start = NULL;
 treePointer end = NULL;
 treePointer temp = NULL;
 treePointer exp = NULL;

 start = search(root, data1, &temp);
 end = search(start, data2, &temp);

 {

  int stack_top = -1;
  treePointer node_stack[100];
  char char_stack[100];
  treePointer temp = start;
  char key;

  // preorder traverse 방식 ( center 해결 , left 해결 , right 해결 )
  // 저장

  while (stack_top != -1 || temp != NULL) {

   if (temp != NULL) {

    //--스택 저장

    node_stack[++stack_top] = temp;
    char_stack[stack_top] = key;

    //--도착지 판단
    if (temp == end)
     break;

    temp = temp->left;
    key = 'F';

    else if (temp == NULL&&) // left 해결.

 

 

     // 출력.

     printf("%c", start->data);

    for (int i = 1; i <= stack_top; i++) {

     printf(" - %c - %c", char_stack[i], node_stack[i]->data);

    }

   }

  }

*/

// 이진 탐색 프로그램
void main()
{
 char string[10];
 char a, b, c;
 treePointer root = NULL;
 while (1){
  printf(">>");
  scanf_s("%s", string, sizeof(string));

  a = string[0];
  b = string[2];
  c = string[4];
  if (b == '?')
  {
   find_relation(root, a, c);
  }
  else
  {
   insert_node(&root, a, b, c);
   preorder(root);
  }

  printf("\n");
 }
}