Tree. 나무다. 🌲🌳🌴.
일단 이제까지 살펴본 자료 구조들은 모두 선형적인(Linear) 자료구조였다.
즉, 처음과 끝이 하나씩 있고 차례로 처음부터 끝까지 이동하다보면 모든 노드들을 거칠 수 있었다.
하지만! Tree(나무)는 비선형적인 구조(Non-Linear Structure)다.
Tree는 나무의 모양을 마치 거꾸로 뒤집어 높은 모양인데, 뿌리(Root)가 가장 위에 있고 가지(Link)들은 밑으로 벌어지면서 아래로 향하는 모양이고 잎(Leaf)이 달렸있다.
Tree 구조에서 사용하는 용어들
트리 구조에서 사용하는 용어들은 실생활에서 부터 따온 용어들이 많다.
실제 나무의 모양에서 따오기도 하고, 족보의 용어에서 따오기도 하고, 연결 리스트에서 따오기도 해서 하나를 가리키는 용어가 어려가지가 있어서 혼란스럽다 😱
따라서 위의 그림을 예시로 한번 정리해보자.
먼저 트리 구조는 어떤 조건을 만족하는 노드(node)와 링크(link)의 집합이다.
여기서 노드는 버텍스(Vertex)라고도 하고 링크는 엣지(Edge)라고도 한다.
노드는 어떤 정보(Information)를 담고있고 링크는 노드와 노드간의 연결을 나타낸다.
또 경로(path)라는거는 나무 내에서링크에 의해 연결된 일련의 노드 집합이다.
즉, 나무를 링크에 의해 연결된 노드를 통해 이동할때 이 이동 경로를 바로 경로(path)라고 한다.
나무의 제일 위에 있는 노드를 뿌리(root)노드 라고 부르고, 이 뿌리 노드로 부터 다른 노드에 이르는 경로(path)는 오직 하나밖에 존재하지 않는다.
(이 부분이 바로 나무 구조가 그래프 구조와 다른 부분이다.)
그리고 나무 구조의 링크에는 방향이랄게 없는데, 관례적으로 뿌리 노드를 위에 두고 그 아래 노드들은 밑에다 그린다.
또 경로는 보통 뿌리에서 점점 내려오면서 아래 노드로 향하는기 때문에 "위" 라고 하면 뿌리 쪽을 의미하고 "아래" 라고 하면 반대쪽을 의미한다.
다음으로 위 그림에서 B노드는 G노드 바로 위에 위치해있는데, 이와 같이 직접 연결되어 있으면서 아래쪽에 위치한 노드를 자식(Children)노드라고 하고, 위쪽에 위치한 노드를 부모(Parent)노드 라고 한다.
또 A노드는 G노드보다 2단계 위에 있기때문에 조부모(GrandParent)노드 라고 하고, E / F / G 노드처럼 같은 레벨에 있으면서 같은 부모 노드를 갖는 경우는 형제(Sibling)라고 한다.
E, F, G, H, J, D 노드 처럼 자식이 없는 노드를 잎(Leaf)노드 라고 하기도 하며, 종료 노드(Terminal Node)라고도 하고 외부 노드(External Node)라고도 한다.
반대로 A, B, C, I 노드처럼 자식이 하나라도 있는 노드를 비종료 노드(Non-Terminal Node)라고 히기도 하고, 내부 노드(Inernal Node)라고 하기도 한다.
용어가 드럽게 많네...
만약 나무가 어떤 정수 이하의 자손을 가져야 한다면 그 나무를 다중 나무(Multiway Tree)라고 하고, 가장 대표적인게 이진 나무(Binary Tree)로 이 나무는 자식을 2개 이하로 가져야 한다.
따라서 Binary Tree는 내부 노드들은 모두 2개나 1개의 자식을 가져야 하고 외부 노드들은 자식이 없다.
추가로 제일 마지막 레벨을 제외하고 각 레벨의 노드들이 꽉 차있는 이진 트리를 "완전한 이진 나무(Complete Binary Tree)" 라고 한며, 모든 레벨이 꽉 차 있는 이진 나무를 "꽉 차 있는 이진 나무(Full Binary Tree)"라고 한다.
Binary Tree 순회
일단 Tree 구조체 초기화에 대해서 먼저 설명을 해야할것 같다.
typedef struct _node {
int key;
struct _node *left;
struct _node *right;
} node;
node *head, *tail;
void init_tree(void) {
head = (node *)malloc(sizeof(node));
tail = (node *)malloc(sizeof(node));
head->left = tail;
head->right = tail;
tail->left = tail;
tail->right = tail;
}전체적인 모양새는 Double Linked List와 큰 차이는 없지만, 초기화 하는 부분에서 head, tail의 모든 링크를 tail을 가리키는걸 볼 수 있다.
이는 Double Linked List는 앞뒤로 자유롭게 이동하는 구조이지만, Tree는 위에서 아래로 내려오는 방법만 있기 때문이다.
또 Tree구조는 응용되는 알고리즘에 따라서 기본 동작이 다르게 정의된다.
따라서 Tree구조에 삽입, 삭제 등의 동작이 알고리즘 따라 모두 다 다른 방식이다.
그래서 당장은 삽입, 삭제와 같은 방법은 다루지 않고 앞으로 배워야할 힙정렬, 이진 검색 나무, 기수 검색 등등에서 확인해볼 생각이다.
여튼! Tree구조는 배열과 연결리스트와 같이 선형적인 구조가 아니기 때문에 모든 노드를 순회하는 방법이 쉽지않다.
일반적으로 아래와 같이 4가지의 나무타기(Tree Traverse)방법이 있는데, 이 4가지 방법들 모두 모든 노드를 중복없이 순회하는 방법을 제공해준다.
- 전위순회(Preorder Traverse): 뿌리를 먼저 타는 방법
- 중위순회(Inorder Traverse): 뿌리를 중간에 타는 방법
- 후위순회(Postorder Traverse): 뿌리를 나중에 타는 방법
- 층별순회(Level Order Traverse): 층별로 타는 방법
일단 위 4가지 방법을 구현하려면 재귀호출 이라는 방법을 사용해야 하는데, 이 부분도 다음에 더 자세히 알아보도록 하고 이번에는 간단히 구현만 해보자.
전위순회 Preorder Traverse
void preorder_traverse(node *t) {
if(t != tail) {
visit(t);
preorder_traverse(t->left);
preorder_traverse(t->right);
}
}일단 뿌리를 먼저 타는 방법은 아래와 같다.
- 뿌리를 먼저 방문한다.
- 왼쪽 작은 나무(Subtree)를 방문한다.
- 오른쪽 작은 나무를 방문한다.
일단 visit() 이라는 함수는 사용자가 정의하기 나름인데, Node가 갖고있는 값을 출력하는 함수여도 상관없고, 카운트를 하는 함수여도 상관 없다.
또 전위순회에서 뿌리를 방문하면 먼저 오른쪽 자식 노드와 다음으로 왼쪽 자식 노드를 차례대로 스택에 Push하고, 다음으로 방문할 노드는 스택에서 Pop한 노드가 된다.
즉! 스택에 차례대로 오른쪽 자식 -> 왼쪽 자식 순서로 저장되고, POP을 하면 왼쪽 자식 노드가 나오고 스택에 오른쪽 자식 노드가 남게 된다.
뿌리인 A를 먼저 방문하고 오른쪽 자식인 C와 왼쪽 자식인 B를 스택에 푸시한다.
스택에서 팝한 B노드를 방문하고 B의 자식인 E와 D를 푸시한다.
스택에서 팝한 D노드를 방문하고 B의 자식인 H와 G를 차례대로 푸시한다.
(잊지말자, 오른쪽 자식먼저 푸시해야 팝할때 왼쪽 자식이 먼저 나온다, 오른쪽 왼쪽 어느것이 먼저인지는 상관 없겠지만, 순서는 쭉 유지해야 한다!)
스택에서 팝한 G노드를 방문하고, G노드는 자식을 가지고 있지 않기 때문에 스택에 푸시할 값이 없다.
스택에서 H를 팝하고 H노드에 방문하고, H노드 역시 자식이 없기 때문에 스택에 푸시할 값은 없다.
스택에서 팝한 E노드를 방문하고, 역시 자식이 없어서 스택에 푸시할 값은 없다.
스택에서 팝한 C노드를 방문하고, C노드의 자식인 F를 스택에 푸시한다.
스택에서 팝한 F노드를 방문하고, 스택에 F의 자식인 I를 푸시한다.
스택에서 팝한 I노드를 방문하고, I노드는 자식이 없기 때문에 스택에 푸시할 값이 없고 동시에 스택도 빈 상태가 되기 때문에 Tree 순회를 종료한다.
결과적으로 Tree를 A➡B➡D➡G➡H➡E➡C➡F➡I 순서로 순회하게 된다.
중위순회 Inorder Traverse
void inorder_travers(node *t) {
if(t != tail) {
inorder_travers(t->left);
visit(t);
inorder_travers(t->right);
}
}두번째로 뿌리를 중간에 타는 방법은 아래와 같다.
- 왼쪽 작은나무(Subtree)를 방문한다.
- 뿌리를 방문한다.
- 오른쪽 작은나무(Subtree)를 방문한다.
뿌리인 A부터 시작해서 계속해서 왼쪽 노드로 진행하면서 Tree구조의 끝까지 이동한다.
그 과정에서 왼쪽 노드들은 A, B, D, G를 차례대로 스택에 Push하고 G는 스택에 푸시할 자식이 없으므로 스택에서 G를 Pop해서해서 방문한다.
스택에서 Pop한 D노드를 방문하고, D의 오른쪽 자식인 H를 스택에 Push한다.
스택에서 Pop한 D의 오른쪽 자식인 H노드를 방문한다.
스택에서 Pop한 B노드를 방문하고, B의 오른쪽 자식인 E노드를 스택에 Push한다.
스택에서 Pop한 E노드를 방문한다. E노드는 자식이 없기 때문에 스택에 따로 Push할 데이터가 없다!
스택에서 Pop한 A노드(뿌리 노드)를 방문하고, 오른쪽 자식인 C노드를 스택에 Push한다.
스택에서 Pop한 C노드를 방문한다.
이때 C노드는 왼쪽 자식이 없다는걸 주의해야한다!
만약 왼쪽 자식이 있다면, 왼쪽자식의 subtree를 먼저 순회하겠지만, 왼쪽 자식이 없기 때문에 오른쪽 자식인 F노드를 스택에 Push한다.
여기서, C노드에서 왜 F가 아니라 I임?? 하겠지만, 정신 단디 차려야한다.
먼저 기존의 스택(바로 전 그림 참고하자)에 있던 F를 Pop한다.
그리고 F 노드가 왼쪽 자식이 있는지를 확인한다.
애석하게도 F노드는 I라는 왼쪽자식이 있다...ㅋㅋ
따라서 F의 왼쪽 자식이 있기 때문에, F와I를 차례대로 스택에 Push하고 왼쪽 자식 노드로 이동한다.
이때 중요한건 A노드부터 시작해서 G까지 쭉 멈추지 않고 이동한것 처럼, F에서부터 왼쪽 자식 노드가 없을때까지 쭉 이동한다는 점이다.
여기선 I노드가 마지막이기에(왜냐면 I는 자식이 없으니) 스택에서 I를 Pop해서 I노드를 방문하게된다.
마지막으로 F를 스택에서 Pop해서 방문한다.
이때 스택은 비게되므로 Tree 순회도 종료되게 된다.
따라서 결과적으로 Tree를 G➡D➡H➡B➡E➡A➡C➡I➡F 순서로 순회하게 된다.
후위순회 Postorder Traverse
void postorder_travers(node *t) {
if(t != tail) {
postorder_travers(t->left);
postorder_travers(t->right);
visit(t);
}
}
먼저 뿌리노드인 A부터 시작해서 각각 왼쪽 자식의 끝까지 스택에 Push한다.
따라서 스택에 A -> B -> D -> G 순서로 Push가 될것이고, G노드는 자식이 없기때문에, 스택에서 Pop해서 G노드를 방문한다.
다음으로 D의 오른쪽 자식인 H노드를 방문한다.
기억하자! 뿌리를 가장 나중에 방문하는 후위순위 방법이다.
Tree구조는 서로다른 작은 Tree들의 조합인걸 알 수 있다. (그림보면 알겠지?)
따라서 D, G, H도 작은 Subtree이고, D가 뿌리임과 동시에 왼쪽자식인 G와 오른쪽 자식인 H를 가지고 있는 나무구조다.
따라서 뿌리인 D를 가장 나중에 방문하게 된다!
여기서 중요한건 G노드에서 H노드로 점프해서 갈 수 없다는 점이다.
따라서 스택에서 G노드의 부모노드인 D를 스택에서 Pop한후에, D가 오른쪽 자식이 있는지 검사를한다.
검사결과 오른쪽 자식이 있다면, 방금 검사를 위해 스택에서부터 꺼내온 D를 다시 스택에 Push하고 오른쪽 자식인 H도 스택에 푸시한다.
동시에 더 이상 H노드가 자식이 없기 때문에 스택에서 H를 Pop한 다음 H노드를 방문한다.
다음으로 스택에서 Pop한 D노드를 방문한다.
기억하자!! D노드는 G와 H의 부모(뿌리)노드 이기때문에 마지막에 방문하는거다! 후위순회!
D에서 E로 이동하기 위해서는 D의 부모노드인 B를 먼저 스택에서 Pop한 다음 B의 오른쪽 자식이 있는지 없는지를 먼저 검사해야 한다.
검사 후 오른쪽 자식을 취한 다음 스택에 B를 푸시하고 자식인 E를 푸시한다.
따라서 결과적으로 B의 오른쪽 자식인 E노드를 방문하게 된다.
이제 D와 E의 부모이자 뿌리인 B노드를 방문하기 위해서 스택에서 B를 Pop해서 방문한다.
B노드에서 C노드로 이동하기 위해서 먼저 B의 부모인 A노드를 스택에서 Pop해서 A노드가 오른쪽 자식을 갖고있는지 먼저 확인한다.
이때 오른쪽 자식이 있기 때문에 차례대로 부모인 A와 자식인 C를 스택에 Push한다.
중요한건 스택에 Push된 C노드 또한 자식이 있기때문에 자식의 마지막 끝까지 이동하면서 F와 I도 스택에 Push된다.
이때 I노드는 더이상 자식이 없기 때문에 I노드를 스택에서 Pop한 다음 방문하게 된다.
F노드는 오른쪽 자식이 없기 때문에, I의 부모노드인 F노드를 방문한다.
F의 부모노드인 C노드를 스택에서 Pop해 방문한다.
마지막으로 뿌리노드인 A노드를 방문한다.
스택에서 A노드를 Pop해서 방문하고, 이때 스택은 비어있으므로 Tree순회를 종료하게 된다.
따라서 결과적으로 Tree를 G➡H➡D➡E➡B➡I➡F➡C➡A 순서로 순회하게 된다.
개인적으로 후위순회가 좀 논리적으로 따라가기가 귀찮았던거 같다.
층별순회 Levelorder Travers
마지막으로 층별로 나무를 타는 방법인데, 말 그대로 층별로 내려오면서 좌측 노드에서 우측 노드로 이동하면서 나무를 타는 방법이다.
일단 층별로 나무를 타는 방법은 앞에서 보여준 것들과는 다르게 Queue를 이용해서 순회하게 된다.
- 큐에 뿌리 노드를 Put한다.
- 큐가 비어있지 않은지 확인한다.
2-1. 큐에서 get한 노드를 t에 대입하고 방문한다.
2-2. t의 왼쪽 자식이 있다면 큐에 Put한다.
2-3. t의 오른쪽 자식이 있다면 큐에 Put한다. - 끝
void levelorder_travers(node *t) {
put(t);
while(!is_queue_empty()) {
t = get();
visit(t);
if(t->left != tail)
put(t->left);
if(t->right != tail)
put(t->right);
}
}
뿌리 노드인 A를 방문하고 큐에 왼쪽자식과 오른쪽 자식인 B, C를 차례대로 Put한다.
큐에서 Get한 B노드를 방문하고, B노드의 자식인 D, E를 차례대로 큐에 Put한다.
큐에서 Get한 C노드를 방문하고, C노드의 자식인 F를 큐에 Put한다.
큐에서 Get한 D노드를 방문하고, D의 자식인 G와 H를 차례대로 큐에 Put한다.
큐에서 Get한 E노드를 방문하고, E노드는 자식이 없기때문에 큐에 Put할게 없다.
큐에서 Get한 F노드를 방문하고, F노드의 자식인 I를 큐에 Put한다.
큐에서 Get한 G노드를 방문하고, 자식이 없기 때문에 큐에 Put할거는 따로 없다.
큐에서 Get한 H노드를 방문하고, 자식이 없기 때문에 큐에 Put할거는 따로 없다.
큐에서 Get한 I노드를 방문하고, 자식이 없기 때문에 큐에 Put할것도 없거니와 Queue가 비게되므로 순회를 멈춘다.
따라서 왼쪽부터 오른쪽 방향으로 레벨(혹은 깊이) 순서로 노드를 순회하는걸 볼 수 있고, 결과적으로 Tree를 A➡️B➡️C➡️D➡️E➡️F➡️G➡️H➡️I 순서로 순회하게 된다.
정리
Tree구조는 이전에 정리한 Stack, Queue에 비해 자세히 설명은 안했다.
스택과 큐는 이제 활용해야하는 단계이지만, Tree는 앞으로 계속해서 배울 알고리즘을 통해서 더 구체적으로 배워야 하기 때문이다!
예시 코드
//
// main.c
// Binary_Tree
//
// Created by 박재현 on 2024/05/12.
//
#include <stdio.h>
#include <stdlib.h>
typedef struct _node {
int key;
struct _node *left;
struct _node *right;
} node;
node *head, *tail;
void init_tree(void) {
head = (node *)malloc(sizeof(node));
tail = (node *)malloc(sizeof(node));
head->left = tail;
head->right = tail;
tail->left = tail;
tail->right = tail;
}
void visit(node *t) {
printf("visit value is %d\n", t->key);
}
int is_queue_empty(void) {
return head->left == tail && head->right == tail ? 1 : 0;
}
void put(node *t) {
// do nothing
}
node *get(void) {
return 0;
}
void preorder_traverse(node *t) {
if(t != tail) {
visit(t);
preorder_traverse(t->left);
preorder_traverse(t->right);
}
}
void inorder_travers(node *t) {
if(t != tail) {
inorder_travers(t->left);
visit(t);
inorder_travers(t->right);
}
}
void postorder_travers(node *t) {
if(t != tail) {
postorder_travers(t->left);
postorder_travers(t->right);
visit(t);
}
}
void levelorder_travers(node *t) {
put(t);
while(!is_queue_empty()) {
t = get();
visit(t);
if(t->left != tail)
put(t->left);
if(t->right != tail)
put(t->right);
}
}
int main(int argc, const char * argv[]) {
// insert code here...
printf("Hello, World!\n");
return 0;
}