이진 트리의 레벨 순서 순회
레벨 순서 순회는 이진 트리를 순회하는 방법 중 하나입니다. 이 기사에서는 C/C++에서 이 알고리즘을 구현하는 방법을 살펴보겠습니다.
그러나 그 전에 개념을 다루겠습니다.
개념 구축
이진 트리는 모든 노드가 최대 두 개의 자식을 갖는 데이터 구조입니다. 최상위 노드를 루트 노드라고 합니다.
이진 트리의 노드를 순회하는 일반적인 방법에는 다음과 같은 4가지가 있습니다.
- 순회순회
- 사전 주문 순회
- 주문 후 순회
- 레벨 순서 순회
이진 트리의 수준이 무엇을 의미하는지 이해해 봅시다.
수준은 트리의 주어진 노드에 해당하는 부모 노드의 수입니다. 기본적으로 해당 노드에서 루트 노드까지의 조상 수입니다.
따라서 루트 노드(최상위 노드)의 경우 부모가 없으므로 레벨이 0입니다. 자식이 있는 경우 루트 노드 자체인 루트 노드까지 단 하나의 조상만 있기 때문에 둘 다 수준이 1입니다.
또한 이진 트리의 높이 개념을 이해해야 합니다. 이것은 단순히 트리의 루트에서 가장 깊은 노드까지의 경로 길이입니다.
이 경우 높이는 가장 깊은 노드(최대 레벨이 있으므로 40 또는 50)에서 루트까지의 길이입니다. 따라서 트리의 높이는 2입니다.
이제 개념을 살펴보았으므로 레벨 순서 순회를 구현하는 방법을 이해하겠습니다.
레벨 순서 순회
레벨 순서 순회는 항상 트리의 레벨을 기준으로 순회하는 순회입니다.
따라서 이 순회는 먼저 레벨 0에 해당하는 노드를 순회한 다음 루트 노드에서 레벨 1 등으로 순회합니다.
위의 이진 트리 예제에서 레벨 순서 순회는 다음과 같습니다.
(루트) 10 -> 20 -> 30 -> 40 -> 50
이렇게 하려면 2가지 작업을 수행해야 합니다.
- 먼저 나무의 높이를 찾아야 합니다
- 모든 레벨에 해당하는 노드를 인쇄하는 방법을 찾아야 합니다.
나무의 높이 찾기
우리는 먼저 나무의 높이를 찾을 것입니다. 이렇게 하려면 논리가 간단합니다.
트리의 높이는 루트에서 리프까지의 가장 큰 경로로 정의되기 때문입니다. 따라서 왼쪽 및 오른쪽 하위 트리의 높이를 재귀적으로 계산하고 하위 트리의 최대 높이를 찾을 수 있습니다. 그러면 트리의 높이는 단순히 하위 트리의 높이 + 1이 됩니다.
C 스타일 의사 코드:
// Find height of a tree, defined by the root node
int tree_height(Node* root) {
if (root == NULL)
return 0;
else {
// Find the height of left, right subtrees
left_height = tree_height(root->left);
right_height = tree_height(root->right);
// Find max(subtree_height) + 1 to get the height of the tree
return max(left_height, right_height) + 1;
}
모든 수준의 모든 노드 인쇄
이제 높이가 있으므로 모든 레벨에 대한 노드를 인쇄해야 합니다. 이를 위해 for 루프를 사용하여 높이까지 모든 레벨을 반복하고 모든 레벨에서 노드를 인쇄합니다.
void print_tree_level_order(Node* root) {
int height = tree_height(root);
for (int i=0; i<height; i++) {
// Print the ith level
print_level(root, i);
}
}
트리의 i레벨을 인쇄하려면 다른 함수가 필요합니다.
여기서도 비슷한 논리가 있습니다. 그러나 이번에는 루트 노드를 인쇄한 후 루트 노드를 왼쪽 및 오른쪽 자식으로 변경하고 두 하위 트리를 모두 인쇄합니다.
이것은 리프 노드에 도달할 때까지 계속됩니다. 즉, 다음 단계에서 보조 루트가 NULL이 됩니다. (leaf_node->left=NULL이고 leaf_node->right=NULL이므로)
void print_level(Node* root, int level_no) {
// Prints the nodes in the tree
// having a level = level_no
// We have a auxiliary root node
// for printing the root of every
// sub-tree
if (!root)
return;
if (level_no == 0) {
// We are at the top of a sub-tree
// So print the auxiliary root node
printf("%d -> ", root->value);
}
else {
// Make the auxiliary root node to
// be the left and right nodes for
// the sub-trees and decrease level by 1, since
// you are moving from top to bottom
print_level(root->left, level_no - 1);
print_level(root->right, level_no - 1);
}
}
이제 드디어 Level Order Traversal을 완료했습니다!
아래에서 삽입을 사용하여 이진 트리를 구성하는 섹션이 있는 전체 프로그램을 제공합니다.
완전한 C/C++ 코드
이것은 원래 C 프로그램이지만 C++에서도 같은 것을 컴파일할 수 있습니다.
/**
Code for https://journaldev.com
File Name: level_order.c
Purpose: Find the Level Order Traversal of a Binary Tree
@author Vijay Ramachandran
@date 28/01/2020
*/
#include <stdio.h>
#include <stdlib.h>
typedef struct Node Node;
// Define the Tree Node here
struct Node {
int value;
// Pointers to the left and right children
Node* left, *right;
};
Node* init_tree(int data) {
// Creates the tree and returns the
// root node
Node* root = (Node*) malloc (sizeof(Node));
root->left = root->right = NULL;
root->value = data;
return root;
}
Node* create_node(int data) {
// Creates a new node
Node* node = (Node*) malloc (sizeof(Node));
node->value = data;
node->left = node->right = NULL;
return node;
}
void free_tree(Node* root) {
// Deallocates memory corresponding
// to every node in the tree.
Node* temp = root;
if (!temp)
return;
free_tree(temp->left);
free_tree(temp->right);
if (!temp->left && !temp->right) {
free(temp);
return;
}
}
int tree_height(Node* root) {
// Get the height of the tree
if (!root)
return 0;
else {
// Find the height of both subtrees
// and use the larger one
int left_height = tree_height(root->left);
int right_height = tree_height(root->right);
if (left_height >= right_height)
return left_height + 1;
else
return right_height + 1;
}
}
void print_level(Node* root, int level_no) {
// Prints the nodes in the tree
// having a level = level_no
// We have a auxiliary root node
// for printing the root of every
// subtree
if (!root)
return;
if (level_no == 0) {
// We are at the top of a subtree
// So print the auxiliary root node
printf("%d -> ", root->value);
}
else {
// Make the auxiliary root node to
// be the left and right nodes for
// the subtrees and decrease level by 1, since
// you are moving from top to bottom
print_level(root->left, level_no - 1);
print_level(root->right, level_no - 1);
}
}
void print_tree_level_order(Node* root) {
if (!root)
return;
int height = tree_height(root);
for (int i=0; i<height; i++) {
printf("Level %d: ", i);
print_level(root, i);
printf("\n");
}
printf("\n\n-----Complete Level Order Traversal:-----\n");
for (int i=0; i<height; i++) {
print_level(root, i);
}
printf("\n");
}
int main() {
// Program to demonstrate Level Order Traversal
// Create the root node having a value of 10
Node* root = init_tree(10);
// Insert nodes onto the tree
root->left = create_node(20);
root->right = create_node(30);
root->left->left = create_node(40);
root->left->right = create_node(50);
// Level Order Traversal
print_tree_level_order(root);
// Free the tree!
free_tree(root);
return 0;
}
산출
Level 0: 10 ->
Level 1: 20 -> 30 ->
Level 2: 40 -> 50 ->
-----Complete Level Order Traversal:-----
10 -> 20 -> 30 -> 40 -> 50 ->
이 목적을 위해 만든 Github gist를 통해 다운로드할 수도 있습니다. (삽입 코드도 포함)
결론
C/C++에서 레벨 순서 순회를 구현하는 방법을 더 잘 이해하셨기를 바랍니다. 질문이 있으시면 아래 댓글 섹션에서 언제든지 질문하십시오!