이진 트리 Q3. 자식이 하나인 노드 개수 세기

자료구조 C 실습 · 이진 트리 · Q3

이진 트리 Q3. 자식이 하나인 노드 개수 세기

C 파일 하나를 문제 하나로 보고 정리한 풀이 글이다.
이번 글은 함수가 실제로 어떤 연결, 순회, 변환을 수행하는지에 초점을 맞춘다.

Section E Binary Tree countOneChildNodes

왼쪽 또는 오른쪽 자식 하나만 가진 노드를 세는 문제다. 각 노드에서 '정확히 하나의 자식만 존재하는가'를 검사하고, 나머지는 왼쪽·오른쪽 서브트리 개수를 더하는 구조다.

한눈에 보는 문제 정보

원본 파일: C:\Users\cedis\OneDrive\문서\ANTIWORK\WEKK6~~~~~\data_structures_docker\Data-Structures\Binary_Tree\Q3_E_BT.c

대상 함수: countOneChildNodes

카테고리: 이진 트리

문제에서 요구한 것

메뉴와 출력 문자열을 보면 이 파일은 특정 자료구조 연산 하나를 직접 구현하도록 만든 실습 문제다. 입력 흐름은 아래처럼 정리할 수 있다.

• 1: Create a binary tree.
• 2: Count the number of nodes that have exactly one child node.
• 0: Quit
• The resulting binary tree is
• The number of nodes that have exactly one child node is: %d.
• Input an integer that you want to add to the binary tree. Any Alpha value will be treated as NULL.

핵심 구현 흐름

STEP 1

빈 노드는 0을 반환한다.

STEP 2

현재 노드가 자식을 하나만 가지면 1을 더한다.

STEP 3

왼쪽·오른쪽 서브트리를 재귀 호출해 누적 합을 만든다.

핵심 코드

문제 파일 전체를 다 옮기기보다, 실제로 구현해야 했던 함수만 뽑아서 보면 로직이 더 선명하게 들어온다.

핵심 코드: countOneChildNodes

int countOneChildNodes(BTNode *node)

{   
    if (node == NULL)
    {
        return 0;
    }
    int leftcount = countOneChildNodes(node->left);
    int rightcount = countOneChildNodes(node->right);

    if(node->left == NULL && node->right == NULL)
    {
        return 0;
    }
    else if(node->left != NULL && node->right != NULL )
    {
        return leftcount + rightcount;
    }
    else if(node->left == NULL && node->right != NULL )
    {
        return rightcount +1;
    }
    else if(node->left != NULL && node->right == NULL )
    {
        return leftcount +1;
    }
}

구현할 때 체크할 점

• 리프 노드와 자식 하나 노드를 헷갈리면 답이 달라진다.
• 현재 노드 판단과 하위 노드 합산을 분리해서 보는 편이 안전하다.

마무리

이 문제는 거대한 알고리즘을 묻는 문제라기보다, 자료구조를 실제 포인터 연결과 순회 흐름으로 이해하고 있는지 확인하는 실습에 가깝다. 각 노드에서 '정확히 하나의 자식만 존재하는가'를 검사하고, 나머지는 왼쪽·오른쪽 서브트리 개수를 더하는 구조다.

같은 카테고리의 다른 문제와 함께 보면, 연결 리스트에서는 재배선, 스택과 큐에서는 순서 제어, 트리에서는 재귀 순회라는 감각이 반복해서 나온다는 점도 같이 볼 수 있다.