C++로 이진 트리의 모든 전체 노드(Full Node) 출력하기

문제 개요

이 문제에서는 하나의 이진 트리가 주어지며, 우리의 목표는 트리에 포함된 모든 전체 노드(Full Node)를 찾아 출력하는 것입니다.

핵심 개념 정리

이진 트리(Binary Tree)

이진 트리는 각 노드가 최대 2개의 자식 노드를 가질 수 있는 트리 구조입니다. 즉, 노드는 자식이 없거나, 왼쪽 또는 오른쪽 자식 하나만 가지거나, 두 자식을 모두 가질 수 있습니다.

전체 노드(Full Node)

전체 노드란 왼쪽 자식과 오른쪽 자식을 모두 가지고 있는 노드를 의미합니다. 다시 말해, 양쪽 자식이 모두 존재하는 노드가 바로 전체 노드입니다.

예시 −

위의 이진 트리에서 전체 노드는 4와 9입니다.

예제로 이해하기

구체적인 예시를 통해 문제를 살펴보겠습니다.

출력 − 4 9

해결 접근 방법

이 문제를 해결하는 가장 간단하고 직관적인 방법은 전위, 중위, 후위 순회 등 임의의 트리 순회 알고리즘을 사용해 트리를 탐색하는 것입니다. 탐색 과정에서 현재 노드가 왼쪽 자식과 오른쪽 자식을 모두 가지고 있는지 확인하고, 조건을 만족하면 해당 노드의 값을 출력하면 됩니다. 만족하지 않는 경우에는 별도의 작업 없이 다음 노드로 넘어갑니다.

구현 예제

다음은 위에서 설명한 해결 방법을 C++로 구현한 프로그램입니다.

#include <iostream>
using namespace std;
struct Node{
    int data;
    struct Node *left, *right;
};
Node *insertNode(int data){
    Node *temp = new Node;
    temp->data = data;
    temp->left = temp->right = NULL;
    return temp;
}
void printFullNode(Node *root){
    if (root != NULL){
        printFullNode(root->left);
        if (root->left != NULL && root->right != NULL)
            cout<<root->data<<"\t";
        printFullNode(root->right);
    }
}
int main(){
    Node* root = insertNode(100);
    root->left = insertNode(56);
    root->right = insertNode(12);
    root->left->left = insertNode(89);
    root->right->left = insertNode(32);
    root->right->right = insertNode(45);
    cout<<"All full nodes of the tree are :\n";
    printFullNode(root);
    return 0;
}

실행 결과

All full nodes of the tree are −
100 12

위 프로그램은 재귀적으로 트리를 순회하면서 왼쪽과 오른쪽 자식을 모두 가진 노드, 즉 전체 노드인 100과 12를 출력합니다. 시간 복잡도는 트리의 모든 노드를 한 번씩 방문하므로 O(N)이며, N은 트리의 노드 수입니다.