Special Effects FX 스스로를 감동시켜야 최선을 다 한 것이다.

순회의 세 가지 방법

이진 트리를 대상으로 하는 대표적인 순회의 세 가지 방법은 다음과 같다.

# 전위 순회(Preorder Traversal) : 루트 노드를 먼저 방문.

# 중위 순회(Inorder Traversal) : 루트 노드를 중간에 방문.

# 후위 순회(Postorder Traversal) : 루트 노드를 마지막에 방문.

이렇듯 이진 트리를 순회하는 대표적인 방법은 다음 내용을 기준으로 세 가지로 나뉜다.

즉, Root Node 를 언제 방문하느냐에 따라 달라진다.

Left -> Root -> Right

루트 노드는 중간에 방문이 이뤄지기 때문에 이러한 방식의 순회를 가리켜 '중위 순회' 라 한다.

Left -> Right -> Root

루트 노드는 마지막에 방문을 하게 되므로, 이러한 방식의 순회를 가리켜 '후위 순회' 라 한다.

Root -> Left -> Right

루트 노드는 첫 번째로 방문을 하게 되므로, 이러한 방식의 순회를 가리켜 '전위 순회' 라 한다.

루트 노드와 이를 부모로 하는 두 자식 노드를 놓고, 한쪽 방향으로 순서대로 방문을 하면 된다.

※ 이진 트리는 그 구조가 재귀적이다.

트리의 개요

트리는 계층적 관계(Hierarchical Realationship) 를 표현하는 자료구조이다.

트리는 가지를 늘려가며 뻗어나가는 자료구조이다.

※ 자료구조는 무엇인가를 '표현'하는 도구이다. 표현을 위해서 저장과 삭제라는 기능이 제공되는 것으로 이해하는 것이 옳다.

트리가 표현할 수 있는 것들

컴퓨터의 디렉토리 구조, 집안의 족보나 기업 및 정부의 조직도 등등

트리 관련 용어

노드:  node

- 트리의 구성요소에 해당하는 요소

간선: edge

- 노드와 노드를 연결하는 연결선

루트 노드: root node

- 트리 구조에서 최상위에 존재하는 노드

단말 노드: terminal node

- 아래로 또 다른 노드가 연결되어 있지 않은 노드

내부 노드: internal node

- 단말 노드를 제외한 모든 노드

참고로 '단말 노드'는 나무의 구조상 잎에 해당한다 하여 '잎사귀 노드(leaf node)' 라고도 불리며, '내부 노드'는 단말 노드가 아니라 하여 '비단말 노드(non-internal node)' 라 불린다.

그리고 노드간에는 부모(parent), 자식(child), 형제(sibling)의 관계가 성립이 된다. 

# 노드 A는 노드 B, C, D의 부모 노드이다.

# 노드 B, C, D는 노드 A의 자식 노드이다.

# 노드 B, C, D는 부모 노드가 같으므로, 서로가 서로에게 형제 노드이다.

그런데 부모와 자식의 관계는 상대적이다. 따라서 노드 B는 노드 A의 자식 노드이지만, 동시에 노드 E와 F의 부모 노드도 된다.

조금 더 나아가서 조상(Ancestor), 후손(Descendant)의 관계도 있다. 특정 노드의 위의 위치한 모든 노드를 가리켜 '조상 노드' 라 하고, 특정 노드의 아래에 위치한 모든 노드를 가리켜 '후손 노드' 라 한다. 

즉 노드 A와 B는 노드 E의 조상 노드이다. 반면 노드 B, C, D, E, F는 모두 노드 A의 후손 노드이다.

이진 트리(Binary Tree)와 서브 트리(Sub Tree)

서브 트리: 큰 트리에 속하는 작은 트리를 가리켜 '서브 트리(sub tree)' 라 한다.

이진 트리: 이진 트리는 다음 두 조건을 만족해야 한다.

1) 루트 노드를 중심으로 두 개의 서브 트리로 나뉘어진다.

2) 나위어진 두 서브 트리도 모두 이진 트리이어야 한다.

※ 이진 트리의 조건 자체가 재귀적이다.

이진트리가 되려면, 루트 노드를 중심으로 둘로 나뉘는 두 개의 서브 트리도 이진 트리이어야 하고, 그 서브 트리의 모든 서브 트리도 이진 트리이어야 한다.

공집합(empty set)

노드가 위치할 수 있는 곳에 노드가 존재하지 않는다면, 공집합(empty set) 노드가 존재하는 것으로 간주한다. 물론 공집합 노드도 이진 트리의 판단에 있어서 노드로 인정한다.

