이진탐색트리의 노드 삽입에 대한 다음 C 프로그램의 ㉠ ~ ㉡에 들어갈… | [7급 국가직 자료구조론] 12년 1회차 기출문제 상세 페이지

1[7급 국가직 자료구조론] 12년 1회차
이진탐색트리의 노드 삽입에 대한 다음 C 프로그램의 ㉠ ~ ㉡에 들어갈 내용은? (단, T는 이진탐색트리, X는 이진탐색트리에 삽입할 값이다)
struct TreeNode {
int Element;
struct TreeNode *Left;
struct TreeNode *Right;
};
typedef struct TreeNode *SearchTree;

SearchTree Insert( int X, SearchTree T )
{
if ( T == NULL ) {
T = (SearchTree)malloc(sizeof(struct TreeNode));
T->Element = X;
T->Left = T->Right = NULL;
} else if ( X < T->Element )
㉠
else if ( X > T->Element )
㉡
return T;
}
㉠ ㉡
1
T->Left = Insert( X, T ); T->Right = Insert( X, T );
2
T->Left = Insert( X, T->Left ); T->Right = Insert( X, T->Right );
3
T->Left = Insert( X, T->Element ); T->Right = Insert( X, T->Element );
4
T->Left = Insert( X, T->Right ); T->Right = Insert( X, T->Left );
해설

㉠에는 T->Left = Insert( X, T->Left );, ㉡에는 T->Right = Insert( X, T->Right );가 들어간다.

X가 현재 노드 값보다 작으면 왼쪽 서브트리, 크면 오른쪽 서브트리에 재귀적으로 삽입하고, 반환된 서브트리 루트를 해당 자식 포인터에 다시 연결한다.

  • Insert( X, T )로 자기 자신을 다시 넘기면 T가 NULL이 되지 않아 무한 재귀에 빠진다.
  • T->Element는 정수 값이므로 트리 포인터 인자로 넘길 수 없다.
  • 왼쪽 자식 자리에 오른쪽 서브트리 삽입 결과를 연결하는 식으로 좌우를 뒤바꾸면 기존 서브트리가 엇갈려 이진탐색트리의 대소 규칙이 깨진다.

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

이어서 풀어보기

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