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

Binary Search Tree (2) - inOrderIterative 함수 구현하기

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

주어진 요소 확인하기

구조체

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

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

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

inOrderIterative 함수의 매개 변수

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

 

핵심 아이디어

• 루트 노드가 NULL이면 바로 종료
• 현재 노드를 추적할 포인터 cur를 선언하고, 루트를 가리키게 한다.
• cur가 존재하거나 스택이 비어있지 않은 동안 반복되는 while문을 연다.
  • cur가 NULL이 아닐 동안 현재 노드를 스택에 push하고, 왼쪽 자식으로 이동
  • 왼쪽 자식이 더 이상 없으면 스택에서 하나를 pop해서 cur가 가리키게 하고, 해당 노드 값을 출력
  • cur를 그 노드의 오른쪽 자식으로 이동시켜 오른쪽 서브트리 순회 시작
• 위 과정을 반복한다.

 

구현하기

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

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

	// 현재 방문할 노드를 가리키는 포인터
    BSTNode *cur = root;

    // 현재 노드가 존재하거나, 스택에 노드가 남아있는 동안 반복
    while (cur != NULL || !isEmpty(&stk)) {

        // 현재 노드의 왼쪽 자식들을 끝까지 스택에 push
        while (cur != NULL) {
        	// 현재 노드 스택 저장 및 왼쪽 자식으로 이동
            push(&stk, cur);
            cur = cur->left;
        }

        // 왼쪽 자식이 더 이상 없으면, 스택에서 하나 꺼내서 방문 및 출력
        cur = pop(&stk);
        printf("%d ", cur->item);

        // 오른쪽 자식이 있으면 그쪽으로 이동
        cur = cur->right;
    }
}