포화 이진 트리(Full Binary Tree)와 완전 이진 트리(Complete Binary Tree)

레벨(level): 트리에서는 각 층별로 숫자를 매겨서 리르 트리의 '레벨'이라 한다.

높이(height): 트리의 최고 레벨을 가리켜 '높이'라 한다.

포화 이진 트리: 모든 레벨이 꽉 찬 이진 트리를 가리켜 '포화 이진 트리'라 한다.

완전 이진 트리: 포화 이진 트리처럼 모든 레벨이 꽉 찬 상태는 아니지만, 차곡차곡 빈 큼 없이 노드가 채워진 이진 트리를 뜻한다. 

즉, 노드가 위에서 아래로, 그리고 외쪽에서 오른쪽으로 순서대로 채워진 트리를 말한다.

덱을 기반으로 큐를 쓸 수 있다면, 덱을 기반으로 스택도 쓸 수 있단 소리다.

덱의 이해

- 덱은 앞으로도 뒤도로 넣을 수 있고, 앞으로도 뒤도로 뺄 수 있는 자료구조이다.

deque은 double-ended queue를 줄여서 표현한 것으로, 양방향으로 넣고 뺄 수 있는다는 사실에 초점이 맞춰져서 지어진 이름이다.

덱은 양방향으로 넣고, 양방향으로 뺄 수 있는 자료구조이기에 스택과 큐의 특성을 모두 갖는, 혹은 스택과 큐를 조합한 형태의 자료구조로 이해되고 있다.

덱 자료구조의 ADT

void DequeInit(Deque * pdeq);

- 덱의 초기화 진행

int DQIsEmpty(Deque * pdeq);

- 덱이 빈 경우 true, 아니면 false

void DQAddFirst(Deque * pdeq, Data data);

- 덱의 머리에 데이터를 저장

void DQAddLast(Deque * pdeq, Data data);

- 덱의 꼬리에 데이터를 저장

Data DQRemoveFirst(Deque * pdeq);

- 덱의 머리에 위치한 데이터를 반환, 소멸

Data DQRemoveLast(Deque * pdeq);

- 덱의 꼬리에 위치한 데이터를 반환, 소멸

Data DQGetFirst(Deque * pdeq);

- 덱의 머리에 위치한 데이터를 소멸하지 않고 반환

Data DQGetLast(Deque * pdeq);

- 덱의 꼬리에 위치한 데이터를 소멸하지 않고 반환

※ 참고로 Deque는 '디큐'로 읽기 쉽다. 그럼에도 불구하고 '덱'으로 발음하는 이유는 '디큐'로 발음할 경우 큐의 dequeue 연산과 그 발음이 같아져서 이 둘을 구분하기 어렵기 때문이다. 이것이 크게 중요한 것은 아니지만, 혼란을 줄 수 있으므로 가급적 '덱'으로 읽으면 좋다.

덱의 구현

덱도 큐와 마찬가지로 배열을 기반으로, 그리고 열결 리스트를 기반으로도 구현이 가능하다. 

하지만 덱의 구현에 가장 어울린다고 알려진 '양방향 연결 리스트'를 기반으로 덱을 구현하는 것이 좋은 선택일 수 있다.

양방향 연결 리스트가 단방향 연결 리스트보다 덱의 구현에 더 잘 어울리는 이유는 다음 함수의 구현과 관련이 있다. 

Data DQRemoveLast(Deque * pdeq);    // 꼬리에 위치한 데이터 삭제

위의 함수는 꼬리에 위치한 노드를 삭제하는 함수인데 노드가 양방향으로 연결되어 있지 않으면, 꼬리에 위치한 노드의 삭제는 간단하지 않다. 때문에 덱의 구현에 있어서 양방향 연결 리스트는 매우 좋은 선택이라 할 수 있다.

Header file

Source file

Main file

실행 결과

원형 큐를 연결 리스트를 기반으로 구현하는 경우에는 의외로 신경 쓸 부분이 적다.

스택과의 차이점

- 스택은 push와 pop이 이뤄지는 위치가 같은 반면, 큐는 enqueue와 dequeue가 이뤄지는 위치가 다르다.

Header File

Source File

Main File

실행 결과

큐의 활용

큐는 운영체제 및 네트워크와 관련된 소프트웨어의 구현에 있어서 중요한 역할을 담당하는 자료구조이다. 

