이진 탐색 트리(Binary Search Tree)

 

#include <stdio.h>
#include <string.h>

#pragma warning(disable:4996)
#define TRUE 1
#define FALSE 0


typedef struct anod * Ty_Node_Ptr;

typedef struct anod
{

 int sno; // 학번
 char name[50];
 Ty_Node_Ptr leftChild, rightChild;

}Ty_Node;

typedef Ty_Node Node;

Ty_Node_Ptr Tree_Init(Node * ptr_node);
void insert(Ty_Node_Ptr * ptr_node, char k[], int stud_num);

Ty_Node_Ptr modifiedSearch(Node * ptr_node, char key[]);

void inorder(Ty_Node_Ptr * ptr_node);
Ty_Node_Ptr search(Ty_Node_Ptr node, char k[]);


Ty_Node_Ptr DE(Ty_Node_Ptr * ptr_node, char k[]);
void SE(Ty_Node_Ptr * ptr_node, char k[]);
int HT(Ty_Node_Ptr * ptr_node);
void CH(Ty_Node_Ptr * ptr_node, char k[]);
int LE(Ty_Node_Ptr * ptr_node);


int GetMax(int a, int b);
int HT_A_Node(Ty_Node_Ptr * ptr_node, char k[]);

int main() {
 Ty_Node_Ptr ROOT;

 char name[50];
 int sno;
 char cmd[30];
 
 int height = 0;
 int leaf;
 int heightOfNode;
 
 printf("시작\n");
 ROOT = Tree_Init(&ROOT); // 트리 초기화
 


 while (1) {
  printf("수행할 작업은 (in, sp, de, se, ht, ch, le, ex) ? ");
  scanf("%s", cmd);
  if (!strcmp(cmd, "in")){
   scanf("%d %s", &sno, name);
   printf("입력 성공! "); 
   insert(&ROOT, name, sno);
   heightOfNode = HT_A_Node(&ROOT, name);
   printf("level = %d\n", heightOfNode);
  }
  if (!strcmp(cmd, "sp") ){
   printf("[inorder]파일의 내용은 다음과 같습니다.\n");
   inorder(&ROOT);
  }
  if (!strcmp(cmd, "de") ){
   scanf("%s", name);
   DE(&ROOT, name);
   printf("성공적으로 삭제되었습니다.\n");
  }

  if (!strcmp(cmd, "se") ){
   scanf("%s", name);
   SE(&ROOT, name);
  }
  if (!strcmp(cmd, "ht")) {
   height = HT(&ROOT);
   printf("트리의 높이 : %d \n", height);
  }
  if (!strcmp(cmd, "ch")) {
   scanf("%s", name);
   CH(&ROOT, name);
  }
  if (!strcmp(cmd, "le")) {
   leaf = LE(&ROOT);
   printf("리프 노드 수 : %d \n", leaf);
  }
  
  
  if (!strcmp(cmd, "ex")) {
   break;
  }
 }

 printf("프로그램을 종료합니다!\n");

 return 0;
}



Ty_Node_Ptr Tree_Init(Node * ptr_node) { //초기화 : 이진탐색트리를 생성하고 파일을 읽어온다.


 (ptr_node)->leftChild = NULL;
 (ptr_node)->rightChild = NULL;

 Ty_Node_Ptr newNode, ROOT;

 FILE *fp;

 fp = fopen("sdata.txt", "r");
 if (fp == NULL) {
  perror("error : can't read the data file..\n");
  return FALSE;
 }
 else {

  ROOT = NULL;
  while (!feof(fp)) {
   //1. newNode 생성 - 메모리 할당,초기화

   if (!(ROOT)) {

    ROOT = (Ty_Node_Ptr)malloc(sizeof(struct anod));
    fscanf(fp, "%d %s", &ROOT->sno, ROOT->name);
    printf("%d %s\n", ROOT->sno, ROOT->name);
    ROOT->leftChild = NULL;
    ROOT->rightChild = NULL;
   }

   else {

    newNode = (Ty_Node_Ptr)malloc(sizeof(struct anod));

    fscanf(fp, "%d %s", &newNode->sno, newNode->name);
    insert(&ROOT, newNode->name, newNode->sno);
    newNode->leftChild = NULL;
    newNode->rightChild = NULL;
    printf("%d %s\n", newNode->sno, newNode->name);

   }
  }


  return ROOT;
 }

}

