document.write('
Data hosted with ♥ by Pastebin.com - Download Raw - See Original
  1. #include "BinarySearchTree.h"
  2. BSTNode * BST_CreateNode(Data data)
  3. {
  4.     BSTNode * BST = (BSTNode *)malloc(sizeof(BSTNode)); //최초의 루트노드를 동적메모리 할당하기.
  5.     BST->data = data;
  6.     BST->Left = NULL;
  7.     BST->Right = NULL;
  8.     return BST;  //루트노드 반환.
  9. }
  10. BSTNode * BST_SearchNode(BSTNode * Tree, Data data)
  11. {
  12.     if (Tree == NULL) // 현재노드가 없는 경우, 반환.
  13.         return NULL;
  14.  
  15.     if (Tree->data > data)  //해당원소가 현재노드보다 작을경우.
  16.         return BST_SearchNode(Tree->Left, data);    //현재노드의 Left로 탐색시작.
  17.     else if (Tree->data < data)    //해당원소가 현재노드 보다 클 경우.
  18.         return BST_SearchNode(Tree->Right, data);   //현재노드의 right로 탐색시작.
  19.     if (Tree->data == data)     //해당 원소를 찾았을 경우,
  20.         return Tree;
  21.     else //찾고자하는 원소가 없는경우, 예외처리
  22.     {
  23.         printf("찾고자하는 원소가 없음 !\\n");
  24.         exit(-1);
  25.     }
  26. }
  27. BSTNode * BST_SearchMinNode(BSTNode * Tree)
  28. {
  29.     if (Tree == NULL)   //트리가 존재하지 않는경우..
  30.         return NULL;   
  31.  
  32.     //트리의 가장작은값은 루트노드를 기준으로 제일 왼쪽에 존재하므로, 제일 왼쪽의 원소가 존재한다면 계속해서 호출하기.
  33.     if (Tree->Left != NULL)
  34.         return BST_SearchMinNode(Tree->Left);
  35.     return Tree;
  36. }
  37. BSTNode * BST_RemoveNode(BSTNode * Tree, BSTNode * Parent, Data data)
  38. {
  39.     BSTNode * Removed = NULL;
  40.     if (Tree == NULL)
  41.         return NULL;
  42.     if (Tree->data < data) //제거할 원소가 해당노드보다 클 경우, 오른쪽으로 호출하기.
  43.         return BST_RemoveNode(Tree->Right, Tree, data); //호출 시 오른쪽노드, 오른쪽노드의 부모는 현재 Tree가 되며, 값은 그대로 적기.
  44.     else if (Tree->data > data) //제거할 원소가 해당노드보다 작은경우, 왼쪽으로 호출하기.
  45.         return BST_RemoveNode(Tree->Left, Tree, data); //호출 시 왼쪽노드, 왼쪽노드의 부모는 현재 Tree가 되며, 값은 그대로 적기.
  46.     else  // 제거할 노드를 찾은경우.
  47.     {
  48.         Removed = Tree; //제거할 노드를 마지막에 반환하기 위해 LRemoved 값에 넣어준다.
  49.  
  50.         if (Tree->Left == NULL && Tree->Right == NULL) //제거할 노드의 자식노드들이 없는경우(단말노드일 경우)
  51.         {
  52.             if (Parent->Left == Tree) //제거할 단말노드가 부모의 Left값 인지 확인하기.
  53.                 Parent->Left = NULL; //제거할 단말노드가 부모의 Left값이면, 부모의 Left = NULL이 되어야 함.
  54.  
  55.             else //제거할 단말노드가 부모의 Right값이면, 부모의 Right = NULL이 되어야 함.
  56.                 Parent->Right = NULL; //제거할 단말노드가 부모의 Right값이면, 부모의 RIght = NULL이 되어야 함.
  57.         }
  58.         else // 제거할 노드가 단말노드가 아닐경우,
  59.         {
  60.             if (Tree->Left != NULL && Tree->Right != NULL) //제거할 노드의 자식이 2명인 경우
  61.             {
  62.                 BSTNode * delNode = BST_SearchMinNode(Tree->Right); //제거할 노드의 오른쪽 자식에서 최소값인 노드를 찾기.
  63.                 delNode = BST_RemoveNode(Tree, NULL, delNode->data);   //delNode에는 오른쪽 노드의 최소값이 제거됨과 동시에 반환된다.
  64.                 /*오른쪽 자식중 최소값인 노드를 제거하고, 이노드의 값을 제거할 노드의 데이터에 삽입한다.
  65.                  * (실제로는 제거할노드는 제거되지않으며, 오른쪽 자식의 최소값을 제거하므로써 불필요한 과정을 생략할 수 있다.)
  66.                  * 그러면 이진트리의 규칙(왼쪽자식의 원소 < 오른쪽자식의 원소)을 지킬수있다.
  67.                  */
  68.                  Tree->data = delNode->data;  //최소값을 가진노드의 값을 제거할 노드(실제로는 제거되지 않는 노드임)에 붙여넣기.
  69.                  Removed = NULL;
  70.             }
  71.             else //제거할 노드의 자식이 하나인 경우
  72.             {
  73.                 //제거할 노드에 매달린 하나의 자식을 부모의 자식으로 옮기기위해
  74.                 //매달린 하나의 노드를 RNode에 삽입
  75.                 BSTNode * RNode = Tree;
  76.                 if (RNode->Left != NULL) //제거할 노드에 매달린 하나의 자식이 왼쪽노드인경우.
  77.                     RNode = RNode->Left; //제거할 노드에 매달린(Left) 하나의 자식을 Rnode로 삽입.
  78.  
  79.                 else // 제거할 노드에 매달린 하나의 자식이 오른쪽 노드인경우
  80.                     RNode = RNode->Right;  //제거할 노드에 매달린(Right) 하나의 자식을 Rnode로 삽입
  81.                 if (Parent->Right == Tree) //제거할 노드가 부모의 오른쪽노드에 해당하는 경우
  82.                     Parent->Right = RNode; //부모의 오른쪽노드에 제거할 노드의 자식값을 삽입하기.
  83.                 else   //제거할 노드가 부모의 왼쪽노드에 해당하는 경우
  84.                     Parent->Left = RNode;  //부모의 왼쪽노드에 제거할 노드의 자식값을 삽입하기.
  85.             }
  86.         }
  87.     }
  88.     return Removed;
  89. }
  90. void BST_InsertNode(BSTNode * Tree, BSTNode * Child) //루트노드를 기준으로 삽입된 노드의 위치를 적절히 삽입하기.
  91. {
  92.     if (Tree->data > Child->data) //삽입될 노드가 현재노드의 값보다 작은경우(왼쪽으로 탐색시작)
  93.     {
  94.         if (Tree->Left != NULL) // 현재노드의 왼쪽노드의 값이 존재하는경우, 왼쪽노드를 기준으로 탐색.
  95.             BST_InsertNode(Tree->Left, Child);
  96.         else //현재노드의 왼쪽노드가 존재하지 않는경우, 현재노드의 왼쪽자식으로 삽입.
  97.             Tree->Left = Child;
  98.     }
  99.     else  //삽입될 노드가 현재노드의 값보다 큰경우(오른쪽으로 탐색시작)
  100.     {
  101.         if (Tree->Right != NULL) //현재노드의 오른쪽노드의 값이 존재하는 경우, 오른쪽노드를 기준으로 탐색.
  102.             BST_InsertNode(Tree->Right, Child);
  103.         else //현재노드의 오른쪽 자식이 존재하지 않는 경우, 현재노드의 오른쪽 자식으로 삽입.
  104.             Tree->Right = Child;
  105.     }
  106. }
  107. void BST_DestroyNode(BSTNode * Node)
  108. {
  109.     Node = NULL;  //댕글링 포인터를 방지하기위해서 NULL삽입
  110.     free(Node);  //동적메모리 해제, 포인터변수 Node 는 여전히 해제된 메모리의 시작주소를 가지고있으므로,
  111.     /* 댕글링 포인터란?
  112.      * 댕글링 포인터에 접근하여 가리키는 주소의 데이터를 저장하거나 읽으려고 시도한다면 프로그램은 에러를 내면서 종료
  113.      * 여기서는 BST_InorderPrintTree에서 재귀호출을 통해서 데이터를 읽으려고 시도할 경우, free()함수로 메모리를 할당하지만,
  114.      * 이 Node란 포인터변수는 이미 할당된주소를 가리키므로 NULL값을 채워서 방지해야 한다!
  115.      *
  116.      */
  117. }
  118. void BST_DestroyTree(BSTNode * Tree)
  119. {
  120.     if (Tree == NULL)
  121.         return;
  122.     if (Tree->Left != NULL)
  123.         BST_DestroyTree(Tree->Left);
  124.     if (Tree->Right != NULL)
  125.         BST_DestroyTree(Tree->Right);
  126.     printf("%d제거!\\n", Tree->data);
  127.     Tree->Right = NULL;
  128.     Tree->Left = NULL;
  129.     BST_DestroyNode(Tree);
  130. }
  131. void BST_InorderPrintTree(BSTNode * Tree)
  132. {
  133.     if (Tree != NULL)
  134.     {
  135.         BST_InorderPrintTree(Tree->Left);
  136.         printf("%d ", Tree->data);
  137.         BST_InorderPrintTree(Tree->Right);
  138.     }
  139. }
');