BST-Binary Search Tree

----------------------------------------bst.h--------------------------------------------

#ifndef BST
#define BST

typedef struct bst* p_bst;
typedef struct bst{
 int data;
 p_bst l_child;
 p_bst r_child;
 int level;
}bst;

int input_option(int* input_value);
int add_bst(int input_value, p_bst root);
int delete_bst(int input_value, p_bst root);
int serch_print_data_bst(int* input_value, p_bst root);
int serch_num_bst(int input_value, p_bst root, int* count);
int find_value_bst(int input_value, p_bst root);
void print_number(p_bst root);
void count_level(p_bst ptr);
void output_bst(p_bst root);
void free_bst(p_bst root);

#endif

------------------------------------------------------------------------------------------

---------------------------------------bst.c-----------------------------------------------

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

int main(){
 int input_value;
 int option;
 int check;
 int count;
 p_bst root;
 root=(p_bst)malloc(sizeof(bst));
 if(root==NULL){
  printf("memory is full!!\n");
  return 1;
 }
 root->l_child=NULL;
 root->r_child=NULL;
 root->level=0;

 while(option=input_option(&input_value)){
  switch(option){
   case 1://input_value값을 추가
    check=add_bst(input_value, root);
    if(check==0)
     return 1;
    break;
   case 2://노드 하나 삭제
    check=delete_bst(input_value, root);
    break;
   case 3://오름차순으로 input_value번째 값 삭제.
    check=serch_print_data_bst(&input_value, root->l_child);
    if(check==1)
     printf(" 없는값.\n");
    else
     check=delete_bst(input_value, root);
    break;
   case 4://input_value가 몇번째인지 출력
    count=1;
    check=serch_num_bst(input_value, root->l_child, &count);
    if(check==1)
     printf("%d는 없는 값.\n",input_value);
    break;
   case 5://input_value가 포함되었는지 출력.
    check=find_value_bst(input_value, root->l_child);
    if(check==1){
     printf("포함되어 있습니다.\n");
    }
    else
     printf("포함되어 있지 않습니다.\n");
    break;
   case 6://오름차순으로 출력.
    print_number(root->l_child);
    printf("\n");
  }
  output_bst(root->l_child);
  printf("\n");
 }

 free_bst(root);
 
 return 0;

}

int input_option(int* input_value){
 char option;

 while(1){
  fflush(stdin);
  if(scanf("%c",&option)!=1){
   printf("잘못된 입력입니다.\n");
   continue;
  }
  if(option=='I' || option=='i'){
   scanf("%d",input_value);
   return 1;
  }
  else if(option=='D' || option=='d'){
   scanf("%d",input_value);
   return 2;
  }
  else if(option=='P' || option=='p'){
   scanf("%d",input_value);
   return 3;
  }
  else if(option=='R' || option=='r'){
   scanf("%d",input_value);
   return 4;
  }
  else if(option=='E' || option=='e'){
   scanf("%d",input_value);
   return 5;
  }
  else if(option=='S' || option=='s'){
   return 6;
  }
  else if(option=='Q' || option=='q'){
   return 0;
  }
  else{
   printf("잘못된 입력입니다.\n");
  }
 }
 
}

------------------------------------------------------------------------------------------

--------------------------------------bst_fun.c--------------------------------------------

#include <stdio.h>
#include "bst.h"

int add_bst(int input_value, p_bst root){
 p_bst node=root->l_child;
 p_bst f_node=root;
 p_bst temp;
 int flag=1;
 temp=(p_bst)malloc(sizeof(bst));
 if(temp==NULL){
  printf("memory is full!!\n");
  return 0;
 }
 temp->l_child=NULL;
 temp->r_child=NULL;
 temp->data=input_value;

 while(node!=NULL){
  if(node->data > temp->data){
   flag=1;
   f_node=node;
   node=node->l_child;
  }
  else if(node->data < temp->data){
   flag=2;
   f_node=node;
   node=node->r_child;
  }
  else {
   printf("같은값이 존재합니다.\n");
   return 1;
  }
 }
 temp->level=(f_node->level)+1;
 if(flag==1)
  f_node->l_child=temp;
 else
  f_node->r_child=temp;
 
 
 return 1;
}

