노드들로 구성된 이진 트리가 주어졌을 때, 해당 트리의 모든 노드 값을 곱한 결과를 구하는 것이 이 글의 목표입니다.
이진 트리에는 트리 내 모든 노드의 시작점 역할을 하는 루트(root) 노드가 존재합니다. 하나의 노드는 데이터 영역과, 왼쪽 하위 트리를 형성하는 왼쪽 포인터(left), 오른쪽 하위 트리를 형성하는 오른쪽 포인터(right)로 구성됩니다. 따라서 트리를 순회할 때는 임시 포인터를 활용해 왼쪽 포인터를 따라 왼쪽 하위 트리를 탐색하거나, 오른쪽 포인터를 따라 오른쪽 하위 트리를 탐색하는 방식으로 진행할 수 있습니다.
입력
출력
노드: 10, 20, 30, 40, 50, 60 곱 = 10 × 20 × 30 × 40 × 50 × 60 = 720,000,000
접근 방법
노드 데이터를 입력받습니다.
루트 노드에서 시작해 왼쪽 또는 오른쪽 하위 트리로 이동하면서 모든 노드를 순회합니다.
노드 데이터를 저장하고, 저장된 값에 새로운 데이터를 계속 곱해 나갑니다.
곱한 값을 보관하고 있는 임시 변수의 값을 출력합니다.
알고리즘
시작
1단계 → 노드 구조체 생성
structure node
int data
node *left, *right 생성
끝
2단계 → 트리에 노드를 삽입하는 함수 선언
node* new_node(int data)
node* temp = new node() 설정
temp→data = data 설정
temp→left = temp→right = NULL 설정
return temp
끝
3단계 → 모든 노드의 곱을 계산하는 함수 선언
int node_product(node* root)
IF root == NULL
return 1
End
return (root→data * node_product(root→left) *
node_product(root→right))
4단계 → main() 함수
node* root = new_node(10) 생성
root→left = new_node(20) 설정
root→right = new_node(30) 설정
int product = node_product(root) 설정
product 출력
종료
예제 코드
#include <iostream>
using namespace std;
// 노드 구조체 정의
struct node{
int data;
node *left, *right;
};
// 새 노드를 삽입하는 함수
node* new_node(int data){
node* temp = new node();
temp->data = data;
temp->left = temp->right = NULL;
return temp;
}
// 모든 노드의 곱을 계산하는 함수
int node_product(node* root){
if (root == NULL)
return 1;
return (root->data * node_product(root->left) * node_product(root->right));
}
int main(){
node* root = new_node(10);
root->left = new_node(20);
root->right = new_node(30);
root->left->left = new_node(40);
root->left->right = new_node(50);
root->right->left = new_node(60);
int product = node_product(root);
cout << "모든 노드의 곱은: " << product << endl;
return 0;
}
출력 결과
위 코드를 실행하면 다음과 같은 출력이 생성됩니다 −
모든 노드의 곱은: 720000000
트리의 모든 노드 값(10 × 20 × 30 × 40 × 50 × 60)을 곱하면 720,000,000(7억 2천만)이 됩니다. 이처럼 재귀 호출을 활용하면 각 노드를 한 번씩 방문하면서 곱을 자연스럽게 누적할 수 있으며, 빈 노드(NULL)를 만나면 곱셈에 영향을 주지 않도록 1을 반환하는 것이 핵심입니다. 이 알고리즘의 시간 복잡도는 트리의 모든 노드를 한 번씩 방문하므로 O(n)입니다.