[C언어] Binary Search Tree (3) - preOrderIterative 함수 구현하기

Binary Search Tree (3) - preOrderIterative 함수 구현하기

이진 탐색 트리의 전위 순회를 스택을 사용하여 반복문으로 구현하고, 순회 결과를 출력하는 함수

주어진 요소 확인하기

구조체

• BSTNode: (struct) 이진 탐색 트리 노드 구조체
  • item: (int field) 노드의 값
  • *left: (pointer field) 왼쪽 자식 노드 주소
  • *right: (pointer field) 오른쪽 자식 노드 주소

• StackNode: (struct) 스택 노드 구조체
  • *data: (pointer field) 이진 탐색 트리 노드 주소
  • *next: (pointer field) 다음(스택 아래쪽) 노드 주소

• Stack: (struct) 스택 구조체
  • *top: (pointer field) 스택 최상단 노드 주소

preOrderIterative 함수의 매개 변수

• *root: (pointer) 이진 탐색 트리 루트 노드 주소

 

핵심 아이디어

• 루트 노드가 NULL이면 바로 종료
• 스택에 루트 노드를 push
• 스택이 남아있는 동안 반복되는 while문을 연다.
  • 스택에서 pop으로 노드 하나 꺼내기
  • 해당 노드의 값을 출력
  • 오른쪽 자식이 있다면 스택에 push (왼쪽 자식부터 처리하기 위해 역순으로 삽입)
  • 왼쪽 자식이 있다면 스택에 push

 

구현하기

// 이진 탐색 트리의 전위 순회를 스택을 사용하여 반복문으로 구현하고, 순회 결과를 출력하는 함수
// 순서: 루트 → 왼쪽 자식 → 오른쪽 자식
void preOrderIterative(BSTNode *root) {
    // 트리가 비어 있으면 return
    if (root == NULL) return;

	// 임시 스택 선언 및 초기화
    Stack stk;
    stk.top = NULL;

    // 루트 노드를 스택에 넣고 시작
    push(&stk, root);

    // 스택이 빌 때까지 반복
    while (!isEmpty(&stk)) {
        // 스택에서 노드를 꺼내 방문 및 출력
        BSTNode *node = pop(&stk);
        printf("%d ", node->item);

        // 오른쪽 자식이 있다면 먼저 push → 나중에 처리되도록
        if (node->right) push(&stk, node->right);
        // 왼쪽 자식이 있다면 나중에 push
        if (node->left) push(&stk, node->left);
    }
}