'이진탐색트리 삭제함수'에 해당되는 글 1건

typedef struct TreeNode{
 int key;
 struct TreeNode *left,*right;
}TreeNode;

//삭제
void delete_node(TreeNode** root, int key){
 TreeNode *p,*child,*succ,*succ_p,*t;

 p = NULL;
 t= *root;

 while(t != NULL && t->key != key){
  p=t;
  t=(key < t->key) ? t->left : t->right;
 }
 if( t== NULL){
  printf("Key is not in the tree");
  return ;
 }
 // 단말노드인 경우
 if((t->left == NULL) && (t->right == NULL)){
  if(p != NULL){
   if(p->left == t)
    p-left = NULL;
  }
  else
   *root = NULL;
 }
 //하나의 자식만 가지는 경우
 else if((t->left == NULL) || (t->right == NULL)){
  child = (t->left != NULL) ? t->left : t->right;
  if(p != NULL){
   if(p->left == t)
    p->left = child;
   else p->right = child;
  }
  else
   *root = child;
 }
 else{
  succ_p = t;
  succ = t->right;
  while(succ->left != NULL){
   succ_p = succ;
   succ = succ->left;
  }
  if(succ_p-<left == succ)
   succ_p->left = succ->right;
  else succ_p->right = succ->right;

  t->key = succ->key;
  t=succ;
 }
 free(t);
}