[C언어] Binary Tree (7) - smallestValue 함수 구현하기

Binary Tree (7) - smallestValue 함수 구현하기

이진 트리에서 가장 작은 값을 반환하는 함수

주어진 요소 확인하기

구조체

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

• StackNode: (struct) 트리 생성을 위한 스택 노드 구조체
  • *btnode: (pointer field) 이진 트리 노드 주소
  • *next: (pointer field) 다음(스택 아래쪽) 노드 주소

• Stack: (struct) 트리 생성을 위한 스택 구조체
  • *top: (pointer field) 스택 최상단 노드의 주소

smallestValue 함수의 매개 변수

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

 

핵심 아이디어

• 각 노드마다 재귀적으로 가장 작은 값인지 확인
  • 노드가 NULL인 경우 INT_MAX 반환 (#include <limits.h> 필요)
  • 좌우 서브트리에서 가장 작은 값을 재귀적으로 구하기
  • 세 개의 값(해당 노드의 값, 좌우 서브트리의 가장 작은 값) 중 가장 작은 값을 반환

 

구현하기

#include <limits.h>  // INT_MAX를 사용하기 위해 필요

int smallestValue(BTNode *node) {
    // 노드가 NULL이면 아주 큰 값 반환
    if (node == NULL) return INT_MAX;

    // 왼쪽과 오른쪽 서브트리에서 최소값을 각각 재귀적으로 구하기
    int left = smallestValue(node->left);
    int right = smallestValue(node->right);

    // 세 값 중 가장 작은 값 결정
    int min = node->item;
    if (left < min) min = left;
    if (right < min) min = right;

    // 최종적으로 가장 작은 값을 반환
    return min;
}