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

Binary Tree (6) - printSmallerValues 함수 구현하기

주어진 정수보다 작은 모든 노드의 값을 출력하는 함수

주어진 요소 확인하기

구조체

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

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

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

printSmallerValues 함수의 매개 변수

• *node: (pointer) 이진 트리 루트 노드 주소
• m: (int) 해당 값보다 작은지 비교할 정수

 

핵심 아이디어

• 각 노드마다 재귀적으로 m보다 작은지 검사(중위 순회)
  • 노드가 NULL이면 return
  • (1) 오른쪽 서브트리에 대해서 재귀적으로 처리
  • (2) 해당 노드 값이 m보다 작다면 값을 출력
  • (3) 오른쪽 서브트리에 대해서 재귀적으로 처리

 

구현하기

// 중위 순회를 사용해 m보다 작은 모든 노드의 값을 출력하는 함수
void printSmallerValues(BTNode *node, int m) {
    if (node == NULL) return; 	// 노드가 없으면 return

    // 왼쪽 서브트리에 대해 재귀 호출
    printSmallerValues(node->left, m);
    // 현재 노드의 값이 m보다 작으면 출력
    if (node->item < m) printf("%d ", node->item);
    // 오른쪽 서브트리에 대해 재귀 호출
    printSmallerValues(node->right, m);
}