C 언어로 구현하는 이진 트리 오른쪽 뷰(Right View) 출력 방법

이번 글에서 다룰 과제는 주어진 이진 트리의 오른쪽 뷰(Right View), 즉 각 레벨에서 가장 오른쪽에 있는 노드들을 출력하는 것입니다. 사용자가 데이터를 입력하여 이진 트리를 생성하면, 완성된 트리의 오른쪽 뷰를 화면에 출력하게 됩니다.

위 다이어그램은 10, 42, 93, 14, 35, 96, 57, 88 노드로 구성된 이진 트리를 보여줍니다. 이 노드들 중 트리의 오른쪽 측면에 위치한 노드들만 골라 화면에 표시합니다. 예를 들어 10, 93, 57, 88이 이진 트리의 오른쪽 뷰에 해당하는 노드입니다.

예제

입력 : 10 42 93 14 35 96 57 88
출력 : 10 93 57 88

각 노드에는 왼쪽(left)과 오른쪽(right) 두 개의 포인터가 존재합니다. 하지만 이 문제에서는 오른쪽 노드만 순회하면 되므로, 노드의 왼쪽 자식은 신경 쓸 필요가 없습니다.

오른쪽 뷰는 각 레벨(깊이)에서 마지막에 위치한 노드들을 모두 저장한 결과입니다. 따라서 오른쪽 서브트리를 왼쪽 서브트리보다 먼저 순회하도록 재귀적 접근 방식을 활용하면 손쉽게 구현할 수 있습니다. 프로그램이 순회 중 현재 노드의 레벨이 지금까지 기록된 최대 레벨보다 클 경우, 해당 노드는 자신이 속한 레벨의 마지막 노드이므로 그대로 출력하면 됩니다.

알고리즘

START
    Step 1 -> 구조체 타입으로 노드 변수 생성
        int data 선언
        node 타입 포인터 *left, *right 선언
    Step 2 -> item을 매개변수로 받아 노드를 삽입하는 함수 생성
        malloc으로 node 타입 temp 변수 선언
        temp->data = item 설정
        temp->left = temp->right = NULL 설정
        temp 반환
    Step 3 -> void right_view(struct node *root, int level, int *end_level) 함수 선언
        IF root == NULL
            Return
        IF *end_level < level
            root->data 출력
            *end_level = level 설정
            right_view(root->right, level+1, end_level) 호출
            right_view(root->left, level+1, end_level) 호출
    Step 4 -> void right(struct node *root) 함수 선언
        int level = 0 설정
        right_view(root, 1, &level) 호출
    Step 5 -> main() 함수에서
        struct node *root = New(10)로 트리 노드 값 전달
        right(root) 호출
STOP

C 언어 구현 코드

아래 코드는 앞서 설명한 알고리즘을 C 언어로 구현한 예제입니다.

#include<stdio.h>
#include<stdlib.h>
struct node {
    int data;
    struct node *left, *right;
};
struct node *New(int item) {
    struct node *temp = (struct node *)malloc(sizeof(struct node));
    temp->data = item;
    temp->left = temp->right = NULL;
    return temp;
}
void right_view(struct node *root, int level, int *end_level) {
    if (root == NULL) return;
    if (*end_level < level) {
        printf("%d\t", root->data);
        *end_level = level;
    }
    right_view(root->right, level+1, end_level);
    right_view(root->left, level+1, end_level);
}
void right(struct node *root) {
    int level = 0;
    right_view(root, 1, &level);
}
int main() {
    printf("right view of a binary tree is : ");
    struct node *root = New(10);
    root->left = New(42);
    root->right = New(93);
    root->left->left = New(14);
    root->left->right = New(35);
    root->right->left = New(96);
    root->right->right = New(57);
    root->right->left->right = New(88);
    right(root);
    return 0;
}

실행 결과

위 프로그램을 실행하면 다음과 같은 결과가 출력됩니다.

right view of a binary tree is : 10 93 57 88

동작 원리 정리

핵심은 end_level 변수입니다. 이 변수는 지금까지 방문한 노드 중 가장 깊은 레벨을 추적합니다. 오른쪽 서브트리를 우선적으로 순회하기 때문에, 각 레벨에 도달하는 첫 번째 노드가 항상 해당 레벨의 가장 오른쪽 노드가 됩니다. 따라서 현재 노드의 레벨이 end_level보다 클 때만 출력하고 값을 갱신하면, 모든 레벨의 오른쪽 끝 노드만 정확히 걸러낼 수 있습니다.