다음은 이진 탐색 트리(binary search tree)에서 최소 키… | [7급 국가직 자료구조론] 08년 1회차 기출문제 상세 페이지

1[7급 국가직 자료구조론] 08년 1회차
다음은 이진 탐색 트리(binary search tree)에서 최소 키 값을 가지는 노드에 대한 포인터를 반환하는 함수를 C 언어로 구현한 프로그램의 일부이다. ( 가 )와 ( 나 )부분에 해당되는 문장이 바르게 나열된 것은?
struct TreeNode  {
      int data;
      struct TreeNode *Left;
      struct TreeNode *Right;
};
typedef struct TreeNode *SearchTree;
SearchTree FindMin(SearchTree T)
{
      if (T == NULL) return NULL;
      else if (T→Left == NULL)  ( 가 ) 
      else  ( 나 ) 
}
( 가 )  ( 나 )
1
return T;  return T→Left;
2
return T→Right;  return T→Left;
3
return T;  return FindMin(T→Left);
4
return FindMin(T→Right);  return FindMin(T→Left);
해설

(가)는 return T;, (나)는 return FindMin(T→Left);이다.

이진 탐색 트리의 최솟값은 왼쪽 자식을 끝까지 따라간 노드에 있다. 왼쪽 자식이 없으면 현재 노드가 최소이므로 T를 반환하고, 있으면 왼쪽 서브트리에서 재귀적으로 찾는다.

  • return T; 와 return T→Left; 조합: 왼쪽으로 한 단계만 내려가 더 깊은 곳의 최솟값을 놓친다.
  • return T→Right; 와 return T→Left; 조합: 왼쪽 자식이 없을 때 최소는 현재 노드인데 더 큰 값인 오른쪽 자식을 반환한다.
  • return FindMin(T→Right); 와 return FindMin(T→Left); 조합: 오른쪽 서브트리에는 현재 노드보다 큰 값만 있어 최솟값이 될 수 없다.

오류나 개정된 내용이 보이면 알려주세요

이어서 풀어보기

[7급 국가직 자료구조론] 08년 1회차 20문항 이어서 보기문제·정답·해설을 한 페이지에서 이어서 볼 수 있어요7급 국가직 자료구조론 기출문제 암기장 전체 보기