그리고 '큐잉 이론(Queuing Theory)' 이라는 학문에서는 수학적으로 모델링 된 결과의 확인을 위해서 특정 현상을 '시뮬레이션(simulation)' 하게 되는데, 이때에도 큐는 중요한 역할을 담당한다. 

F(Front), R(Rear)

F는 큐의 머리를, R은 큐의 꼬리를 가리키는 일종의 변수를 의미.

R이 배열의 끝에 도달하면, 다시 맨 앞으로 이동시켜서 R이 회전하게 만든다. 물론 R을 뒤쫗아 가는 F도 배열의 끝에 도달하면 회전해야 한다. 그리고 이러한 방식으로 동작하는 배열 기반의 큐를 가리켜 '원형 큐(Circular Queue)' 라 한다. 

논리적으로 배열이 원형의 형태를 갖춘다고 해서 붙여진 이름이다.

원형 큐의 문제점

원형 큐는 F와 R의 위치만 가지고는 꽉 찬 경우와 텅 빈 경우를 구분할 수가 없다.

원형 큐의 문제해결

배열을 꽉 채우지 않는다. 꽉 차면 구분이 안되니 꽉 채우지 않는다.

즉, 배열의 길이가 N이라면 데이터가 N-1개 채워졌을 때, 이를 꽉 찬 것으로 간주한다.

이렇게 하면 저장 공간 하나를 낭비하지만 이로 인해서 문제 하나가 해결이 되는 셈이니 잃는 것보다 얻는 것이 더 많다.

실제 큐의 구현을 위해서 인지하고 있어야 하는 2가지

1. enqueue 연산 시, R이 가리키는 위치를 한 칸 이동시킨 다음에, R이 가리키는 위치에 데이터를 저장한다.

2. dequeue 연산 시, F가 가리키는 위치를 한 칸 이동시킨 다음에, F가 가리키는 위치에 저장된 데이터를 반환 및 소멸한다.

이 중에서 특히 dequeue 연산 시에도 F가 가리키는 위치를 우선 한 칸 이동한다는 사실을 잊어선 안된다.

이로써 구현할 큐의 특성 두 가지를 다음과 같이 추가로 정리할 수 있다.

# 원형 큐가 텅 빈 상태        -        F와 R이 동일한 위치를 가리킨다.

# 원형 큐가 꽉 찬 상태        -        R이 가리키는 위치의 앞을 F가 가리킨다.

Header File

Source File

Main File

큐의 이해

큐는 스택과 함께 언급되고 또 비교되는 자료구조이다.  스택은 먼저 들어간 데이터가 나중에 나오는 구조인 반면, 큐는 먼저 들어간 데이터가 먼저 나오는 구조이다. 이것이 스택과 큐의 유일한 차이점이다.

큐의 자료구조를 실생활에서 예를 들자면 터널, 고무 호스, 양쪽으로 구멍 난 통, 줄을 서는 것 등등이 있다. 

이렇듯 큐는 '선입선출' 구조의 자료구조이다. 때문에 FIFO(First-In, First-Out) 구조의 자료구조이다.

큐의 ADT 정의

스택과 마찬가지로 큐의 ADT도 정형화된 편이다. 큐의 핵심 연산

enqueue        : 큐에 데이터를 넣는 연산

dequeue        : 큐에서 데이터를 꺼내는 연산

보편적인 큐 자료구조의 ADT

void QueueInit(Queue * pq);

- 큐의 초기화를 진행한다.

- 큐 생성 후 제일 먼저 호출되어야 하는 함수이다. 

int QIsEmpty(Queue * pq);

- 큐가 빈 경우 TRUE(1)를, 그렇지 않은 경우 FALSE(0)를 반환한다.

void Enqueue(Queue  * pq, Data data);

- 큐에 데이터를 저장한다. 매개변수 data로 전달된 값을 저장한다.

Data Dequeue(Queue * pq);

- 저장순서가 가장 앞선 데이터를 삭제한다.

- 삭제된 데이터는 반환된다.

- 본 함수의 호출을 위해서는 데이터가 하나 이상 존재함이 보장되어야 한다.

Data QPeek(Queue * pq);

- 저장순서가 가장 앞선 데이터를 반환하되 삭제하지 않는다.

- 본 함수의 호출을 위해서는 데이터가 하나 이상 존재함이 보장되어야 한다.

Stack 자료구조로 구현 된 계산기

InfixCalculator

InfixCalculator.c

InfixCalculator.h

InfixToPostfix.c

InfixToPostfix.h

ListBaseStack.c

ListBaseStack.h

main.c

PostCalculator.c

PostCalculator.h