2020. 8. 7. 00:36ㆍ인생 난제 알고리즘/알고리즘 기본
이진 트리의 정의
트리의 일종으로, 각 노드가 최대 2개의 하위 노드로 구성되어 있는 트리를 말한다. 하위 트리는 왼쪽과 오른쪽으로 구분된다.
이진 트리는 모양에 따라서 포화 이진 트리, 완전 이진 트리, 편향 이진 트리로 나눠진다. 포화 이진 트리는 아래와 같이 모든 노드가 2개의 하위 노드를 가진 경우이다.
완전 이진 트리는 트리의 높이가 k 일 때, 높이 k - 1 까지는 모든 노드가 있어야 하고, 높이 k에 존재하는 노드들은 왼쪽에서 오른쪽으로 순서대로 존재해야 한다. 아래와 같이 번호가 부여되면, k번 노드의 부모는 k / 2, 왼쪽 / 오른쪽 자식은 2k / 2k + 1로 노드의 번호를 알 수 있다. 이러한 특성 때문에 1차원 배열에 저장하기 쉽다.
편향 이진 트리는 한쪽 방향으로만 노드가 구성된 경우를 말한다.
이진 트리 순회
이진 트리의 모든 노드를 방문하기 위한 방법으로는 DFS를 이용하는 방법과 BFS를 이용하는 방법이 있다. DFS를 이용하는 경우, 재귀 함수를 사용하며 값을 출력하는 위치에 따라 전위 순회, 중위 순회, 후위 순회로 구분된다. 각 예제 코드는 아래와 같다.
1) 전위 순회
이진 트리의 노드는 왼쪽과 오른쪽으로 방향이 구분되어 있으며, 방향성은 왼쪽에서 오른쪽이 기본이다. 전위 순회는 루트 노드를 시작으로 하위 노드의 왼쪽을 끝까지 파고 내려가면서 방문한다. 더이상 왼쪽으로 내려갈 수 없는 경우, 이전 노드로 되돌아와 오른쪽을 방문한다.
전위 순회 코드는 아래와 같다.
void preShowNode (Node * node) {
if (node == NULL) {
return;
}
printf("%c ", node->nodeName);
preShowNode(node->left);
preShowNode(node->right);
}
2) 중위 순회
트리의 좌측 아래부터 순회를 시작하며 루트까지 거슬러 올라가는 순회 방식이다. 왼쪽 노드 방문이 끝난 후 루트 노드를 방문하면 오른쪽에 있는 노드들 중 가장 왼쪽 아래의 노드부터 다시 거슬러 올라오는 방식이다.
중위 순회 코드는 아래와 같다.
void midShowNode (Node * node) {
if (node == NULL) {
return;
}
midShowNode(node->left);
printf("%c ", node->nodeName);
midShowNode(node->right);
}
3) 후위 순회
중위 순회와 다른 점은 하위 노드들을 먼저 방문한 후 상위 노드를 방문한다는 것이다. 마지막으로 루트 노드를 방문하는 특성이 있기 때문에 메모리를 소거해야 하는 경우에도 사용한다.
후위 순회 코드는 아래와 같다.
void endShowNode (Node * node) {
if (node == NULL) {
return;
}
endShowNode(node->left);
endShowNode(node->right);
printf("%c ", node->nodeName);
}
4) 레벨 순회
위 3가지 순회가 DFS 방식이라면, 레벨 순회는 BFS를 이용하여 방문하는 방법이다. 루트 노드에 하위 노드를 추가할 때마다 큐에 추가한 노드를 저장하고, 조회 시 큐에서 순서대로 빼서 방문하는 방법이다.
아래의 이진트리 예제 코드에서 레벨 순회가 어떻게 구현 되었는지 확인해보자.
이진 트리 예제
아래의 코드는 C언어로 구현한 이진 트리 예제이다. 노드 추가 시 큐를 이용하여 레벨 순회 방식과 동일하게 노드를 추가하였으며, 하단에는 전위, 중위, 후위 순회를 실행한다.
#include <stdio.h>
#include <stdlib.h>
#define MAX 10
typedef struct _Node {
struct Node * left;
struct Node * right;
char nodeName;
} Node;
Node * root;
Node * next;
int front = -1, rear = -1;
Node * queue[MAX * MAX];
void initQueue () {
front = -1;
rear = -1;
for (int i = 0; i < MAX * MAX; i++) {
queue[i] = NULL;
}
}
// 새로 추가할 노드의 부모 노드를 저장하는 인-큐 함수
void enqueue (Node * next) {
rear++;
queue[rear] = next;
}
// 새로 추가할 노드의 부모 노드를 불러오기 위한 디-큐 함수
Node* dequeue () {
front++;
return queue[front];
}
void initRoot () {
root = (Node*)malloc(sizeof(Node));
root->left = NULL;
root->right = NULL;
root->nodeName = 'A';
initQueue();
next = root;
}
void insertNode (char nodeName) {
Node * newNode = (Node*)malloc(sizeof(Node));
newNode->left = NULL;
newNode->right = NULL;
newNode->nodeName = nodeName;
// 이진 트리에 새롭게 노드를 추가할 때, 방향별로 부모 노드의 포인터를 큐에 저장한다.
if (next->left == NULL) {
next->left = newNode;
enqueue(next->left);
} else if (next->right == NULL) {
next->right = newNode;
enqueue(next->right);
}
// 만약, 현재 부모 노드가 2개의 자식을 가진 경우, 큐에 저장된 다음 노드 포인터를 불러온다.
// 이 코드는 레벨 순회와 완벽하게 동일한 코드이며, 이진트리의 방향성을 주기 위해 순회 대신 삽입으로 사용한 것이다.
if (next->left != NULL && next->right != NULL) {
next = dequeue();
}
}
// 전위 순회 (DFS)
void preShowNode (Node * node) {
if (node == NULL) {
return;
}
printf("%c ", node->nodeName);
preShowNode(node->left);
preShowNode(node->right);
}
// 중위 순회 (DFS)
void midShowNode (Node * node) {
if (node == NULL) {
return;
}
midShowNode(node->left);
printf("%c ", node->nodeName);
midShowNode(node->right);
}
// 후위 순회 (DFS) > 메모리를 제거하고자 할 경우, 후위 순회를 사용해야만 루트 노드가 마지막에 소거된다.
void endShowNode (Node * node) {
if (node == NULL) {
return;
}
endShowNode(node->left);
endShowNode(node->right);
printf("%c ", node->nodeName);
}
int main(int argc, const char * argv[]) {
initRoot();
insertNode('B');
insertNode('C');
insertNode('D');
insertNode('E');
insertNode('F');
insertNode('G');
printf("전위 순회\n\n");
preShowNode(root);
printf("\n\n");
printf("중위 순회\n\n");
midShowNode(root);
printf("\n\n");
printf("후위 순회\n\n");
endShowNode(root);
printf("\n\n");
return 0;
}
결과는 아래와 같다.
