BST의 3가지 연산 中 삽입 - sihyun10/data_structures_docker GitHub Wiki

BST의 3가지 연산 中 삽입 (insertBSTNode() 함수)

재귀적으로 알맞은 위치로 찾아가 새 노드를 붙여준다

//main() 함수 일부분 - 삽입 함수 호출 부분
case 1:  
  printf("Input an integer that you want to insert into the Binary Search Tree: ");
  scanf("%d", &i);
  insertBSTNode(&root, i);
  break;

//insertBSTNode() 함수
void insertBSTNode(BSTNode **node, int value){
  if (*node == NULL)
  {
    *node = malloc(sizeof(BSTNode));

    if (*node != NULL) {
      (*node)->item = value;
      (*node)->left = NULL;
      (*node)->right = NULL;
    }
  }
  else
  {
    if (value < (*node)->item)
    {
      insertBSTNode(&((*node)->left), value);
    }
    else if (value > (*node)->item)
    {
      insertBSTNode(&((*node)->right), value);
    }
    else
      return; //중복은 삽입 X
  }
}

void insertBSTNode(BSTNode **node, int value)
  • **node : 포인터를 수정하려면 이중 포인터가 필요
  • value : 삽입할 값

[작동 순서]
ex) 10,5,15 삽입

  1. root == NULL 인 경우, insertBSTNode(&root, 10)
    새로운 노드를 만들어서 root에 연결한다

  2. insertBSTNode(&root, 5)
    5 < 10 이므로 "왼쪽"으로 이동 -> Left가 NULL
    left에 새 노드 연결됨

  3. insertBSTNode(&root, 15)
    15 > 10 이므로 "오른쪽"으로 이동 -> Right가 NULL
    right에 새 노드 연결됨

  • value < node->item : 왼쪽 서브트리로 이동 (재귀)
  • value > node->item : 오른쪽 서브트리로 이동 (재귀)

Q. 그럼 만약 이 상태에서 "7"을 추가하면 어떻게 작동할까?

insertBSTNode(&root, 7)

    10
   /  \
  5    15
  • 7 < 10 (root) : 왼쪽(5)로 재귀
  • 7 > 5 : 오른쪽(NULL)로 재귀
  • NULL이므로 여기에 새 노드 생성함
    10
   /  \
  5    15
   \
    7
⚠️ **GitHub.com Fallback** ⚠️