void insert(Ty_Node_Ptr *ptr_node, char k[], int stud_num)
{              /*  ptr_node : 루트 변수의 주소를 받음.
                k : 삽입할 레코드의 키값(이름)
                stud_num: 삽입할 레코드에서 키값을 제외한 나머지 데이터  */
 Ty_Node_Ptr ptr, temp;
 ptr = (Ty_Node_Ptr)malloc(sizeof(*ptr));

 strcpy(ptr->name, k);
 ptr->sno = stud_num;
 ptr->leftChild = ptr->rightChild = NULL;
 if (!(*ptr_node))  // 루트가 NULL인 경우. 즉, 노드가 한 개도 없는 경우.
  *ptr_node = ptr;
 else {
  temp = modifiedSearch(*ptr_node, k); // 새 노드를 붙일 노드 탐색
  //이 때, temp는 붙일 노드의 부모 노드임
  if (!temp)
   printf("동일 키의 노드가 이미 존재하여 삽입 실패함.\n");
  else {  // temp 가 가리키는 노드에 새 노드를 붙인다.
   if (strcmp(k, temp->name) > 0)
    temp->rightChild = ptr;
   else
    temp->leftChild = ptr;
  }
 }

}

Ty_Node_Ptr modifiedSearch(Node *Parent_node, char key[]) {
 Ty_Node_Ptr Parent = NULL;

 while (Parent_node) {
  if (!strcmp(key, Parent_node->name))
   return FALSE;
  Parent = Parent_node;
  if (strcmp(key, Parent_node->name) > 0)
   Parent_node = Parent_node->rightChild;
  else
   Parent_node = Parent_node->leftChild;
 }
 return Parent;
}
Ty_Node_Ptr search(Ty_Node_Ptr node, char k[]) {
 if (!node) {
  printf("찾는 이름이 트리에 없습니다.\n");
  return NULL;
 }
 if (!(strcmp(k, node->name))) return node;
 if (strcmp(k, node->name) < 0)
  return search(node->leftChild, k);
 else
  return search(node->rightChild, k);
}

void inorder(Ty_Node_Ptr * ptr_node) {
 if (*ptr_node) {
  inorder(&((*ptr_node)->leftChild));
  printf("%s, %d\n", (*ptr_node)->name, (*ptr_node)->sno);
  inorder(&((*ptr_node)->rightChild));
 }

}


