이진 트리가 주어졌을 때, 트리에 존재하는 비잎 노드(Non-Leaf Node)의 개수를 계산하는 것이 이 글의 목표입니다.
이진 트리란?
이진 트리(Binary Tree)는 데이터를 저장하기 위해 사용되는 특수한 자료구조입니다. 이진 트리는 각 노드가 최대 두 개의 자식 노드만 가질 수 있다는 특별한 조건을 가지고 있습니다.
이진 트리는 정렬된 배열과 연결 리스트의 장점을 모두 갖춘 자료구조입니다. 탐색 속도는 정렬된 배열만큼 빠르고, 삽입·삭제 연산은 연결 리스트만큼 빠르게 수행할 수 있기 때문입니다.
비잎 노드는 자식 노드를 하나 이상 가진 노드를 의미하며, 자식이 있는 노드라는 의미에서 부모 노드(Parent Node)라고도 불립니다.
예시
입력 −
출력 − 비잎 노드의 개수: 3
설명 − 주어진 트리에서 27, 14, 35는 자식 노드를 가지고 있으므로 비잎 노드에 해당합니다.
접근 방법
아래 프로그램에서 사용한 접근 방식은 다음과 같습니다.
- 왼쪽 노드 포인터, 오른쪽 노드 포인터, 그리고 노드에 저장될 데이터를 포함하는 이진 트리 구조체를 정의합니다.
- 함수가 호출될 때마다 새 노드를 생성·삽입하는 함수를 만듭니다. 이 함수는 새 노드에 데이터를 저장하고, 새 노드의 왼쪽과 오른쪽 포인터를 NULL로 설정한 뒤 해당 노드를 반환합니다.
- 이진 트리에서 비잎 노드의 개수를 세는 재귀 함수를 작성합니다.
- 루트가 NULL이거나, 루트의 왼쪽 자식과 오른쪽 자식이 모두 NULL이라면 0을 반환합니다.
- 그렇지 않으면 1에 왼쪽 포인터를 인자로 한 재귀 호출의 결과와 오른쪽 포인터를 인자로 한 재귀 호출의 결과를 더하여 반환합니다.
- 최종 개수를 출력합니다.
예제 코드
#include <iostream>
using namespace std;
// 노드 구조체 정의
struct Node {
int data;
struct Node* left;
struct Node* right;
};
// 새 노드 생성 함수
struct Node* newNode(int data){
struct Node* node = new Node;
node->data = data;
node->left = node->right = NULL;
return (node);
}
// 비잎 노드 개수 세기
int nonleaf(struct Node* root){
if (root == NULL || (root->left == NULL && root->right == NULL)){
return 0;
}
return 1 + nonleaf(root->left) + nonleaf(root->right);
}
// 메인 함수
int main(){
struct Node* root = newNode(10);
root->left = newNode(21);
root->right = newNode(33);
root->left->left = newNode(48);
root->left->right = newNode(51);
cout << "count of non-leaf nodes is: " << nonleaf(root);
return 0;
}실행 결과
위 코드를 실행하면 다음과 같은 결과가 출력됩니다.
count of non-leaf nodes is: 2
이 예제 트리에서 비잎 노드는 루트인 10과 왼쪽 자식인 21입니다. 노드 33, 48, 51은 자식이 없는 잎 노드이므로 개수에 포함되지 않아 결과적으로 2가 출력됩니다. 이처럼 재귀적으로 각 노드를 방문하면서 자식 노드의 존재 여부만 확인하면, 전체 트리를 한 번씩만 순회하여 O(n)의 시간 복잡도로 비잎 노드의 개수를 효율적으로 구할 수 있습니다.