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

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

이진 트리에서 자식 노드가 정확히 하나인 노드의 개수를 세는 함수

주어진 요소 확인하기

구조체

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

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

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

countOneChildNodes 함수의 매개 변수

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

 

핵심 아이디어

• 각 노드에 대해 재귀적으로 자식이 하나만 있는지 검사
  • 노드가 NULL이면 0을 반환
  • 노드의 자식이 정확히 하나일 경우 +1 더하기
  • 좌우 서브트리에서 얻은 결과를 합산하여 반환

 

 

구현하기

int countOneChildNodes(BTNode *node) {
    // 노드가 없으면 0 반환 (비어 있는 부분)
    if (node == NULL) return 0;

    // 왼쪽과 오른쪽 서브트리에서 각각 자식이 하나만 있는 노드 개수를 재귀적으로 계산
    int left = countOneChildNodes(node->left);
    int right = countOneChildNodes(node->right);

    // 현재 노드가 자식을 정확히 하나만 가지고 있는 경우
    if ((node->left != NULL && node->right == NULL) || 
        (node->right != NULL && node->left == NULL)) {
        // 현재 노드 포함 + 좌우 결과 합산
        return 1 + left + right;
    }

    // 자식이 0개 또는 2개인 경우, 현재 노드는 포함하지 않고 좌우 결과만 반환
    return left + right;
}