[자료구조] 이진트리(Binary Tree) 작은 수 출력(printSmaller Values) 구현(C언어)

문제 설명

이 문제에서는 이진 트리의 루트 노드와 정수 m이 주어졌을 때, 트리 내에서 m보다 작은 값을 가진 모든 노드를 출력하는 함수를 작성해야 합니다.

---

문제 요구사항

• 이진 트리의 모든 노드를 순회하여, 각 노드의 값이 m보다 작은 경우 해당 값을 출력합니다.

---

문제 코드 설명

1. 구조체 정의

1.1 BTNode 구조체

typedef struct _btnode {
    int item;               // 노드가 담고 있는 정수 값
    struct _btnode *left;   // 왼쪽 자식 노드의 주소
    struct _btnode *right;  // 오른쪽 자식 노드의 주소
} BTNode;

• item: 노드에 저장된 정수 값
• left: 왼쪽 서브트리(자식 노드)를 가리키는 포인터
• right: 오른쪽 서브트리(자식 노드)를 가리키는 포인터

1.2 StackNode 구조체

typedef struct _stackNode {
    BTNode *btnode;         // 저장된 이진 트리 노드의 포인터
    struct _stackNode *next; // 다음 스택 노드의 주소
} StackNode;

• btnode
  • 타입: BTNode *
  • 설명: 이 필드는 스택에 저장되는 이진 트리 노드의 주소를 저장합니다.
    • 즉, 현재 스택 노드가 임시로 보관하고 있는 이진 트리의 노드를 가리킵니다.
• next
  • 타입: struct _stackNode *
  • 설명: 스택 내에서 현재 노드의 바로 아래에 있는(즉, 다음으로 저장된) 스택 노드의 주소를 가리킵니다.
    • 이를 통해 스택은 후입선출(LIFO, Last In First Out) 방식으로 동작할 수 있습니다.

1.3 Stack 구조체

typedef struct _stack {
    StackNode *top;         // 스택의 최상위 노드의 주소
} Stack;

• top
  • 타입: StackNode *
  • 설명: 스택 구조체에서 이 필드는 스택의 최상위(top) 노드의 주소를 저장합니다.
    • push 연산 시 새 노드를 top에 추가하고,
    • pop 연산 시 top에 있는 노드를 제거하면서 스택의 다음 노드로 이동하는 역할을 합니다.

2. 함수 원형

void printSmallerValues(BTNode *node, int m);

매개변수:

• BTNode *node: 이진 트리의 루트 노드를 가리키는 포인터
• int m: 비교 대상이 되는 정수 값

반환값:

• 이 함수는 void형이므로 반환값이 없습니다.
• 단지 트리 내의 노드 중 값이 m보다 작은 노드들의 값을 출력합니다.

---

작은 수 출력 플로우 차트

 

1. 시작 (Start)
   • 함수가 호출되면, 우선 현재 처리할 node 포인터와 기준값 m이 전달됩니다.
2. 조건 검사: node == NULL?
   • 예 → 더 이상 탐색할 노드가 없으므로 바로 종료(리턴)
   • 아니오 → 다음 단계로 진행
3. 왼쪽 서브트리 탐색
   • printSmallerValues(node->left, m);
   • 현재 노드의 왼쪽 자식 노드를 대상으로 똑같은 함수 호출
   • 이 과정이 완료되면, 왼쪽 서브트리에 있는 모든 값 중 m보다 작은 값이 출력됨
4. 현재 노드 처리
   • if (node->item < m) printf("%d ", node->item);
   • 현재 노드의 값이 m보다 작은지를 검사
     • 예 → 노드 값을 화면에 출력
     • 아니오 → 아무 작업도 하지 않음
5. 오른쪽 서브트리 탐색
   • printSmallerValues(node->right, m);
   • 현재 노드의 오른쪽 자식 노드를 대상으로 똑같은 함수 호출
   • 이 과정을 통해 오른쪽 서브트리에 있는 작은 값들도 출력
6. 끝 (Return)
   • 모든 재귀 호출이 완료되면, 최종적으로 함수를 빠져나갑니다.

 

---

핵심 아이디어

1. 기저 조건:
   • 재귀 호출 시 현재 노드가 NULL이면 더 이상 탐색할 노드가 없으므로 함수를 종료합니다.
2. 현재 노드 처리:
   • 현재 노드의 값을 확인하고, 만약 값이 m보다 작다면 그 값을 출력합니다.
3. 재귀 호출:
   • 현재 노드의 왼쪽 서브트리와 오른쪽 서브트리에 대해 동일한 작업을 재귀적으로 수행하여, 전체 트리를 한 번만 순회합니다.

---

구현

void printSmallerValues(BTNode *node, int m)
{
    // 예외 처리: 현재 노드가 NULL이면 더 이상 탐색할 노드가 없으므로 함수 종료.
    // (재귀 호출의 종료 조건)
    if (node == NULL) 
        return;

    // 왼쪽 서브트리 탐색:
    // 현재 노드의 왼쪽 자식부터 재귀적으로 탐색하여, 
    // m보다 작은 값들을 출력할 기회를 제공합니다.
    printSmallerValues(node->left, m);

    // 현재 노드 처리:
    // 현재 노드의 값(node->item)이 주어진 값 m보다 작은지 검사합니다.
    // 만약 조건을 만족하면, 해당 노드의 값을 출력합니다.
    if (node->item < m) {
        printf("%d ", node->item);
    }

    // 오른쪽 서브트리 탐색:
    // 현재 노드의 오른쪽 자식부터 재귀적으로 탐색하여, 
    // m보다 작은 값들을 출력할 기회를 제공합니다.
    printSmallerValues(node->right, m);
}