이진 탐색 트리 Q1. 레벨 순서 순회하기

자료구조 C 실습 · 이진 탐색 트리 · Q1

이진 탐색 트리 Q1. 레벨 순서 순회하기

C 파일 하나를 문제 하나로 보고 정리한 풀이 글이다.
이번 글은 함수가 실제로 어떤 연결, 순회, 변환을 수행하는지에 초점을 맞춘다.

Section F Binary Search Tree levelOrderTraversal

BST를 위에서 아래로, 같은 깊이에서는 왼쪽에서 오른쪽으로 방문하는 레벨 순서 순회를 구현하는 문제다. 레벨 순서는 재귀보다 큐가 더 자연스럽다. 먼저 들어온 노드를 먼저 꺼내야 같은 층 순서가 보장된다.

한눈에 보는 문제 정보

원본 파일: C:\Users\cedis\OneDrive\문서\ANTIWORK\WEKK6~~~~~\data_structures_docker\Data-Structures\Binary_Search_Tree\Q1_F_BST.c

대상 함수: levelOrderTraversal

카테고리: 이진 탐색 트리

문제에서 요구한 것

메뉴와 출력 문자열을 보면 이 파일은 특정 자료구조 연산 하나를 직접 구현하도록 만든 실습 문제다. 입력 흐름은 아래처럼 정리할 수 있다.

• 1: Insert an integer into the binary search tree
• 2: Print the level-order traversal of the binary search tree
• 0: Quit
• Input an integer that you want to insert into the Binary Search Tree
• The resulting level-order traversal of the binary search tree is
• %d

핵심 구현 흐름

STEP 1

루트 노드를 큐에 먼저 넣는다.

STEP 2

큐에서 노드를 하나 꺼내 값을 출력한다.

STEP 3

꺼낸 노드의 왼쪽·오른쪽 자식이 있으면 큐 뒤에 넣는다.

핵심 코드

문제 파일 전체를 다 옮기기보다, 실제로 구현해야 했던 함수만 뽑아서 보면 로직이 더 선명하게 들어온다.

핵심 코드: levelOrderTraversal

void levelOrderTraversal(BSTNode* root)
{	
	// 루트가 비어있으면(NULL) 출력할 게 없으니 바로 종료!
	if( root == NULL)
	{
		return ;
	}

	QueueNode *head = NULL; // 줄 서는 곳(Queue)의 맨 앞자리
	QueueNode *tail = NULL; // 줄 서는 곳(Queue)의 맨 뒷자리

	// 1. 트리 순회의 시작점인 루트 노드를 먼저 큐(대기열)에 넣음
	enqueue( &head, &tail, root);

	// 2. 대기열(Queue)이 텅 빌 때까지 무한 반복!
    while(!isEmpty(head))
	{
		// 맨 앞에 줄 서 있는 노드를 데려옴 (Dequeue)
		BSTNode *temp = dequeue(&head, &tail);

		// 데려온 노드의 값을 출력 (방문 완료!)
		printf("%d ", temp->item);

		// 만약 방금 데려온 노드한테 왼쪽 자식이 있다면? 대기열 맨 뒤에 세움!
		if (temp->left != NULL)
		{
			enqueue( &head, &tail, temp->left);
		}

		// 만약 오른쪽 자식도 있다면? 방금 선 왼쪽 자식 다음에 줄을 세움!
		if (temp->right != NULL)
		{
			enqueue( &head, &tail, temp->right);
		}
	}
}

구현할 때 체크할 점

• 큐 초기화 없이 시작하면 첫 enqueue부터 깨진다.
• 루트가 NULL인 경우는 바로 종료해야 한다.

마무리

이 문제는 거대한 알고리즘을 묻는 문제라기보다, 자료구조를 실제 포인터 연결과 순회 흐름으로 이해하고 있는지 확인하는 실습에 가깝다. 레벨 순서는 재귀보다 큐가 더 자연스럽다. 먼저 들어온 노드를 먼저 꺼내야 같은 층 순서가 보장된다.

같은 카테고리의 다른 문제와 함께 보면, 연결 리스트에서는 재배선, 스택과 큐에서는 순서 제어, 트리에서는 재귀 순회라는 감각이 반복해서 나온다는 점도 같이 볼 수 있다.