이진트리의 레벨 순회 (Level Order Traversal)
이진트리는 각 노드가 최대 두 개의 자식을 가지는 트리 자료구조입니다.
이진트리의 순회 방식 중 하나인 레벨 순회는 노드를 깊이(depth) 순서대로 방문합니다. 즉, 루트 노드에서 시작하여 같은 깊이의 노드를 왼쪽에서 오른쪽으로 방문한 후, 그다음 깊이의 노드를 같은 방식으로 방문하는 방법입니다. 레벨 순회는 큐(Queue)를 사용하여 구현할 수 있습니다.
같은 깊이의 노드를 왼쪽에서 오른쪽으로 방문한 후, 그 다음 깊이의 노드를 같은 방식으로 방문하는 방법
레벨 순회의 필요성 및 활용
레벨 순회는 다음과 같은 상황에서 유용하게 사용됩니다:
1. 최단 경로 문제: 트리의 특정 노드에서 가장 가까운 노드를 찾을 때 유용합니다.
2. 그래프의 너비 우선 탐색(BFS): 레벨 순회는 너비 우선 탐색과 동일한 원리로 동작합니다.
3. 트리의 높이 계산: 레벨 순회를 통해 트리의 각 레벨을 순차적으로 방문함으로써 트리의 높이를 계산할 수 있습니다.
4. 시스템 설계: 트리 구조의 각 레벨에 있는 노드들을 처리해야 하는 경우 (예: 트리 구조의 데이터베이스 처리) 유용합니다.
레벨 순회 알고리즘
레벨 순회는 큐를 사용하여 구현할 수 있습니다. 큐는 선입선출(FIFO) 자료구조로, 먼저 삽입된 데이터가 먼저 제거됩니다. 이 특성을 활용하여 레벨 순회를 다음과 같이 구현할 수 있습니다:
1. 루트 노드를 큐에 삽입합니다.
2. 큐가 비어 있지 않은 동안 다음을 반복합니다:
3. 큐의 맨 앞 노드를 제거하여 방문합니다.
4. 방문한 노드의 값을 출력합니다.
5. 방문한 노드의 왼쪽 자식이 있다면 큐에 삽입합니다.
6. 방문한 노드의 오른쪽 자식이 있다면 큐에 삽입합니다.
C언어로 구현한 레벨 순회
구조체 설명
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
typedef struct TreeNode { // 트리 노드 구조체 선언
int data;// 트리의 데이터
struct TreeNode *left, *right;//트리의 자식 노드 (이진)
} TreeNode;
typedef TreeNode* element;
typedef struct { // 큐 타입을 저장하는 구조체
element *data; // 데이터 저장 배열
int front, rear; // 포인터와 리어 변수
int size; // 배열의 사이즈
} QueueType;큐의 데이터 타입 (element)
⸰ typedef TreeNode element*
element 새로운 타입을 정의합니다. 이 타입은 TreeNode 구조체에 대한 포인터입니다.
즉, 트리 노드의 포인터가 큐의 요소로 사용됩니다.
트리 노드 구조체 (TreeNode)
⸰ struct TreeNode: 이 구조체는 트리의 노드를 나타내기 위해 사용됩니다.
⸰ int data: 트리 노드가 저장하는 데이터입니다. 여기서는 정수형 데이터를 저장합니다.
⸰ struct TreeNode *left: 트리 노드의 왼쪽 자식 노드를 가리키는 포인터입니다.
⸰ struct TreeNode *right: 트리 노드의 오른쪽 자식 노드를 가리키는 포인터입니다.
큐 구조체 (QueueType)
⸰ struct QueueType: 이 구조체는 원형 큐를 나타내기 위해 사용됩니다.
⸰ element *data
큐의 데이터를 저장하는 배열입니다. 여기서 element는 TreeNode 구조체에 대한 포인터 타입입니다.
따라서 이 배열은 트리 노드의 포인터들을 저장합니다.
⸰ int front: 큐의 가장 앞을 가리키는 인덱스입니다. 큐에서 데이터를 제거할 위치를 나타냅니다.
⸰ int rear: 큐의 가장 뒤를 가리키는 인덱스입니다. 큐에 데이터를 삽입할 위치를 나타냅니다.
i⸰ nt size: 큐의 전체 크기입니다. 배열의 최대 크기를 나타냅니다.
이 코드에서 트리 노드와 큐는 이진트리와 원형 큐를 구현하기 위한 기본적인 자료구조를 정의합니다. 이 구조체들을 사용하여 트리 노드의 삽입, 삭제 및 레벨 순회를 구현할 수 있습니다.
init 함수
void init(QueueType *Q):
- 함수의 반환형은 void이며, QueueType 구조체에 대한 포인터를 인수로 받습니다.
- 이 포인터는 초기화할 큐를 가리킵니다.
*Q->data = (element)malloc(sizeof(element)*Q->size)**:
- 큐의 데이터 저장 배열을 동적 할당합니다.
- 할당된 메모리의 크기는 sizeof(element) * Q->size입니다. 여기서 element는 트리 노드에 대한 포인터 타입입니다.
- 할당된 메모리 블록은 Q->data에 저장됩니다. 이를 통해 큐는 데이터 저장을 위한 배열을 갖게 됩니다.
Q->front = Q->rear = 0:
- 큐의 front와 rear를 모두 0으로 초기화합니다.
- front는 큐의 가장 앞을 가리키는 인덱스이며, 큐에서 데이터를 제거할 위치를 나타냅니다.
- rear는 큐의 가장 뒤를 가리키는 인덱스이며, 큐에 데이터를 삽입할 위치를 나타냅니다.
- 초기화 시 front와 rear가 모두 0이 되므로, 큐는 비어 있는 상태를 나타냅니다.
// 큐 초기화 함수
void init(QueueType *Q){
Q->data = (element*)malloc(sizeof(element)*Q->size); //데이터 저장 배열 동적할당
Q->front = Q->rear = 0; // 큐의 front와 rear를 초기화
}isEmpty / isFull 함수
int isEmpty(QueueType *Q) {return Q->front == Q->rear;}
int isFull(QueueType *Q) {return (Q->rear + 1) % Q->size == Q->front;}isEmpty 함수
동작 원리: 원형 큐에서 큐가 비어 있는 상태는 front와 rear가 같은 위치를 가리킬 때입니다.
큐를 초기화할 때 front와 rear를 같은 값(예: 0)으로 설정합니다.
큐에서 요소를 제거할 때마다 front가 증가하고, 큐에 요소를 삽입할 때마다 rear가 증가합니다.
이 경우, 큐가 비어 있으면 front와 rear가 다시 같은 위치를 가리키게 됩니다.
isFull 함수
동작 원리: 원형 큐에서 큐가 가득 차 있는 상태는 rear의 다음 위치가 front의 위치와 같을 때입니다.
이는 rear가 front 바로 뒤에 있는 상태로, 큐에 더 이상 요소를 삽입할 공간이 없음을 나타냅니다.
(Q->rear + 1) % Q->size는 rear의 다음 위치를 계산합니다.
% Q->size는 원형 큐의 특성을 유지하기 위해 사용됩니다.
rear가 배열의 끝에 도달하면 다시 배열의 시작으로 돌아가야 하기 때문입니다.
만약 이 계산된 위치가 front와 같다면, 큐는 가득 찬 상태입니다.
enqueue / dequeue 함수
void enqueue(QueueType *Q, element item) { // 큐에 데이터를 넣는 함수
if (isFull(Q)) {printf("Queue is full\n");exit(1);} //큐가 가득 차있으면 메세지를 출력하고 종료
Q->rear = (Q->rear + 1) % Q->size; // 리어를 증가하고, 증가된 리어의 위치에 데이터 저장(증가되지 않은 리어에는 이미 데이터 저장 되있음)
Q->data[Q->rear] = item;
}
element dequeue(QueueType *Q) { // 큐에 데이터를 빼는 함수
if (isEmpty(Q)) {printf("Queue is empty\n");exit(1);} //큐가 비어있으면 데이터를 뺄 수 없으므로 메세지 출력 후 종료
Q->front = (Q->front + 1) % Q->size;
return Q->data[Q->front];
}enqueue 함수
초기 상태
큐에 데이터를 인큐 하는 과정을 단계별로 설명드리겠습니다.
초기 상태에서 큐는 비어 있으며, front와 rear는 모두 0을 가리킵니다. 큐의 배열은 다음과 같습니다:
⸰ front = 0
⸰ rear = 0
⸰ data = [_, _, _, _, _, _, _, _, _, _] (여기서 _는 빈 공간을 의미합니다)
▶ 첫 번째 데이터 삽입
예를 들어, 첫 번째 데이터로 A를 삽입한다고 가정합니다.
큐가 가득 찼는지 확인: 큐가 가득 찼는지 확인합니다. 이 단계에서 큐는 비어 있으므로 가득 차 있지 않습니다.
rear를 증가:
- rear를 1 증가시킵니다.
- 원형 큐의 특성을 유지하기 위해 배열의 크기 size로 나눈 나머지를 사용하여 rear의 위치를 계산합니다.
- 초기 rear가 0이므로, 증가한 rear는 1이 됩니다.
데이터 삽입: 증가된 rear 위치에 데이터를 삽입합니다. 이 경우, data [1]에 A를 저장합니다.
⸰ front = 0
⸰ rear = 1
⸰ data = [_, A, _, _, _, _, _, _, _, _]
▶ 두 번째 데이터 삽입
이번에는 두 번째 데이터로 B를 삽입한다고 가정합니다.
큐가 가득 찼는지 확인: 큐가 가득 찼는지 확인합니다. 아직 큐에 여유 공간이 있으므로, 가득 차 있지 않습니다.
rear를 증가: rear를 1 증가시킵니다. 현재 rear는 1이므로, 증가한 rear는 2가 됩니다.
데이터 삽입: 증가된 rear 위치에 데이터를 삽입합니다. 이 경우, data [2]에 B를 저장합니다.
⸰ front = 0
⸰ rear = 2
⸰ data = [_, A, B, _, _, _, _, _, _, _]
▶ 세 번째 데이터 삽입
마찬가지로, 세 번째 데이터로 C를 삽입한다고 가정합니다.
큐가 가득 찼는지 확인: 큐가 가득 찼는지 확인합니다. 큐에 여전히 여유 공간이 있으므로, 가득 차 있지 않습니다.
rear를 증가: rear를 1 증가시킵니다. 현재 rear는 2이므로, 증가한 rear는 3이 됩니다.
데이터 삽입: 증가된 rear 위치에 데이터를 삽입합니다. 이 경우, data [3]에 C를 저장합니다.
⸰ front = 0
⸰ rear = 3
⸰ data = [_, A, B, C, _, _, _, _, _, _]
이제 큐의 상태는 다음과 같습니다:
이와 같은 과정으로 큐에 데이터를 계속 삽입할 수 있습니다. 큐가 가득 차지 않는 한, rear를 증가시키고 해당 위치에 데이터를 삽입하는 방식으로 동작합니다.
큐가 원형 구조를 갖기 때문에, rear가 배열의 끝에 도달하면 다시 배열의 시작으로 돌아갑니다. 예를 들어, rear가 배열의 마지막 인덱스에 도달하면 다음 삽입 위치는 배열의 첫 번째 인덱스가 됩니다.
dequeue 함수
이제 큐에서 데이터를 디큐(제거)하는 과정을 단계별로 설명하겠습니다.
초기 상태에서 큐에 데이터가 몇 개 있다고 가정하고 디큐 과정을 설명하겠습니다.
초기 상태
예를 들어, 큐에 A, B, C가 순서대로 삽입되어 있다고 가정합니다. 이때 큐의 상태는 다음과 같습니다:
⸰ front = 0
⸰ rear = 3
⸰ data = [_, A, B, C, _, _, _, _, _, _] (여기서 _는 빈 공간을 의미합니다)
▶ 첫 번째 데이터 제거 (디큐)
큐가 비어있는지 확인: 먼저 큐가 비어 있는지 확인합니다. 이 단계에서 큐는 비어 있지 않으므로 디큐를 진행할 수 있습니다.
front를 증가:
- front를 1 증가시킵니다.
- 원형 큐의 특성을 유지하기 위해 배열의 크기 size로 나눈 나머지를 사용하여 front의 위치를 계산합니다.
- 초기 front가 0이므로, 증가한 front는 1이 됩니다.
| Q->front = (Q->front + 1) % Q->size; |
- 위 코드에서 초기 front가 0이므로, front값을 증가하면 삭제할 (디큐)할 데이터에 접근하게 됩니다.
- 이후 증가된 front 위치의 데이터를 반환합니다. 이 경우, data [1]에 저장된 A를 반환합니다.
⸰ front = 1
⸰ rear = 3
⸰ data = [_, _, B, C, _, _, _, _, _, _] (데이터 A는 반환됨)
이제 큐의 상태는 다음과 같습니다:
▶ 두 번째 데이터 제거 (디큐)
큐가 비어있는지 확인: 큐가 비어 있는지 확인합니다. 이 단계에서 큐는 비어 있지 않으므로 디큐를 진행할 수 있습니다.
front를 증가: front를 1 증가시킵니다. 현재 front는 1이므로, 증가한 front는 2가 됩니다.
데이터 반환: 증가된 front 위치의 데이터를 반환합니다. 이 경우, data [2]에 저장된 B를 반환합니다.
⸰ front = 2
⸰ rear = 3
⸰ data = [_, _, _, C, _, _, _, _, _, _] (데이터 B는 반환됨)
이제 큐의 상태는 다음과 같습니다:
▶ 세 번째 데이터 제거 (디큐)
큐가 비어있는지 확인: 큐가 비어 있는지 확인합니다. 이 단계에서 큐는 비어 있지 않으므로 디큐를 진행할 수 있습니다.
front를 증가: front를 1 증가시킵니다. 현재 front는 2이므로, 증가한 front는 3이 됩니다.
데이터 반환: 증가된 front 위치의 데이터를 반환합니다. 이 경우, data [3]에 저장된 C를 반환합니다.
⸰ front = 3
⸰ rear = 3
⸰ data = [_, _, _, _, _, _, _, _, _, _] (데이터 C는 반환됨)
이제 큐의 상태는 다음과 같습니다:
큐가 비어있는지 확인:
큐가 비어있는 경우, 디큐를 할 수 없으며 오류 메시지를 출력합니다.
front를 증가:
front를 1 증가시켜 다음 위치를 가리키도록 합니다. 원형 큐의 특성을 유지하기 위해 배열의 크기 size로 나눈 나머지를 사용합니다.
데이터 반환:
증가된 front 위치의 데이터를 반환합니다.
이제 전체 디큐 과정을 종합해 보면, front는 큐의 앞쪽을 가리키고, 디큐 시 front를 증가시켜 다음 위치의 데이터를 반환하게 됩니다. 이 과정은 큐가 원형 구조를 가지도록 합니다.
front와 rear의 값을 변경하여, 실제 배열에서 삭제되지 않으나
접근을 못하게 함으로써 '삭제(디큐)'로 사용한다.
makeNode 함수 : 새로운 노드를 생성
// 새로운 노드를 생성하는 함수
TreeNode* makeNode(int data) {
TreeNode *newNode = (TreeNode *)malloc(sizeof(TreeNode));
newNode->data = data;
newNode->left = newNode->right = NULL;
return newNode;
}
TreeNode *newNode = (TreeNode *) malloc(sizeof(TreeNode)):
- malloc 함수를 사용하여 TreeNode 구조체 크기만큼의 메모리를 동적 할당합니다.
- 할당된 메모리의 시작 주소를 newNode 포인터에 저장합니다.
- TreeNode* 타입으로 캐스팅하여, newNode 포인터가 TreeNode 구조체 타입의 메모리를 가리키도록 합니다.
- 이 메모리는 새로 생성된 트리 노드가 됩니다.
newNode->data = data:
- 새로운 노드의 data 필드를 입력받은 인수 data로 초기화합니다.
- 이 필드는 노드가 저장하는 실제 데이터를 나타냅니다.
newNode->left = newNode->right = NULL:
- 새로운 노드의 left와 right 포인터를 모두 NULL로 초기화합니다.
- 이는 새로운 노드가 현재는 자식 노드가 없음을 나타냅니다.
- 이후 자식 노드를 추가할 때 이 포인터들을 적절히 설정할 수 있습니다.
return newNode:
- 초기화가 완료된 새로운 노드의 포인터를 반환합니다.
- 이 포인터는 새로 생성된 트리 노드를 가리킵니다.
levelOrder 함수 : 레벨 순회 함수
void levelOrder(TreeNode *root) {
if (!root) return;
QueueType Q;
init(&Q);
enqueue(&Q, root);
while (!isEmpty(&Q)) {
TreeNode *node = dequeue(&Q);
printf("%d ", node->data);
if (node->left) enqueue(&Q, node->left);
if (node->right) enqueue(&Q, node->right);
}
}위 코드는 이진트리를 레벨 순서대로 순회하는 함수 levelOrder를 정의하고 있습니다. 레벨 순회는 트리의 각 레벨을 왼쪽에서 오른쪽으로 방문하는 방식입니다. 이를 위해 큐를 사용하여 각 노드를 차례대로 방문합니다. 각 코드 라인에 대한 해석은 다음과 같습니다.
if (! root) return:
- 트리의 루트 노드가 NULL인 경우 (즉, 트리가 비어 있는 경우), 함수를 종료합니다.
- 이는 빈 트리에 대해 아무 작업도 하지 않도록 하기 위함입니다.
QueueType Q: 큐를 선언합니다. QueueType은 원형 큐 구조체 타입입니다.
init(&Q): 큐를 초기화합니다. 이 함수는 큐의 front와 rear를 초기화하고 데이터 저장 배열을 동적 할당합니다.
enqueue(&Q, root): 루트 노드를 큐에 삽입합니다. 루트 노드는 레벨 순회의 시작점입니다.
while (! isEmpty(&Q)):
- 큐가 비어 있지 않은 동안 반복합니다.
- 큐가 비어 있지 않다는 것은 아직 방문할 노드가 남아 있다는 의미입니다.
TreeNode *node = dequeue(&Q):
- 큐에서 노드를 제거하여 현재 노드로 설정합니다.
- dequeue 함수는 큐의 front 위치에서 노드를 제거하고 front를 증가시킵니다.
▷ printf("% d ", node->data): 현재 노드의 데이터를 출력합니다. 이로써 노드를 방문합니다.
▷ if (node->left) enqueue(&Q, node->left):
- 현재 노드의 왼쪽 자식이 존재하면, 왼쪽 자식을 큐에 삽입합니다.
- 이는 다음에 방문할 노드를 큐에 추가하는 과정입니다.
▷ if (node->right) enqueue(&Q, node->right):
- 현재 노드의 오른쪽 자식이 존재하면, 오른쪽 자식을 큐에 삽입합니다.
- 왼쪽 자식과 마찬가지로, 다음에 방문할 노드를 큐에 추가하는 과정입니다.
아래 글을 통해 알고리즘을 상세히 분석할 수 있습니다.
레벨 순회에서 다음 코드는 큐를 이용해 트리의 각 레벨을 순차적으로 방문하는 과정을 보여줍니다.
여기서 큐는 다음에 방문할 노드를 저장하는 데 사용됩니다.
초기 상태
루트 노드를 큐에 추가한 후, 초기 상태는 다음과 같습니다:
1. 큐에 루트 노드가 저장됩니다.
2. front와 rear는 각각 큐의 시작과 끝을 가리킵니다.
단계별 설명
1. 루트 노드를 큐에 삽입
enqueue(&Q, root);
• 루트 노드를 큐에 추가합니다.
• 큐의 rear 포인터를 증가시키고, 루트 노드를 큐의 rear 위치에 저장합니다.
큐 상태:
⸰ front = 0
⸰ rear = 1
⸰ data = [root, _, _, _, _, _, _, _, _, _] (여기서 root는 트리의 루트 노드입니다)
2. 반복문 시작
while (! isEmpty(&Q)) {
• 큐가 비어 있지 않은 동안 반복문을 실행합니다.
• 이 반복문은 큐에 방문할 노드가 남아 있는 동안 계속 실행됩니다.
3. 큐에서 노드를 제거하여 현재 노드로 설정
TreeNode *node = dequeue(&Q);
• 큐의 front 위치에서 노드를 제거하여 현재 노드로 설정합니다.
• front 포인터를 증가시킵니다.
• 큐 상태:
⸰ front = 1
⸰ rear = 1
⸰ data = [_, root, _, _, _, _, _, _, _, _] (여기서 root는 제거된 상태)
4. 현재 노드의 데이터 출력
printf("% d ", node->data);
• 현재 노드의 데이터를 출력합니다.
• 이는 현재 방문 중인 노드를 출력하는 것입니다.
5. 왼쪽 자식 노드가 있는 경우 큐에 삽입
if (node->left) enqueue(&Q, node->left);
• 현재 노드의 왼쪽 자식 노드가 존재하는지 확인합니다.
• 존재한다면, 그 노드를 큐에 삽입합니다.
큐 상태:
⸰ front = 1
⸰ rear = 2
⸰ data = [_, root, node->left, _, _, _, _, _, _, _] (여기서 node->left는 왼쪽 자식 노드)
6. 오른쪽 자식 노드가 있는 경우 큐에 삽입
if (node->right) enqueue(&Q, node->right);
• 현재 노드의 오른쪽 자식 노드가 존재하는지 확인합니다.
• 존재한다면, 그 노드를 큐에 삽입합니다.
큐 상태:
⸰ front = 1
⸰ rear = 3
⸰ data = [_, root, node->left, node->right, _, _, _, _, _, _] (여기서 node->right는 오른쪽 자식 노드)
다음 반복
반복문은 큐가 비어 있지 않은 동안 계속됩니다.
1. 큐에서 다음 노드를 제거하고,
2. 그 노드의 데이터를 출력한 다음,
3. 그 노드의 자식 노드를 큐에 삽입합니다.
이 과정은 큐가 비어 있을 때까지 반복됩니다.
전체 순회 과정 예시
• 트리가 다음과 같다고 가정합니다:
1
/ \
2 3
/ \ / \
4 5 6 7
큐의 상태 변화와 함께 레벨 순회를 설명하면:
루트 노드(1) 삽입 후 상태:
front = 0
rear = 1
data = [1, _, _, _, _, _, _, _, _, _]
노드 1 제거, 데이터 출력 후 자식 노드(2, 3) 삽입:
front = 1
rear = 3
data = [_, 1, 2, 3, _, _, _, _, _, _]
출력: 1
노드 2 제거, 데이터 출력 후 자식 노드(4, 5) 삽입: 노드 2의 자식 노드 (4,5)
front = 2
rear = 5
data = [_, _, 2, 3, 4, 5, _, _, _, _]
출력: 1 2
노드 3 제거, 데이터 출력 후 자식 노드(6, 7) 삽입: 노드 3의 자식 노드 (6,7)
front = 3
rear = 7
data = [_, _, _, 3, 4, 5, 6, 7, _, _]
출력: 1 2 3
노드 4 제거, 데이터 출력 (자식 없음):
front = 4
rear = 7
data = [_, _, _, _, 4, 5, 6, 7, _, _]
출력: 1 2 3 4
노드 5 제거, 데이터 출력 (자식 없음):
front = 5
rear = 7
data = [_, _, _, _, _, 5, 6, 7, _, _]
출력: 1 2 3 4 5
노드 6 제거, 데이터 출력 (자식 없음):
front = 6
rear = 7
data = [_, _, _, _, _, _, 6, 7, _, _]
출력: 1 2 3 4 5 6
노드 7 제거, 데이터 출력 (자식 없음):
front = 7
rear = 7
data = [_, _, _, _, _, _, _, 7, _, _]
출력: 1 2 3 4 5 6 7
요약
이 과정을 통해 트리의 각 레벨을 순차적으로 방문하며 노드를 출력하게 됩니다. 큐를 사용하여 방문할 노드를 저장하고, 이를 통해 레벨 순회를 효율적으로 수행할 수 있습니다.
코드 해석
이 함수는 이진트리를 레벨 순서대로 순회하며, 큐를 사용하여 각 레벨의 노드를 방문합니다. 과정은 다음과 같습니다:
1. 루트 노드 확인: 트리가 비어 있는지 확인하고, 비어 있다면 함수를 종료합니다.
2. 큐 초기화: 큐를 초기화하여, 순회 과정에서 사용할 수 있도록 준비합니다.
3. 루트 노드 삽입: 루트 노드를 큐에 삽입하여 순회를 시작합니다.
4. 큐가 비어 있지 않은 동안 반복: 큐가 비어 있지 않을 때까지 반복하여 모든 노드를 방문합니다.
5. 노드 방문 및 자식 노드 추가:
1) 큐에서 노드를 제거하고 해당 노드를 방문합니다.
2) 현재 노드의 왼쪽 자식이 있으면 큐에 삽입합니다.
3) 현재 노드의 오른쪽 자식이 있으면 큐에 삽입합니다.
main 함수
// 메인 함수
int main() {
// 이진 트리 생성
TreeNode *root = makeNode(1);
root->left = makeNode(2);
root->right = makeNode(3);
root->left->left = makeNode(4);
root->left->right = makeNode(5);
root->right->left = makeNode(6);
root->right->right = makeNode(7);
// 레벨 순회 출력
printf("Level Order Traversal: ");
levelOrder(root);
printf("\n");
return 0;
}전체 코드
다음은 C언어를 사용하여 이진트리의 레벨 순회를 구현한 예제 코드입니다:
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
typedef struct TreeNode { // 트리 노드 구조체 선언
int data;// 트리의 데이터
struct TreeNode *left, *right;//트리의 자식 노드 (이진)
} TreeNode;
typedef TreeNode* element;
typedef struct { // 큐 타입을 저장하는 구조체
element *data; // 데이터 저장 배열
int front, rear; // 포인터와 리어 변수
int size; // 배열의 사이즈
} QueueType;
// 큐 초기화 함수
void init(QueueType *Q){
Q->data = (element*)malloc(sizeof(element)*Q->size); //데이터 저장 배열 동적할당
Q->front = Q->rear = 0; // 큐의 front와 rear를 초기화
}
int isEmpty(QueueType *Q) {return Q->front == Q->rear;}
int isFull(QueueType *Q) {return (Q->rear + 1) % Q->size == Q->front;}
void enqueue(QueueType *Q, element item) {
if (isFull(Q)) {
printf("Queue is full\n");
exit(1);
}
Q->rear = (Q->rear + 1) % Q->size;
Q->data[Q->rear] = item;
}
element dequeue(QueueType *Q) {
if (isEmpty(Q)) {
printf("Queue is empty\n");
exit(1);
}
Q->front = (Q->front + 1) % Q->size;
return Q->data[Q->front];
}
// 새로운 노드를 생성하는 함수
TreeNode* makeNode(int data) {
TreeNode *newNode = (TreeNode *)malloc(sizeof(TreeNode));
newNode->data = data;
newNode->left = newNode->right = NULL;
return newNode;
}
// 레벨 순회 함수 정의
void levelOrder(TreeNode *root) {
if (!root) return;
QueueType Q;
init(&Q);
enqueue(&Q, root);
while (!isEmpty(&Q)) {
TreeNode *node = dequeue(&Q);
printf("%d ", node->data);
if (node->left) enqueue(&Q, node->left);
if (node->right) enqueue(&Q, node->right);
}
}
// 메인 함수
int main() {
// 이진 트리 생성
TreeNode *root = makeNode(1);
root->left = makeNode(2);
root->right = makeNode(3);
root->left->left = makeNode(4);
root->left->right = makeNode(5);
root->right->left = makeNode(6);
root->right->right = makeNode(7);
// 레벨 순회 출력
printf("Level Order Traversal: ");
levelOrder(root);
printf("\n");
return 0;
}'Datastructure > [8] 트리' 카테고리의 다른 글
| [8] 트리 ⑥ 응용 (1) : 연결리스트를 이용한 트리 구현 (1) | 2024.06.05 |
|---|---|
| [8] 트리 ⑤ 스택을 이용한 이진 트리 (1) | 2024.06.04 |
| [8] 트리 ③ 원형 큐 (0) | 2024.06.03 |
| [8] 트리 ② 트리의 구현 : ADT (0) | 2024.05.30 |
| [8] 트리 ① 트리의 정의 (1) | 2024.05.29 |
