[C] SearchTree, DeleteTree

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

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)
{

 // case 1 : 루트값이 NULL인 경우
 if( t == NULL )
 {

  Node *r = new Node;
  r->key = x;
  r->left = r->right = NULL;
  return r;

 }

 // case 2 : 루트값과 비교할 수 있는 경우

 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                                                      //   0일때 이중포인터 사용, 1일때 포인터 사용

 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
}

int _tmain(int argc, _TCHAR* argv[])
{

 int A[] = { 3, 2, 7, 4, 6, 9, 1, 10, 5, 8 };
  
 Node *root = 0;

 for( int i = 0; i < 10; i++ )

  insertTree(&root, A[i]);

 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;

}

실행결과

// 삭제 트리

#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)
{

 // case 1 : 루트값이 NULL인 경우
 if( t == NULL )
 {

  Node *r = new Node;
  r->key = x;
  r->left = r->right = NULL;
  return r;

 }

 // case 2 : 루트값과 비교할 수 있는 경우
 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)
{

 // 첫번째 삭제할 노드를 찾는다.
 
 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;

 // 두번째 찾은 노드를 삭제한다.
 if( (*r)->left == 0 && (*r)->right == 0 )
 {

  Node *s = (*r);
  *r = 0;
  delete s;

 }
 else if( (*r)->left == 0 )
 {

  Node *s = (*r);
  *r = s->right;
  delete s;

 }
 else if( (*r)->right == 0 )
 {

  Node *s = (*r);
  *r = s->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, 5);    // 자식이 없는 노드(5)를 지운다
 //deleteTree(&root, 10);   // 자식이 한개 있는 노드(10)를 지운다
 deleteTree(&root, 6);    // 자식이 두개 있는 노드(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;

}

실행결과