int delete_bst(int input_value, p_bst root){
 p_bst temp=root->l_child;
 p_bst f_temp=root;
 p_bst serch=NULL;
 p_bst f_serch=NULL;
 p_bst temp2=NULL;
 int flag=0;
 int flag1=2;

 while(temp!=NULL){
  if(input_value>temp->data){
   f_temp=temp;
   temp=temp->r_child;
   flag1=1;
  }
  else if(input_value<temp->data){
   f_temp=temp;
   temp=temp->l_child;
   flag1=2;
  }
  else {
   flag=1;
   break;
  }
 }
 if(flag==0){
  printf("입력한 숫자가 없습니다.\n");
  return 0;
 }
 if(temp->l_child!=NULL){
  serch=temp->l_child;
  f_serch=temp;
  while(serch->r_child!=NULL){
   f_serch=serch;
   serch=serch->r_child;
  }

  if(flag1==1)
   f_temp->r_child=serch;
 
  else if(flag1==2)
   f_temp->l_child=serch;

  if(serch->level== (temp->level)+1){
   serch->r_child=temp->r_child;
  }
  else{
   f_serch->r_child=serch->l_child;
   serch->l_child=temp->l_child;
   serch->r_child=temp->r_child;
  }
 }
 else if(temp->r_child!=NULL){
  serch=temp->r_child;
  f_serch=temp;
  while(serch->l_child!=NULL){
   f_serch=serch;
   serch=serch->l_child;
  }
  if(flag1==1)
   f_temp->r_child=serch;
  else if(flag1==2)
   f_temp->l_child=serch;

  if(serch->level== (temp->level)+1){
   serch->l_child=temp->l_child;
  }
  else{
   f_serch->l_child=serch->r_child;
   serch->l_child=temp->l_child;
   serch->r_child=temp->r_child;
  }
 }
 else{
  if(flag1==1)
   f_temp->r_child=NULL;
  else if(flag1==2)
   f_temp->l_child=NULL;
 }
 
 free(temp);
 count_level(root);
 
 return 0;

}

int serch_print_data_bst(int* input_value, p_bst root){
 int check=1;
 if(root==NULL)
  return 1;
 check=serch_print_data_bst(input_value, root->l_child);
 if(check==0)
  return 0;
 if(*input_value==1){
  printf("%d 입니다.\n", root->data);
  *input_value=root->data;
  return 0;
 }
 (*input_value)--;
 check=serch_print_data_bst(input_value, root->r_child);
 if(check==0)
  return 0;

 return 1;
}

int serch_num_bst(int input_value, p_bst root, int* count){
 int check=1;
 if(root==NULL)
  return 1;
 check=serch_num_bst(input_value, root->l_child, count);
 if(check==0)
  return 0;
 if(root->data==input_value){
  printf("%d는 %d번째 값\n",input_value,*count);
  return 0;
 }
 (*count)++;
 check=serch_num_bst(input_value, root->r_child, count);
 if(check==0)
  return 0;

 return 1;

}

int find_value_bst(int input_value, p_bst root){
 p_bst temp=root;

 while(temp!=NULL){
  if(input_value==temp->data)
   return 1;
  else if(input_value>temp->data){
   temp=temp->r_child;
  }
  else
   temp=temp->l_child;
 }
 return 0;
}

void print_number(p_bst root){
 if(root==NULL){
  return ;
 }
 print_number(root->l_child);
 printf(" %d ",root->data);
 print_number(root->r_child);
}

void count_level(p_bst ptr){
 if(ptr==NULL)
  return ;
 if(ptr->l_child!=NULL)
  (ptr->l_child)->level=(ptr->level)+1;
 if(ptr->r_child!=NULL)
  (ptr->r_child)->level=(ptr->level)+1;
 count_level(ptr->l_child);
 count_level(ptr->r_child);
}

void output_bst(p_bst root){
 int i;
/* if(root==NULL){
  printf("\n");
  return ;
 }
 output_bst(root->l_child);

 for(i=1; i<root->level ; i++)
  printf("\t");
 printf("[%d]\n",root->data);

 output_bst(root->r_child);i*/
 if(root==NULL){
  printf("[   ]");
  return ;
 }
 printf("[%3d]",root->data);
// if(root->l_child!=NULL)
  printf("o->");

 output_bst(root->l_child);

 printf("\n");

 for(i=0;i<root->level;i++)
  printf("        ");

// if(root->r_child!=NULL)
  printf("\b\b\b+->");

 output_bst(root->r_child);
}

void free_bst(p_bst root){
 if(root==NULL)
  return;
 free_bst(root->l_child);
 free_bst(root->r_child);
 free(root);
}