이진 탐색 트리 Q3. 반복문으로 전위 순회하기

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

이진 탐색 트리 Q3. 반복문으로 전위 순회하기

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

Section F Binary Search Tree preOrderIterative

재귀 대신 스택을 이용해 BST의 전위 순회를 구현하는 문제다. 전위 순회는 '현재-왼쪽-오른쪽' 순서다. 스택에 push할 때는 반대로 오른쪽을 먼저 넣어야 왼쪽이 먼저 처리된다.

한눈에 보는 문제 정보

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

대상 함수: preOrderIterative

카테고리: 이진 탐색 트리

문제에서 요구한 것

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

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

핵심 구현 흐름

STEP 1

루트를 스택에 push한다.

STEP 2

pop한 노드의 값을 출력한다.

STEP 3

오른쪽 자식, 왼쪽 자식 순으로 push해 다음 pop에서 왼쪽이 먼저 나오게 만든다.

핵심 코드

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

핵심 코드: preOrderIterative

void preOrderIterative(BSTNode *root)
{
    Stack s;
    s.top = NULL; // 스택 초기화 (나중에 다시 돌아와서 '오른쪽'으로 가야 할 곳을 기억하는 용도)

	// 현재 파고드는 노드가 있거나 혹은 스택에 저장해둔 게 있으면 계속 탐색!
    while (root != NULL || !isEmpty(&s))
    {
        if (root != NULL)
        {
			// Pre-order(전위 순회)는 "Root -> Left -> Right" 원칙!
			// 그러니까 노드를 만나자마자 일단 값을 시원하게 출력해버림!
            printf("%d ", root->item);

			// 이따가 "오른쪽"으로 가야 한다는 사실을 까먹지 않기 위해 현재 노드를 스택에 킵(Push)해둠
            push(&s, root);

			// 그리고 곧바로 왼쪽으로 끝까지 냅다 직진함
            root = root->left;
        }
        else
        {
			// 만약 왼쪽을 타고 내려가다가 길 끝(NULL)을 만났다면?
			// 아까 스택에 킵해뒀던 노드를 하나 꺼내서(Pop)...
            root = pop(&s);

			// 그 노드의 "오른쪽" 길로 방향을 틂
            root = root->right;
        }
    }
}

구현할 때 체크할 점

• 왼쪽을 먼저 push하면 출력 순서가 뒤바뀐다.
• 반복 순회는 스택이 비는 조건을 종료 기준으로 둬야 한다.

마무리

이 문제는 거대한 알고리즘을 묻는 문제라기보다, 자료구조를 실제 포인터 연결과 순회 흐름으로 이해하고 있는지 확인하는 실습에 가깝다. 전위 순회는 '현재-왼쪽-오른쪽' 순서다. 스택에 push할 때는 반대로 오른쪽을 먼저 넣어야 왼쪽이 먼저 처리된다.

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