이진탐색트리를 이용한 삽입 삭제

 #include "stdafx.h"
 #include<stdlib.h>

typedef struct treeNode {
    int key;                //데이터 필드
    struct treeNode* left;     //왼쪽 서브트리 링크 필드
    struct treeNode* right;    //오른쪽 서브트리 링크 필드
 } treeNode;
typedef int element;  //int를 이진 탐색 트리 element의 자료형으로 정의

treeNode* insertNode(treeNode *p, int x)  {    //포인터 p가 가리키는 노드와 비교하여 노드 x를 삽입하는 연산
    treeNode *newNode;
   
 if (p == NULL) {
       newNode = (treeNode*)malloc(sizeof(treeNode));
       newNode->key = x;
       newNode->left = NULL;
       newNode->right = NULL;
       return newNode;
    }
   
 else if (x < p->key) {
  p->left = insertNode(p->left, x);
 }
   
 else if (x > p->key) { 
  p->right = insertNode(p->right, x);
 }
   
 else
  printf("\n 이미 같은 키가 있습니다! \n");
   
 return p;
 }

 void deleteNode(treeNode *root, element key)  { //root 노드부터 탐색하여 key 값과 같은 노드를 찾아 삭제하는 연산
    treeNode *parent, *p, *succ, *succ_parent;
    treeNode *child;
    parent=NULL;
    p=root;
    while((p != NULL) && (p->key != key)) {  //삭제할 노드의 위치 탐색
       parent=p;
       if(key < p->key)
     p=p->left;
       else
     p=p->right;
    }

    if(p == NULL) {  //삭제할 노드가 없는 경우
       printf("\n 찾는 키가 이진트리에 없습니다!!\n");
       return;
    }
    // 삭제할 노드가 단말노드인 경우
    if((p->left == NULL) && (p->right == NULL)) {
      
  if(parent != NULL) {
       
   if(parent->left == p)
     parent->left=NULL;
       
   else
     parent->right=NULL;
       }
       else root=NULL;
    }
    // 삭제할 노드가 한 개의 자식노드를 가진 경우
    else if((p->left == NULL) || (p->right == NULL)) {
      
  if(p->left != NULL)
     child=p->left;
      
  else
     child=p->right;
      
  if(parent != NULL) {
       
   if(parent->left == p)
     parent->left=child;
   
   else
     parent->right=child;
       }
       else root=child;
    }
    // 삭제할 노드가 두 개의 자식노드를 가진 경우
    else{
       succ_parent=p;
       succ=p-> left;
       while(succ->right  != NULL) {
          succ_parent=succ;
          succ=succ-> right;
       }
      
    if(succ_parent->left == succ) 
     succ_parent->left=succ-> left;
      
    else
     succ_parent->right=succ-> left;
       p->key=succ->key;
       p=succ;
    }
    free(p);
 }

 void displayInorder(treeNode* root)  {    //이진 탐색 트리를 중위 순회하면서 출력하는 연산
    if(root) { 
       displayInorder(root->left);
       printf("%d ", root->key);
       displayInorder(root->right);
    } 
 }

void main() {
 treeNode* root = NULL; 
    treeNode* foundedNode = NULL;
    int key;
    root=insertNode(root, 40);  //트리 만들기
   
 insertNode(root, 38);
    insertNode(root, 28);
    insertNode(root, 1);
    insertNode(root, 6);
    insertNode(root, 3);
    insertNode(root, 12);
    insertNode(root, 22);
    insertNode(root, 18);
    insertNode(root, 10);
    insertNode(root, 30);

 
 printf("\t[이진트리 출력]  ");
    displayInorder(root);  printf("\n");
        
    printf("삽입할 숫자를 입력하세요 : ");
    scanf("%d", &key);
    getchar();
    insertNode(root, key);
 displayInorder(root);  printf("\n");
           
 printf("삭제할 숫자를 입력하세요 : ");
    scanf("%d", &key);
    getchar();
    deleteNode(root, key);
 displayInorder(root);  printf("\n");

 printf("***************************\n");
 printf("    200802091  지 선 구    \n");
 printf("***************************\n");
}