이진 탐색 트리 Q2. 중위 순회하기

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

이진 탐색 트리 Q2. 중위 순회하기

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

Section F Binary Search Tree inOrderTraversal

BST를 중위 순회해 오름차순 결과를 출력하는 문제다. BST의 중위 순회가 오름차순이 된다는 사실을 직접 코드로 확인하는 기본 문제다.

한눈에 보는 문제 정보

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

대상 함수: inOrderTraversal

카테고리: 이진 탐색 트리

문제에서 요구한 것

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

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

핵심 구현 흐름

STEP 1

왼쪽 서브트리를 먼저 방문한다.

STEP 2

현재 노드 값을 출력한다.

STEP 3

오른쪽 서브트리를 마지막에 방문한다.

핵심 코드

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

핵심 코드: inOrderTraversal

void inOrderTraversal(BSTNode *root)
{	
	Stack s;
	s.top = NULL; // 스택 초기화 (우리가 지나온 경로를 기억할 가방)

	// 현재 노드가 있거나, 스택에 기억해둔 노드가 아직 모자라게 남아있다면 계속 빙글빙글 돕니다.
	while (root != NULL || !isEmpty(&s))
	{
		if (root != NULL)
		{
			// 일단 왼쪽으로 갈 수 있는 데까지 쭉쭉 내려가면서, 지나온 길을 스택에 푸시!
			push(&s, root);
			root = root->left;
		}
		else
		{
			// 왼쪽 끝까지 도착해서 더 이상 갈 곳이 없게 되면(NULL)?
			// 스택에서 가장 최근에 지나쳐온 노드를 꺼냄(pop)
			root = pop(&s);

			// 해당 노드의 값을 출력! 이게 In-order(Left -> Root -> Right)의 핵심!
    		printf("%d ", root->item);

			// 왼쪽 자식 처리 다 했고 나 자신(Root)도 출력했으니 이젠 "오른쪽 자식"으로 탐험 시작!
    		root = root->right;
		}
	}
}

구현할 때 체크할 점

• 재귀 순서가 조금만 바뀌어도 전혀 다른 순회가 된다.
• BST가 아니라 일반 트리라면 오름차순 성질이 성립하지 않는다는 점도 같이 기억해야 한다.

마무리

이 문제는 거대한 알고리즘을 묻는 문제라기보다, 자료구조를 실제 포인터 연결과 순회 흐름으로 이해하고 있는지 확인하는 실습에 가깝다. BST의 중위 순회가 오름차순이 된다는 사실을 직접 코드로 확인하는 기본 문제다.

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