스택과 이진트리 정의
스택 (Stack)
스택은 선형 자료구조로, 가장 나중에 삽입된 데이터가 가장 먼저 삭제되는 LIFO(Last In First Out) 특성을 가집니다. 주요 연산으로는 데이터 삽입(Push), 삭제(Pop), 피크(Peek), 공백 상태 검출(IsEmpty), 포화 상태 검출(IsFull) 등이 있습니다.
이진 트리 (Binary Tree)
이진 트리는 각 노드가 최대 두 개의 자식 노드를 가지는 트리 자료구조입니다. 각 노드는 데이터를 포함하며, 왼쪽 자식 노드와 오른쪽 자식 노드를 가리키는 포인터를 가집니다.
주요 순회 방식으로는 전위 순회(Pre-order), 중위 순회(In-order), 후위 순회(Post-order) 등이 있습니다.
스택 구조체 설명
스택(Stack)은 후입선출(LIFO, Last In First Out) 방식으로 데이터를 저장하고 관리하는 선형 자료구조입니다. 스택 구조체는 다음과 같은 요소들로 구성됩니다:
- 데이터 배열: 스택의 요소들을 저장하는 배열입니다. 예제 코드에서는 TreeNode* data[N]로 정의되어 있습니다. 이 배열은 최대 N개의 요소를 저장할 수 있습니다.
- top: 스택의 현재 위치를 나타내는 인덱스입니다. 초기 상태에서는 -1로 설정되어 있습니다. 요소가 추가되면 top이 증가하고, 요소가 제거되면 top이 감소합니다.
스택 구조체의 정의는 다음과 같습니다:
typedef struct {
TreeNode* data[N]; // 스택의 배열: 최대 용량은 100
int top; // (현재 스택의 데이터 개수 - 1)
} StackType;트리 구조체 설명
트리(Tree)는 계층적 구조를 가지는 비선형 자료구조로, 각 노드는 데이터를 가지고 있으며 자식 노드로의 포인터를 통해 연결됩니다. 이진 트리(Binary Tree)는 각 노드가 최대 두 개의 자식 노드를 가지는 트리입니다.
트리 구조체는 다음과 같은 요소들로 구성됩니다:
- 데이터: 노드가 저장하는 값입니다. 예제 코드에서는 element data로 정의되어 있습니다.
- 부모 노드 포인터: 부모 노드를 가리키는 포인터입니다. struct TreeNode* parent로 정의되어 있습니다.
- 왼쪽 자식 노드 포인터: 왼쪽 자식 노드를 가리키는 포인터입니다. struct TreeNode* left로 정의되어 있습니다.
- 오른쪽 자식 노드 포인터: 오른쪽 자식 노드를 가리키는 포인터입니다. struct TreeNode* right로 정의되어 있습니다.
트리 구조체의 정의는 다음과 같습니다:
typedef struct TreeNode {
element data; // 노드의 데이터
struct TreeNode* parent; // 부모 노드를 가리키는 포인터
struct TreeNode* left; // 왼쪽 자식 노드를 가리키는 포인터
struct TreeNode* right; // 오른쪽 자식 노드를 가리키는 포인터
} TreeNode;스택 함수: Push와 Pop
스택의 두 가지 주요 연산인 Push와 Pop에 대해 설명하겠습니다. 이 연산들은 스택의 기본적인 동작을 정의하며, LIFO(Last In First Out) 구조를 유지하는 데 핵심적인 역할을 합니다.
Push 함수
Push 함수는 스택에 새로운 요소를 추가하는 연산입니다. 이 함수는 스택이 가득 차 있는지 확인한 후, 요소를 스택의 맨 위에 추가합니다. Push 함수의 단계는 다음과 같습니다:
- 포화 상태 확인: 스택이 가득 찬 경우, 새로운 요소를 추가할 수 없으므로 이를 확인합니다.
- 데이터 삽입: 스택이 가득 차지 않은 경우, top 인덱스를 증가시키고 해당 위치에 새로운 요소를 삽입합니다.
다음은 Push 함수의 코드와 설명입니다:
void Push(StackType *s, TreeNode* ipt) {
if (IsFull(s)) {
printf("스택 포화 발생\n");
return;
} else {
s->data[++(s->top)] = ipt;
}
}- IsFull(s): 스택이 가득 찼는지 확인하는 함수입니다. IsFull 함수는 s->top이 스택의 최대 용량 N-1과 같은지 확인하여 스택의 포화 상태를 판단합니다.
- s->data[++(s->top)] = ipt: 스택의 top 인덱스를 먼저 증가시키고, 해당 위치에 새로운 요소 ipt를 삽입합니다.
Pop 함수
Pop 함수는 스택에서 요소를 제거하고 반환하는 연산입니다. 이 함수는 스택이 비어 있는지 확인한 후, 스택의 맨 위 요소를 제거하고 반환합니다. Pop 함수의 단계는 다음과 같습니다:
- 공백 상태 확인: 스택이 비어 있는 경우, 요소를 제거할 수 없으므로 이를 확인합니다.
- 데이터 제거 및 반환: 스택이 비어 있지 않은 경우, top 인덱스에 있는 요소를 반환하고 top 인덱스를 감소시킵니다.
다음은 Pop 함수의 코드와 설명입니다:
TreeNode* Pop(StackType *s) {
if (IsEmpty(s)) {
printf("스택 공백 발생: 프로그램을 종료합니다.");
exit(1);
} else {
return s->data[(s->top)--];
}
}- sEmpty(s): 스택이 비어 있는지 확인하는 함수입니다. IsEmpty 함수는 s->top이 -1과 같은지 확인하여 스택의 공백 상태를 판단합니다.
- s->data[(s->top)--]: 스택의 top 인덱스에 있는 요소를 반환하고, top 인덱스를 감소시킵니다.
스택과 트리의 관계
스택과 트리는 서로 다른 자료구조지만, 트리를 순회하거나 탐색하는 데 스택을 사용할 수 있습니다. 스택을 사용하면 트리의 노드를 비재귀적으로 방문할 수 있습니다.
이는 특히 깊이 우선 탐색(DFS, Depth-First Search)과 같은 알고리즘을 구현할 때 유용합니다.
트리를 순회할 때 스택을 사용하는 방법은 다음과 같습니다:
전위 순회 (Pre-order Traversal) : 부모 노드 → 자식 노드
1. 초기화:
- 스택 S를 초기화합니다.
- 루트 노드가 NULL이 아닌 경우, 루트 노드를 스택에 푸시합니다.
2. 반복문 (스택이 비어 있지 않은 동안):
- 스택에서 노드를 팝하여 현재 노드로 설정합니다.
- 현재 노드의 데이터를 출력합니다.
- 현재 노드의 오른쪽 자식이 NULL이 아닌 경우, 오른쪽 자식을 스택에 푸시합니다.
- 현재 노드의 왼쪽 자식이 NULL이 아닌 경우, 왼쪽 자식을 스택에 푸시합니다.
중위 순회 (In-order Traversal): 왼쪽 노드 → 부모 노드 → 오른쪽 노드
1. 초기화: 스택 S를 초기화하고, 현재 노드를 루트로 설정합니다.
2. 왼쪽 자식 처리: 현재 노드가 NULL이 아닐 때까지 현재 노드를 스택에 푸시하고, 왼쪽 자식으로 이동합니다.
3. 노드 방문 및 오른쪽 자식 처리:
- 스택이 비어 있는지 확인하고, 비어 있으면 순회를 종료합니다.
- 스택에서 노드를 팝하여 현재 노드로 설정하고, 노드의 데이터를 출력합니다.
- 현재 노드를 오른쪽 자식으로 이동합니다.
4. 반복: 위의 과정을 반복합니다
후위 순회 (Post-order Traversal): 자식 노드 → 부모 노드 순으로 방문
1. 초기화:
- 두 개의 스택 S1과 S2를 초기화합니다.
- 루트 노드가 NULL이 아닌 경우, 루트 노드를 S1에 푸시합니다.
2. 첫 번째 반복문 (S1이 비어 있지 않을 때까지):
- S1에서 노드를 팝하여 현재 노드로 설정합니다.
- 현재 노드를 S2에 푸시합니다.
- 현재 노드의 왼쪽 자식이 NULL이 아닌 경우, S1에 푸시합니다.
- 현재 노드의 오른쪽 자식이 NULL이 아닌 경우, S1에 푸시합니다.
3. 두 번째 반복문 (S2가 비어 있지 않을 때까지): S2에서 노드를 팝하여 데이터를 출력합니다.
이진 트리와 스택을 활용한 순회 알고리즘
아래 코드는 스택을 이용한 이진 트리의 전위, 중위, 후위 순회 알고리즘을 구현한 것입니다.
각 함수는 스택을 이용해 순회를 비재귀적으로 수행합니다.
전위 순회 (Pre-order Traversal)
전위 순회는 현재 노드를 방문하고, 왼쪽 자식을 순회한 후, 오른쪽 자식을 순회합니다. 이를 스택을 이용해 구현한 함수는 다음과 같습니다.
void IterativePreOrder(TreeNode* root) {
StackType S;
Initialize(&S);
if (root != NULL) Push(&S, root);
while (!IsEmpty(&S)) {
TreeNode* current = Pop(&S);
printf("%c ", current->data);
// 오른쪽 자식을 먼저 푸시(스택의 LIFO 특성으로 인해 나중에 처리됨)
if (current->right != NULL) Push(&S, current->right);
// 왼쪽 자식을 나중에 푸시(스택의 LIFO 특성으로 인해 먼저 처리됨)
if (current->left != NULL) Push(&S, current->left);
}
}1. 스택을 초기화합니다.
2. 루트 노드를 스택에 푸시합니다.
3. 스택이 비어 있지 않은 동안 반복합니다:
⸰ 스택에서 노드를 팝하여 현재 노드로 설정하고, 데이터를 처리합니다.
⸰ 현재 노드의 오른쪽 자식이 있으면 이를 스택에 푸시합니다.
⸰ 현재 노드의 왼쪽 자식이 있으면 이를 스택에 푸시합니다.
⸰ 이 방법은 스택의 LIFO(Last In First Out) 특성을 이용해 왼쪽 자식을 먼저 처리하게 됩니다.
전위 순회의 과정은 아래 [더보기] 란을 참고한다.
전위 순회의 예시 설명전위 순회는 "현재 노드 -> 왼쪽 자식 -> 오른쪽 자식"의 순서로 트리를 방문하는 방법입니다. 스택을 사용한 전위 순회 과정을 예제로 설명하겠습니다.예제 트리 구조다음과 같은 이진 트리를 예로 들겠습니다.A / \ B C / \ / \ D E F G 전위 순회 과정
|
중위 순회 (In-order Traversal)
중위 순회는 왼쪽 자식을 순회한 후, 현재 노드를 방문하고, 오른쪽 자식을 순회합니다. 이를 스택을 이용해 구현한 함수는 다음과 같습니다.
void IterativeInOrder(TreeNode* root) {
StackType S;
Initialize(&S);
TreeNode* current = root;
while (1) {
// 현재 노드의 왼쪽으로 끝까지 내려가며 스택에 푸시
for (; current != NULL; current = current->left) {
Push(&S, current);
}
// 스택이 비어 있으면 순회 완료
if (IsEmpty(&S)) {break;}
// 스택에서 노드를 팝하고 출력
current = Pop(&S);
printf("%c ", current->data);
// 현재 노드를 오른쪽 자식으로 이동
current = current->right;
}
}
중위 순회는 "왼쪽 자식 -> 현재 노드 -> 오른쪽 자식"의 순서로 방문합니다. 스택을 이용해 중위 순회를 구현하는 방법은 다음과 같습니다:
1. 스택을 초기화합니다.
2. 현재 노드를 루트로 설정합니다.
3. 현재 노드가 NULL이 아니거나 스택이 비어 있지 않은 동안 반복합니다:
⸰ 현재 노드가 NULL이 아닐 때까지 현재 노드를 스택에 푸시하고 왼쪽 자식으로 이동합니다.
⸰ 현재 노드를 스택에서 팝하여 현재 노드로 설정하고, 데이터를 처리합니다.
⸰ 현재 노드를 오른쪽 자식으로 이동합니다.
⸰ 이 방법은 스택을 이용해 왼쪽 자식을 모두 방문한 후, 현재 노드와 오른쪽 자식을 방문합니다.
중위 순회의 과정은 아래 [더보기] 란을 참고한다.
중위 순회의 예시 설명중위 순회는 "왼쪽 자식 -> 현재 노드 -> 오른쪽 자식"의 순서로 트리를 방문하는 방법입니다. 스택을 사용한 중위 순회 과정을 예제로 설명하겠습니다.예제 트리 구조다음과 같은 이진 트리를 예로 들겠습니다.A / \ B C / \ / \ D E F G 중위 순회 과정초기화
첫 번째 반복 (왼쪽 자식 처리)
두 번째 반복 (노드 방문 및 오른쪽 자식 처리)
세 번째 반복 (노드 방문 및 오른쪽 자식 처리)
네 번째 반복 (왼쪽 자식 처리)
다섯 번째 반복 (노드 방문 및 오른쪽 자식 처리)
여섯 번째 반복 (노드 방문 및 오른쪽 자식 처리)
일곱 번째 반복 (왼쪽 자식 처리)
여덟 번째 반복 (노드 방문 및 오른쪽 자식 처리)
아홉 번째 반복 (노드 방문 및 오른쪽 자식 처리)
열 번째 반복 (왼쪽 자식 처리)
열한 번째 반복 (노드 방문 및 오른쪽 자식 처리)
종료
|
후위 순회 (Post-order Traversal)
후위 순회는 왼쪽 자식을 순회하고, 오른쪽 자식을 순회한 후, 현재 노드를 방문합니다. 이를 스택을 이용해 구현한 함수는 다음과 같습니다.
void IterativePostOrder(TreeNode* root) {
StackType S1, S2;
Initialize(&S1);
Initialize(&S2);
if (root != NULL) Push(&S1, root);
while (!IsEmpty(&S1)) {
TreeNode* current = Pop(&S1);
Push(&S2, current);
// 왼쪽 자식을 스택1에 푸시
if (current->left != NULL) Push(&S1, current->left);
// 오른쪽 자식을 스택1에 푸시
if (current->right != NULL) Push(&S1, current->right);
}
while (!IsEmpty(&S2)) {
TreeNode* current = Pop(&S2);
printf("%c ", current->data);
}
}후위 순회는 "왼쪽 자식 -> 오른쪽 자식 -> 현재 노드"의 순서로 방문합니다. 스택을 이용해 후위 순회를 구현하는 방법은 다음과 같습니다:
1. 두 개의 스택을 초기화합니다 (S1과 S2).
2. 루트 노드를 스택 S1에 푸시합니다.
3. 스택 S1이 비어 있지 않은 동안 반복합니다:
⸰ 스택 S1에서 노드를 팝하여 스택 S2에 푸시합니다.
⸰ 현재 노드의 왼쪽 자식이 있으면 이를 스택 S1에 푸시합니다.
⸰ 현재 노드의 오른쪽 자식이 있으면 이를 스택 S1에 푸시합니다.
4.스택 S2가 비어 있지 않은 동안 반복합니다:
⸰ 스택 S2에서 노드를 팝하여 데이터를 처리합니다.
이 방법은 두 개의 스택을 이용해 후위 순회를 구현합니다. 스택 S2에 푸시된 순서대로 노드를 처리하여 후위 순회 순서를 보장합니다.
두 개의 스택을 사용하는 이유
후위 순회(Post-order Traversal)에서는 노드를 방문하는 순서가 "왼쪽 자식 -> 오른쪽 자식 -> 현재 노드"입니다. 이 순서를 유지하면서 스택을 사용해 비재귀적으로 후위 순회를 구현하려면, 두 개의 스택을 사용하는 방법이 효율적입니다. 두 개의 스택을 사용하는 이유와 그 과정을 설명하겠습니다.
- 후위 순회의 특성: 후위 순회에서는 현재 노드를 방문하기 전에 반드시 왼쪽 자식과 오른쪽 자식을 먼저 방문해야 합니다. 따라서 현재 노드를 마지막에 방문해야 하는데, 이를 한 개의 스택으로 구현하는 것은 복잡합니다.
- 노드 방문 순서 유지: 두 개의 스택을 사용하면 현재 노드를 두 번째 스택에 푸시하여 마지막에 방문하도록 할 수 있습니다. 첫 번째 스택은 노드를 저장하고, 두 번째 스택은 노드를 최종 방문 순서대로 저장합니다.
첫 번째 스택은 노드를 저장하고, 두 번째 스택은 노드를 최종 방문 순서대로 저장합니다.
두 개의 스택을 사용한 후위 순회 과정은 아래와 같습니다.
- 첫 번째 스택(S1): 현재 노드를 저장하는 데 사용됩니다. 노드를 팝할 때마다 왼쪽 자식과 오른쪽 자식을 푸시합니다.
- 두 번째 스택(S2): 방문 순서대로 노드를 저장하는 데 사용됩니다. 첫 번째 스택에서 팝한 노드를 푸시하여 최종 방문 순서를 유지합니다.
후위 순회의 과정은 아래 [더보기] 란을 참고한다.
후위 순회의 예시 설명후위 순회는 "왼쪽 자식 -> 오른쪽 자식 -> 현재 노드"의 순서로 트리를 방문하는 방법입니다.스택을 사용한 후위 순회 과정을 예제로 설명하겠습니다. 예제 트리 구조다음과 같은 이진 트리를 예로 들겠습니다.A / \ B C / \ / \ D E F G 후위 순회 과정
예제 순회 과정
|
전체 코드
#include <stdio.h>
#include <stdlib.h>
typedef char element;
#define N 100
// 노드 구조체 정의
typedef struct TreeNode {
element data; // 노드의 데이터
struct TreeNode* parent; // 부모 노드를 가리키는 포인터
struct TreeNode* left; // 왼쪽 자식 노드를 가리키는 포인터
struct TreeNode* right; // 오른쪽 자식 노드를 가리키는 포인터
} TreeNode;
// ===== 스택 코드의 시작 =====
typedef struct {
TreeNode* data[N]; // 스택의 배열: 최대 용량은 100
int top; // (현재 스택의 데이터 개수 - 1)
} StackType;
// 스택 초기화 함수
void Initialize(StackType *s) { s->top = -1; }
// 공백 상태 검출 함수
int IsEmpty(StackType *s) { return (s->top == -1); }
// 포화 상태 검출 함수
int IsFull(StackType *s) { return (s->top >= (N - 1)); }
// 삽입 함수
void Push(StackType *s, TreeNode* ipt) {
if (IsFull(s)) {
printf("스택 포화 발생\n");
return;
} else {
s->data[++(s->top)] = ipt;
}
}
// 삭제 함수
TreeNode* Pop(StackType *s) {
if (IsEmpty(s)) {
printf("스택 공백 발생: 프로그램을 종료합니다.");
exit(1);
} else {
return s->data[(s->top)--];
}
}
// 피크 함수
TreeNode* Peek(StackType *s) {
if (IsEmpty(s)) {
printf("스택 공백 발생: 프로그램을 종료합니다.");
exit(1);
} else {
return s->data[s->top];
}
}
// 노드 생성 함수
TreeNode* makeNode(element data, TreeNode *parent, TreeNode *left, TreeNode *right) {
TreeNode *node = (TreeNode*)malloc(sizeof(TreeNode));
if (node == NULL) {
fprintf(stderr, "메모리 할당 실패\n");
exit(1);
}
node->data = data;
node->parent = parent;
node->left = left;
node->right = right;
return node;
}
// 스택을 사용한 전위 순회 함수
void IterativePreOrder(TreeNode* root) {
StackType S;
Initialize(&S);
if (root != NULL) Push(&S, root);
while (!IsEmpty(&S)) {
TreeNode* current = Pop(&S);
printf("%c ", current->data);
// 오른쪽 자식을 먼저 푸시(스택의 LIFO 특성으로 인해 나중에 처리됨)
if (current->right != NULL) Push(&S, current->right);
// 왼쪽 자식을 나중에 푸시(스택의 LIFO 특성으로 인해 먼저 처리됨)
if (current->left != NULL) Push(&S, current->left);
}
}
// 스택을 사용한 중위 순회 함수
// 스택을 사용한 중위 순회 함수
void IterativeInOrder(TreeNode* root) {
StackType S;
Initialize(&S);
TreeNode* current = root;
while (1) {
// 현재 노드의 왼쪽으로 끝까지 내려가며 스택에 푸시
for (; current != NULL; current = current->left) {
Push(&S, current);
}
// 스택이 비어 있으면 순회 완료
if (IsEmpty(&S)) {break;}
// 스택에서 노드를 팝하고 출력
current = Pop(&S);
printf("%c ", current->data);
// 현재 노드를 오른쪽 자식으로 이동
current = current->right;
}
}
// 스택을 사용한 후위 순회 함수
void IterativePostOrder(TreeNode* root) {
StackType S1, S2;
Initialize(&S1);
Initialize(&S2);
if (root != NULL) Push(&S1, root);
while (!IsEmpty(&S1)) {
TreeNode* current = Pop(&S1);
Push(&S2, current);
// 왼쪽 자식을 스택1에 푸시
if (current->left != NULL) Push(&S1, current->left);
// 오른쪽 자식을 스택1에 푸시
if (current->right != NULL) Push(&S1, current->right);
}
while (!IsEmpty(&S2)) {
TreeNode* current = Pop(&S2);
printf("%c ", current->data);
}
}
int main() {
TreeNode *n11 = makeNode('I', NULL, NULL, NULL);
TreeNode *n10 = makeNode('H', NULL, NULL, NULL);
TreeNode *n7 = makeNode('G', NULL, NULL, NULL);
TreeNode *n6 = makeNode('F', NULL, NULL, NULL);
TreeNode *n5 = makeNode('E', NULL, n10, n11);
TreeNode *n4 = makeNode('D', NULL, NULL, NULL);
TreeNode *n3 = makeNode('C', NULL, n6, n7);
TreeNode *n2 = makeNode('B', NULL, n4, n5);
TreeNode *n1 = makeNode('A', NULL, n2, n3);
n10->parent = n11->parent = n5;
n6->parent = n7->parent = n3;
n4->parent = n5->parent = n2;
n2->parent = n3->parent = n1;
// printf("Pre (Recursive): "); preOrder(n1); printf("\n");
// printf("In (Recursive): "); inOrder(n1); printf("\n");
// printf("Post (Recursive): "); postOrder(n1); printf("\n");
printf("Pre (Iterative): "); IterativePreOrder(n1); printf("\n");
printf("In (Iterative): "); IterativeInOrder(n1); printf("\n");
printf("Post (Iterative): "); IterativePostOrder(n1); printf("\n");
return 0;
}'Datastructure > [8] 트리' 카테고리의 다른 글
| [8] 트리 ⑦ 응용 (2) : 폴더 용량 출력 프로그램 (0) | 2024.06.06 |
|---|---|
| [8] 트리 ⑥ 응용 (1) : 연결리스트를 이용한 트리 구현 (1) | 2024.06.05 |
| [8] 트리 ④ 레벨 순회 : 원형 큐 이용 (0) | 2024.06.03 |
| [8] 트리 ③ 원형 큐 (0) | 2024.06.03 |
| [8] 트리 ② 트리의 구현 : ADT (0) | 2024.05.30 |
