이진 탐색 트리 Q5. 두 개의 스택으로 후위 순회하기

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

이진 탐색 트리 Q5. 두 개의 스택으로 후위 순회하기

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

Section F Binary Search Tree postOrderIterativeS2

후위 순회를 두 개의 스택으로 구현해, 한 개 스택 버전보다 직관적으로 푸는 문제다. 첫 번째 스택으로 `루트-오른쪽-왼쪽` 비슷한 순서를 만들고, 두 번째 스택에 뒤집어 담으면 자연스럽게 `왼쪽-오른쪽-루트`가 된다.

한눈에 보는 문제 정보

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

대상 함수: postOrderIterativeS2

카테고리: 이진 탐색 트리

문제에서 요구한 것

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

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

핵심 구현 흐름

STEP 1

루트를 첫 번째 스택에 넣고 하나씩 꺼낸다.

STEP 2

꺼낸 노드를 두 번째 스택에 push하고, 왼쪽·오른쪽 자식을 첫 번째 스택에 넣는다.

STEP 3

첫 번째 스택이 빌 때까지 반복한 뒤, 두 번째 스택을 pop하며 출력한다.

핵심 코드

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

핵심 코드: postOrderIterativeS2

void postOrderIterativeS2(BSTNode *root)
{
	if (root == NULL) return;

	Stack s1, s2;
	s1.top = NULL;
	s2.top = NULL;

	push(&s1, root);

	while (!isEmpty(&s1))
	{
		BSTNode *temp = pop(&s1);
		push(&s2, temp);

		if (temp->left != NULL)
			push(&s1, temp->left);
		if (temp->right != NULL)
			push(&s1, temp->right);
	}

	while (!isEmpty(&s2))
	{
		printf("%d ", pop(&s2)->item);
	}
}

구현할 때 체크할 점

• 두 번째 스택을 단순 보조 공간으로만 보면 순서 뒤집기 역할을 놓치기 쉽다.
• 문제 파일에는 삭제 함수도 함께 있지만, 실제 요구 구현은 후위 순회 함수라는 점을 구분해야 한다.

마무리

이 문제는 거대한 알고리즘을 묻는 문제라기보다, 자료구조를 실제 포인터 연결과 순회 흐름으로 이해하고 있는지 확인하는 실습에 가깝다. 첫 번째 스택으로 `루트-오른쪽-왼쪽` 비슷한 순서를 만들고, 두 번째 스택에 뒤집어 담으면 자연스럽게 `왼쪽-오른쪽-루트`가 된다.

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