이진 트리가 하나 주어졌을 때, 반복(iterative)과 재귀(recursive) 두 가지 접근 방식을 사용해 트리에 존재하는 풀 노드(full node)의 개수를 계산하는 것이 이 글의 목표입니다. 풀 노드란 왼쪽과 오른쪽 자식을 모두 가지고 있으며, null인 자식이 없는 노드를 의미합니다. 즉, 정확히 두 개의 자식을 가진 노드만 풀 노드로 간주합니다.
이진 트리(Binary Tree)는 데이터 저장을 위해 사용되는 특수한 자료구조입니다. 이진 트리는 각 노드가 최대 두 개의 자식만 가질 수 있다는 조건을 갖습니다. 이진 트리는 정렬된 배열과 연결 리스트의 장점을 모두 지니고 있는데, 탐색 속도는 정렬된 배열만큼 빠르고, 삽입·삭제 연산은 연결 리스트만큼 빠릅니다. 자식을 하나 이상 가진 노드는 부모 노드(parent node)라고도 부릅니다.
이진 트리의 기본 구조는 다음과 같습니다.
예시
입력 −
출력 − 개수는 2
설명 − 주어진 트리에서 정확히 두 개의 자식을 가진 노드, 즉 풀 노드는 10과 20 두 개입니다. 나머지 노드들은 자식이 하나뿐이거나 자식이 전혀 없습니다.
반복(Iterative) 방법
아래 프로그램에 적용된 접근 방식
데이터 값, 왼쪽 포인터, 오른쪽 포인터를 담는 노드 구조체를 생성합니다.
이진 트리에 노드를 삽입하는 함수를 만듭니다.
풀 노드의 개수를 세는 함수를 만듭니다.
함수 안에서 먼저 !node 여부를 확인하고, 트리가 비어 있으면 바로 반환합니다.
풀 노드의 개수를 저장할 변수 count를 선언합니다.
큐(queue) 타입의 변수 qu를 생성합니다.
qu.push(node)로 루트 노드를 큐에 넣습니다.
!qu.empty() 조건으로 루프를 실행합니다.
Node 타입의 임시 변수 temp를 만들고 queue.front()로 초기화합니다.
qu.pop()으로 큐에서 요소를 꺼냅니다.
temp->left와 temp->right가 모두 NULL이 아니면 count를 1 증가시킵니다.
temp->left != NULL이면 qu.push(temp->left)를 수행합니다.
temp->right != NULL이면 qu.push(temp->right)를 수행합니다.
루프가 끝나면 count를 반환합니다.
결과를 출력합니다.
이 방식은 레벨 순서 순회(level order traversal, BFS)를 활용해 트리의 모든 노드를 한 번씩만 방문하므로 시간 복잡도는 O(n)입니다.
예제 코드
// Iterative program to count full nodes
#include <iostream>
#include <queue>
using namespace std;
struct Node{
int data;
struct Node* left, *right;
};
// Function to count the full Nodes in a binary tree
int fullcount(struct Node* node){
// Check if tree is empty
if (!node){
return 0;
}
queue<Node *> myqueue;
// traverse using level order traversing
int result = 0;
myqueue.push(node);
while (!myqueue.empty()){
struct Node *temp = myqueue.front();
myqueue.pop();
if (temp->left && temp->right){
result++;
}
if (temp->left != NULL){
myqueue.push(temp->left);
}
if (temp->right != NULL){
myqueue.push(temp->right);
}
}
return result;
}
struct Node* newNode(int data){
struct Node* node = new Node;
node->data = data;
node->left = node->right = NULL;
return (node);
}
int main(void){
struct Node *root = newNode(10);
root->left = newNode(20);
root->right = newNode(30);
root->left->left = newNode(40);
root->left->right = newNode(50);
root->left->left->right = newNode(60);
root->left->right->right = newNode(70);
cout <<"count is: "<<fullcount(root);
return 0;
}
출력
위 코드를 실행하면 다음과 같은 결과를 얻을 수 있습니다.
count is: 2
재귀(Recursive) 방법
아래 프로그램에 적용된 접근 방식
데이터 값, 왼쪽 포인터, 오른쪽 포인터를 담는 노드 구조체를 생성합니다.
이진 트리에 노드를 삽입하는 함수를 만듭니다.
풀 노드의 개수를 세는 함수를 만듭니다.
함수 안에서 root == NULL이면 트리에 노드가 없으므로 0을 반환합니다.
풀 노드의 개수를 저장할 변수 count를 선언합니다.
root->left와 root->right가 모두 존재하면 count를 1 증가시킵니다.
count = count + 왼쪽 서브트리에 대한 재귀 호출 결과 + 오른쪽 서브트리에 대한 재귀 호출 결과로 설정합니다.
count를 반환합니다.
결과를 출력합니다.
재귀 방식 역시 모든 노드를 한 번씩 방문하므로 시간 복잡도는 O(n)이며, 재귀 호출 스택으로 인해 공간 복잡도는 트리의 높이에 비례한다는 점을 참고하세요.
예제 코드
// Recursive program to count full nodes
#include <iostream>
using namespace std;
struct Node{
int data;
struct Node* left, *right;
};
// Function to get the count of full Nodes
int fullcount(struct Node* root){
if (root == NULL){
return 0;
}
int result = 0;
if (root->left && root->right){
result++;
}
result += (fullcount(root->left) +
fullcount(root->right));
return result;
}
struct Node* newNode(int data){
struct Node* node = new Node;
node->data = data;
node->left = node->right = NULL;
return (node);
}
int main(){
struct Node *root = newNode(10);
root->left = newNode(20);
root->right = newNode(30);
root->left->left = newNode(40);
root->left->right = newNode(50);
root->left->left->right = newNode(60);
root->left->right->right = newNode(70);
cout <<"count is: "<<fullcount(root);
return 0;
}
출력
위 코드를 실행하면 다음과 같은 결과를 얻을 수 있습니다.
count is: 2