이번 글에서는 사용자가 지정한 레벨 k에 존재하는 이진 트리(binary tree)의 리프 노드를 출력하는 방법을 알아보겠습니다.
리프 노드(leaf node)란 왼쪽과 오른쪽 자식 포인터가 모두 NULL인 노드를 의미합니다. 즉, 어떤 자식 노드도 가지지 않는 트리의 끝 노드이며, 부모 노드가 아닌 노드라고 할 수 있습니다.
예시
입력 : 11 22 33 66 44 88 77
출력 : 88 77
여기서 k는 출력 대상이 되는 트리의 레벨을 나타냅니다. 해결 방식은 모든 노드를 순회하면서 해당 노드가 자식 포인터를 가지고 있는지 검사하는 것입니다. 왼쪽이든 오른쪽이든 하나라도 포인터가 존재한다면 그 노드는 리프 노드가 될 수 없습니다.
각 노드는 재귀 호출을 통해 순회하며, 한 단계 내려갈 때마다 레벨 값을 1씩 감소시킵니다. 목표 레벨에 도달한 시점에서 해당 노드의 왼쪽과 오른쪽 포인터가 모두 NULL인지 확인하여 리프 노드 여부를 최종적으로 판별합니다.
아래 코드는 위 알고리즘을 C 언어로 구현한 예제입니다.
알고리즘
시작
1단계 -> 구조체 타입의 노드 변수 생성
정수형 data 선언
*left, *right 노드 타입 포인터 선언
2단계 -> new_data를 매개변수로 받는 노드 생성 함수 작성
malloc으로 노드 타입의 temp 변수 선언
temp->data = new_data 설정
temp->left = temp->right = NULL 설정
temp 반환
3단계 -> void leaf(struct node* root, int level) 함수 선언
IF root == NULL
종료
End
IF level == 1
IF root->left == NULL && root->right == NULL
root->data 출력
End
End
ELSE IF level > 1
leaf(root->left, level - 1) 호출
leaf(root->right, level - 1) 호출
End
4단계 -> main() 함수에서
level = 4 설정
struct node* root = New(11) 형태로 원하는 값을 삽입하며 트리 구성
leaf(root, level) 호출
종료
C 언어 구현 예제
#include<stdio.h>
#include<stdlib.h>
// 노드의 구조체 정의
struct node {
struct node* left;
struct node* right;
int data;
};
// 새로운 노드를 생성하는 함수
struct node* New(int data) {
struct node* temp = (struct node*)malloc(sizeof(struct node));
temp->data = data;
temp->left = NULL;
temp->right = NULL;
return temp;
}
// 리프 노드를 찾는 함수
void leaf(struct node* root, int level) {
if (root == NULL)
return;
if (level == 1) {
if (root->left == NULL && root->right == NULL)
printf("%d\n", root->data);
} else if (level > 1) {
leaf(root->left, level - 1);
leaf(root->right, level - 1);
}
}
int main() {
printf("leaf nodes are: ");
struct node* root = New(11);
root->left = New(22);
root->right = New(33);
root->left->left = New(66);
root->right->right = New(44);
root->left->left->left = New(88);
root->left->left->right = New(77);
int level = 4;
leaf(root, level);
return 0;
}
실행 결과
위 프로그램을 실행하면 다음과 같은 결과가 출력됩니다.
leaf nodes are: 88 77
레벨 4에 위치한 노드는 88과 77이며, 이 두 노드는 자식을 가지지 않으므로 리프 노드로 판별되어 화면에 출력됩니다.