이진 트리가 주어졌을 때, 반복(iterative) 방식과 재귀(recursive) 방식을 활용해 트리에 존재하는 반쪽 노드(half node)의 개수를 계산하는 방법을 알아보겠습니다. 반쪽 노드란 자식을 하나만 가지고 나머지 하나의 자식은 NULL인 노드를 말합니다. 단, 리프 노드는 반쪽 노드에 포함하지 않습니다.
이진 트리(Binary Tree)는 데이터 저장을 위해 사용되는 특수한 자료구조입니다. 이진 트리는 각 노드가 최대 두 개의 자식만 가질 수 있다는 조건을 갖습니다. 이진 트리는 정렬된 배열과 연결 리스트의 장점을 모두 갖추고 있습니다. 즉, 탐색은 정렬된 배열만큼 빠르고, 삽입·삭제 연산은 연결 리스트만큼 빠릅니다. 자식 수가 0보다 크고 2개 미만인 비-리프(non-leaf) 노드는 부모 노드(parent node)라고도 부릅니다.
이진 트리의 기본 구조는 아래와 같습니다.
예시
입력 −
출력 − 개수는 2
설명 − 주어진 트리에는 자식을 정확히 하나씩 가진 노드, 즉 반쪽 노드가 2개(40과 50) 있습니다. 나머지 노드들은 자식을 두 개 가지거나 전혀 가지지 않습니다.
반복(Iterative) 방식
아래 프로그램에 사용된 접근 방식
데이터 부분과 왼쪽 포인터, 오른쪽 포인터를 포함하는 노드 구조체를 생성합니다.
이진 트리에 노드를 삽입하는 함수를 만듭니다.
반쪽 노드의 개수를 세는 함수를 만듭니다.
함수 내부에서 !node이면 트리에 노드가 없다는 의미이므로 0을 반환합니다.
반쪽 노드의 개수를 저장할 임시 변수 count를 선언합니다.
큐(queue) 타입 변수, 예를 들어 qu를 생성합니다.
qu.push(node)로 루트 노드를 큐에 넣습니다.
!qu.empty()인 동안 반복문을 실행합니다.
Node 타입의 임시 변수 temp를 만들어 queue.front() 값으로 초기화합니다.
qu.pop()으로 요소를 꺼냅니다.
(!temp->left && temp->right) 또는 (temp->left && !temp->right)이면 count를 1 증가시킵니다.
temp->left가 NULL이 아니면 qu.push(temp->left)를 수행합니다.
temp->right가 NULL이 아니면 qu.push(temp->right)를 수행합니다.
count를 반환하고 결과를 출력합니다.
예제 코드
// 이진 트리에서 반쪽 노드 개수를 세는 프로그램
#include <iostream>
#include <queue>
using namespace std;
struct Node{
int data;
struct Node* left, *right;
};
// 반쪽 노드의 개수를 구하는 함수
int halfcount(struct Node* node){
// 트리가 비어 있는 경우
if (!node)
return 0;
int result = 0; // 반쪽 노드 개수 초기화
// 루트부터 시작하는 레벨 순서 순회(level order traversal)
queue<Node *> myqueue;
myqueue.push(node);
while (!myqueue.empty()){
struct Node *temp = myqueue.front();
myqueue.pop();
if ((!temp->left && temp->right) || (temp->left && !temp->right)){
result++;
}
if (temp->left != NULL){
myqueue.push(temp->left);
}
if (temp->right != NULL){
myqueue.push(temp->right);
}
}
return result;
}
/* 주어진 데이터와 NULL 좌·우 포인터를 가진 새 노드를 할당 */
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: "<<halfcount(root);
return 0;
}
출력
위 코드를 실행하면 다음과 같은 결과를 얻습니다 −
count is: 2
재귀(Recursive) 방식
아래 프로그램에 사용된 접근 방식
데이터 부분과 왼쪽 포인터, 오른쪽 포인터를 포함하는 노드 구조체를 생성합니다.
이진 트리에 노드를 삽입하는 함수를 만듭니다.
반쪽 노드의 개수를 세는 함수를 만듭니다.
함수 내부에서 !node이면 트리에 노드가 없으므로 0을 반환합니다.
반쪽 노드의 개수를 저장할 임시 변수 count를 선언합니다.
(root->left == NULL && root->right != NULL) 또는 (root->left != NULL && root->right == NULL)이면 count를 1 증가시킵니다.
count = count + halfcount(root->left) + halfcount(root->right) 형태로 재귀 호출 결과를 더합니다.
count를 반환하고 결과를 출력합니다.
예제 코드
// 반쪽 노드 개수를 세는 재귀 프로그램
#include <bits/stdc++.h>
using namespace std;
// 이진 트리 노드는 데이터와 왼쪽 자식 포인터,
// 오른쪽 자식 포인터를 가진다
struct Node{
int data;
struct Node* left, *right;
};
int halfcount(struct Node* root){
if (root == NULL)
return 0;
int result = 0;
if ((root->left == NULL && root->right != NULL) || (root->left != NULL && root->right ==
NULL)){
result++;
}
result += (halfcount(root->left) + halfcount(root->right));
return result;
}
/* 주어진 데이터와 NULL 좌·우 포인터를 가진 새 노드를 할당 */
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: "<<halfcount(root);
return 0;
}
출력
위 코드를 실행하면 다음과 같은 결과를 얻습니다 −
count is: 2