Ty_Node_Ptr DE(Ty_Node_Ptr * ptr_root, char k[]) {

 Ty_Node_Ptr del_parent, delete_node;
 Ty_Node_Ptr succ;
 Ty_Node_Ptr curr = *ptr_root;


 del_parent = NULL;
 while (curr != NULL && strcmp(curr->name, k)) {
  del_parent = curr;
  if (strcmp(curr->name, k) > 0)
   curr = curr->leftChild;
  else
   curr = curr->rightChild;
 }
 delete_node = curr;
 printf("삭제할 이름은 %s.\n", delete_node->name);
 if (!curr) {
  printf("찾는 이름이 트리에 없습니다.\n");
  return NULL;
 }

 else {
  if (delete_node->leftChild && delete_node->rightChild) { // 자식이 둘 다 있는 경우,
   succ = delete_node->rightChild;
   Ty_Node_Ptr succ_parent = delete_node;

   while (succ->leftChild) { // succ을 찾는다.
    succ_parent = succ;
    succ = succ->leftChild;
   }
   printf("%s의 위치 변경이 일어남.\n", succ->name);
   //데이터 백업 과정

   strcpy(delete_node->name, succ->name);
   delete_node->sno = succ->sno;
   delete_node = succ;


   if (succ->leftChild || succ->rightChild) { //대체노드의 자식노드가 있을 경우 : Case 2가지
    if (succ_parent->leftChild == succ)
     succ_parent->leftChild = succ->rightChild;
    else if (succ_parent->rightChild == succ)
     succ_parent->rightChild = succ->rightChild;
   }


   else {
    if (succ_parent->leftChild == succ)
     succ_parent->leftChild = NULL;

    else if (succ_parent->rightChild == succ)
     succ_parent->rightChild = NULL;

   }



  }


  else if (delete_node->leftChild || delete_node->rightChild) { //자식노드가 1개
   Ty_Node_Ptr del_child_node;
   if (delete_node->leftChild)
    del_child_node = delete_node->leftChild;
   else
    del_child_node = delete_node->rightChild;
   printf("%s의 위치 변경이 일어남.\n", del_child_node->name);
   if (del_parent) { //삭제할 노드의 부모 노드가 존재할 때
    if (del_parent->leftChild == delete_node)
     del_parent->leftChild = del_child_node;
    else if (del_parent->rightChild == delete_node)
     del_parent->rightChild = del_child_node;
   }
   else { // 삭제하려는게 루트 노드일 경우

    strcpy(delete_node->name, del_child_node->name);
    delete_node->sno = del_child_node->sno;
    delete_node->leftChild = del_child_node->leftChild;
    delete_node->rightChild = del_child_node->rightChild;
    delete_node = del_child_node;

   }

  }

  else // 리프노드인 경우
  {
   if (del_parent->leftChild == delete_node)
    del_parent->leftChild = NULL;
   else
    del_parent->rightChild = NULL;
  }
 }


 return TRUE;
}
void SE(Ty_Node_Ptr * ptr_node, char k[]) {
 int heightOfNode;
 Ty_Node_Ptr temp;
 temp = search(*ptr_node, k);
 if (!temp)
  return FALSE;
 printf("이름 : %s, 학번 : %d, ", temp->name, temp->sno);
 heightOfNode = HT_A_Node(ptr_node, k);
 printf("레벨 위치 : %d\n", heightOfNode);
}
int HT(Ty_Node_Ptr * ptr_node) {
 Ty_Node_Ptr curr = *ptr_node;

 int level = 0;
 if (curr)
  level = 1 + GetMax(HT(&curr->leftChild), HT(&curr->rightChild));
 return level;

}
int HT_A_Node(Ty_Node_Ptr * ptr_node, char k[]) {
 Ty_Node_Ptr curr = *ptr_node;
 int level = 1;
 while (curr) {
  if (!strcmp(curr->name, k))
   return level;
  else if (strcmp(curr->name, k) > 0) {
   curr = curr->leftChild;
   level++;
  }
  else {
   curr = curr->rightChild;
   level++;
  }
 }
 return;



}
void CH(Ty_Node_Ptr * ptr_node, char k[]) {
 Ty_Node_Ptr curr = *ptr_node;

 while (curr) {
  if (!strcmp(curr->name, k))
   break;
  else if (strcmp(curr->name, k) > 0)
   curr = curr->leftChild;
  else
   curr = curr->rightChild;
 }
 if (curr->leftChild)
  printf("%s의 left child : %s\n", curr->name, curr->leftChild->name);
 else
  printf("%s has no left child.\n", curr->name);
 if (curr->rightChild)
  printf("%s의 right child : %s\n", curr->name, curr->rightChild->name);
 else
  printf("%s has no right child.\n", curr->name);
}
int LE(Ty_Node_Ptr * ptr_node) {
 Ty_Node_Ptr curr = *ptr_node;
 int Num_leaf = 0;
 if (curr) {
  if (curr->leftChild == NULL && curr->rightChild == NULL)
   return (Num_leaf + 1);
  Num_leaf += LE(&curr->leftChild);
  Num_leaf += LE(&curr->rightChild);
 }
 return Num_leaf;
}
int GetMax(int a, int b) {
 if (a > b)
  return a;
 else
  return b;
}