이번 글에서는 주어진 이진 트리(binary tree)의 왼쪽 뷰(left view)를 출력하는 방법을 다룹니다. 사용자가 데이터를 입력하면 이진 트리가 생성되고, 이렇게 만들어진 트리의 왼쪽 뷰를 화면에 출력하는 것이 프로그램의 목표입니다.
이진 트리 왼쪽 뷰란?
이진 트리의 왼쪽 뷰란 트리를 왼쪽에서 바라볼 때 보이는 노드들, 즉 각 레벨(level)에서 가장 왼쪽에 위치한 노드들을 의미합니다.
이진 트리의 모든 노드는 최대 2개의 자식 노드를 가질 수 있으므로, 프로그램은 각 노드에 연결된 포인터 중 왼쪽 포인터만 순차적으로 따라가면 됩니다.
왼쪽 포인터가 NULL이 아니라면 그 포인터에는 데이터나 다른 노드가 연결되어 있는 것이고, 더 이상 왼쪽 자식이 없다면 해당 지점이 출력 대상이 되는 왼쪽 뷰의 노드입니다.
예시
입력 : 1 0 3 2 4
출력 : 1 0 2
위 그림에서 주황색으로 표시된 노드들이 이진 트리의 왼쪽 뷰에 해당합니다.
데이터 1을 가진 노드가 루트(root) 노드이므로 가장 먼저 출력됩니다. 이후 왼쪽 자식으로 이동하면 0이 출력되고, 다음으로 오른쪽 서브트리의 3으로 이동해 그 왼쪽 자식인 2를 출력합니다.
이 문제는 재귀(recursion) 접근 방식을 활용해 노드의 레벨을 추적하고, 새로운 레벨에 도달할 때마다 해당 노드를 출력하는 방식으로 해결할 수 있습니다.
알고리즘
시작
단계 1 -> 구조체 타입의 노드 변수 생성
int data 선언
노드 타입 포인터 *left, *right 선언
단계 2 -> new_data를 매개변수로 받는 노드 생성 함수 작성
malloc을 사용해 node 타입의 temp 변수 선언
temp->data = new_data 설정
temp->left = temp->right = NULL 설정
temp 반환
단계 3 -> void left_view(struct node* root, int level, int* highest_level) 함수 선언
IF root = NULL
종료
End
IF *highest_level < level
root->data 출력
*highest_level = level 설정
End
left_view(root->left, level + 1, highest_level) 재귀 호출
left_view(root->right, level + 1, highest_level) 재귀 호출
단계 4 -> void left(struct node* root) 함수 선언
int highest_level = 0 설정
left_view(root, 1, &highest_level) 호출
단계 5 -> main() 함수에서
struct node* root = New(1) 형태로 사용자가 삽입할 값 전달
left(root) 호출
종료
C 언어 구현 코드
#include <stdio.h>
#include <stdlib.h>
// 노드 구조체 생성
struct node {
int data;
struct node *left, *right; // 노드에 연결된 자식 노드를 가리키는 포인터
};
struct node* New(int new_data) {
struct node* temp = (struct node*)malloc(sizeof(struct node));
// 포인터에 동적으로 메모리 할당
temp->data = new_data;
temp->left = temp->right = NULL;
return temp;
}
void left_view(struct node* root, int level, int* highest_level) {
if (root == NULL) // 노드가 없으면 데이터도 없으므로 종료
return;
// 트리에 루트 노드만 존재한다면 루트 노드를 그대로 출력
if (*highest_level < level) {
printf("%d\t", root->data);
*highest_level = level;
}
// 재귀 호출
left_view(root->left, level + 1, highest_level);
left_view(root->right, level + 1, highest_level);
}
void left(struct node* root) {
int highest_level = 0;
left_view(root, 1, &highest_level);
}
int main() {
printf("left view of a binary tree is : ");
struct node* root = New(1);
root->left = New(0);
root->right = New(3);
root->right->left = New(2);
root->right->right = New(4);
left(root);
return 0;
}
실행 결과
위 프로그램을 실행하면 다음과 같은 결과가 출력됩니다.
left view of a binary tree is : 1 0 2
동작 원리 정리
핵심은 highest_level 변수입니다. 재귀 호출 시 현재 노드의 레벨(level)이 지금까지 방문한 최고 레벨보다 크다면, 해당 노드는 그 레벨에서 처음 도달한 노드, 즉 왼쪽 뷰에 포함되는 노드입니다. 따라서 노드 값을 출력하고 highest_level을 갱신합니다. 왼쪽 서브트리를 먼저 순회하기 때문에 각 레벨에서 가장 왼쪽에 있는 노드가 항상 먼저 발견됩니다.
이 알고리즘은 트리의 모든 노드를 한 번씩 방문하므로 시간 복잡도는 O(n)이며, 재귀 호출 깊이는 트리의 높이에 비례합니다.