// SearchTree.cpp : 콘솔 응용 프로그램에 대한 진입점을 정의합니다.
//

#include "stdafx.h"

struct Node
{
 int key;
 //int recidx;           //<record가 있는 위치에 대한 정보
 Node *left , *right;
};

//이진트리에서 x라는 키값을 가지는 있는 노드를 찾는다.
// t                 :root node
// x                 :찾고자 하는 키값
// 찾은 경우에는 해당 노드의 포인터를 그렇지 않은 경우는 NULL 반환
Node *searchTree(Node *t, int x)
{
 if ( t == NULL) return NULL;
 if ( t->key == x ) return t;
 if ( t->key < x) return searchTree(t->right, x);
 return searchTree(t->left,x);
}

// 재귀를 사용한 노드 삽입
// 특징 : 반환값이 존재한다.
Node *insertTreeRecursive(Node *t, int x)
{
 // case1 : 루트값이 NULL인 경우
 if ( t == NULL )
 {
  //root  = insertTree(root-<NULL 이라면 , 10)
  // ↑
  //NULL-10-NULL
  Node *r = new Node;
  //인스턴스 값이 저장한 곳이 있다. 때문에 포인터는 해당 인스턴스를 가리킬 뿐 값이 없으므로 New로 인스턴스로 변환
  r->key= x;
  r->left= r->right = NULL;
  //아무것도 가리키지 않고 있다.
  return r;
 }

 //case2 :루트값과 비교할 수 있는 경우
 if ( x < t->key ) t->left = insertTreeRecursive (t->left,x);
 else t->right = insertTreeRecursive(t->right,x);

 return t;
}

//재귀를 사용한 노드 삽입
//이중포인터를 사용한다.

void insertTreeRecursiveA(Node **t, int x )
{
 if ( *t == NULL)
 {
  *t = new Node;
  (*t)->key = x;
  (*t)->left = (*t)->right = NULL;
  return;
 }
 if( x < (*t)->key) insertTreeRecursiveA(&(*t)->left,x);
 else insertTreeRecursiveA(&(*t)->right,x);

}

void insertTree(Node **root, int x)
{
 Node *r = new Node;
 r->key = x;
 r->left= 0;
 r->right = 0;
#if 0
 if(*root == 0) {*root=r; return;}
 Node *p =0;
 Node *tmp = *root;
 while(tmp)
 {
  p = tmp;
  if(x < tmp->key) tmp = tmp->left;
  else tmp = tmp->right;
 }

 if(x<p->key) p ->left = r;
 else p->right =r;
#else
 while (*root)
 {
  if(x<(*root)->key) root = &(*root)->left;
  else root = &(*root)->right;
 }
 *root  =r;
#endif
}

void deleteTree(Node **root, int x)
{
 // 1)삭제할 노드를 찾는다.
 Node **r = root;
 while( *r )
 {
  if((*r)->key == x )break;
  if( x < (*r)->key ) r= &(*r)->left;
  else r = &(*r)->right;
 }
 if( *r==0) return;

 // 2)찾은 노드를 삭제한다.
 if( (*r)->left == 0 && (*r)->right == 0)
 {
  Node *s = (*r);
  *r = 0;
  delete s;
 }
 else if ((*r)->left == 0)
 {
  Node *s= (*r);
  *r = (*r) ->right;
  delete s;
 }

 else if ((*r)->right == 0)
 {
  Node *s =(*r);
  *r = (*r) ->left;
  delete s;
 }

 else
 {
  Node **s = &(*r)->right;
  while ((*s)->left) s=&(*s)->left;
  (*r)->key = (*s)->key;
  Node *p = (*s);
  *s = p->right;
  delete p;
 }
 
}

int _tmain(int argc, _TCHAR* argv[])
{
 int A[]={6,8,4,2,7,1,3,10,5,9,};
 Node *root = 0;

 for(int i=0 ; i<10; i++)
  insertTree(&root, A[i]);

 deleteTree(&root,6);

 for(int i=1; i<=10; i++)
 {
  Node *t = searchTree(root, i);
    if(t)
  printf("%d, %d %d\\n",t->key,(t->left)?t->left->key:0,
   (t->right)?t->right->key:0);
 }

  return 0;
}