트리 (Tree)
들어가는 말
우리는 지금까지 리스트, 스택, 큐와 같은 자료구조를 살펴보았다.
이들은 내부 구현이 배열이든 연결 리스트이든 데이터가 논리적으로 한 줄로 이어지는 선형 구조라는 공통점이 있다.
따라서 우리는 자료를 어떤 규칙으로 삽입하고 삭제할 수 있는지에 주목해 왔다.
하지만 현실의 데이터는 단순히 한 줄로 나열되기보다 데이터마다 중요도나 계층이 다르고 서로 다양한 관계를 맺는 경우가 많다.
회사 조직도에는 직급과 역할에 따른 구성원의 관계가 있고, 컴퓨터의 폴더 구조에는 상위 폴더와 하위 폴더의 관계가 있다.
이처럼 하나의 데이터가 여러 데이터와 관계를 맺어 계층을 이루는 경우에는 선형 자료구조만으로 표현하기 어렵다.
트리는 이러한 계층적 관계를 표현하기 위한 비선형 자료구조다.
트리의 구성 요소
Level 0, Depth 0 A Height 2
/ | \
Level 1, Depth 1 B C D Height 1, 0, 0
/ \
Level 2, Depth 2 E F Height 0, 0노드(Node)
node는 라틴어 nodus(매듭이나 마디)에서 유래한 말이다.
여러 선이나 관계가 만나거나 갈라지는 지점을 뜻하며, 다양한 분야에서 폭넓게 쓰인다.
트리 자료구조에서는 자료를 저장하고 다른 대상과 연결 관계를 맺는 기본 단위를 노드라고 한다.
간선(Edge)
노드와 노드 사이를 연결하는 선으로, 둘 사이의 관계를 나타낸다.
루트 노드(Root Node)
최상위에 있는 노드로, 그림에서는 A가 이에 해당한다.
부모 노드(Parent Node)
어떤 노드와 직접 연결되어 있으며, 그 노드보다 한 단계 위에 있는 노드를 말한다.
위 그림에서 A는 B, C, D의 부모 노드이고, B는 E와 F의 부모 노드다.
자식 노드(Child Node)
어떤 노드와 직접 연결되어 있으며, 그 노드보다 한 단계 아래에 있는 노드를 말한다.
위 그림에서 B, C, D는 A의 자식 노드이고, E와 F는 B의 자식 노드다.
형제 노드(Sibling Node)
같은 부모 노드를 가진 노드들을 말한다.
위 그림에서 B, C, D는 서로 형제 노드이고, E와 F도 서로 형제 노드다.
단말 노드(Leaf Node, Terminal Node)
자식이 없는 노드를 말하며, 그림에서는 C, D, E, F가 이에 해당한다.
내부 노드(Internal Node)
자식이 하나 이상 있는 노드를 말하며, 그림에서는 A와 B가 이에 해당한다.
부분 트리(Subtree)
트리의 어떤 노드를 새로운 루트로 보고, 그 노드와 모든 자손 노드를 포함한 트리를 말한다.
트리의 모든 노드는 각각 하나의 부분 트리를 이룬다.
위 그림에서 B를 루트로 하는 부분 트리는 B, E, F로 이루어진다.
레벨(Level)
루트 노드를 기준으로 몇 번째 층에 있는지를 나타낸다.
루트 노드의 레벨은 정의에 따라 다를 수 있는데, 이 글에서는 0으로 본다.
깊이(Depth)
특정 노드가 루트 노드에서 얼마나 떨어져 있는지를 나타낸다.
루트 노드부터 해당 노드까지 지나야 하는 간선의 수로 계산하며, 루트 노드의 깊이는 0이다.
따라서 위 그림에서 A의 깊이는 0이고, B, C, D의 깊이는 1이며, E와 F의 깊이는 2이다.
높이(Height)
특정 노드에서 가장 멀리 있는 단말 노드까지의 거리를 나타낸다.
해당 단말 노드까지 지나야 하는 간선의 수로 계산한다.
단말 노드의 높이는 0이고 루트 노드의 높이는 트리 전체의 높이와 같다.
위 그림에서 C, D, E, F는 모두 자식이 없는 단말 노드이므로 높이는 0이다.
B의 높이는 자식 노드 E 또는 F까지의 간선 수가 1이므로 1이다.
C와 D는 B와 같은 깊이 1에 있지만 자식이 없으므로 높이는 0이다.
A에서 가장 먼 단말 노드인 E 또는 F까지는 A → B → E 또는 A → B → F처럼 간선 2개를 지나므로 A의 높이는 2이다.
이진 트리(Binary Tree)
A
/ \
B C
/ \ \
D E F각 노드가 자식을 최대 2개까지만 가질 수 있는 트리다.
자식은 항상 왼쪽과 오른쪽으로 구분된다.
예를 들어 위 그림에서 A는 왼쪽에 B, 오른쪽에 C를 자식으로 두고 있다.
자식이 하나도 없거나(F처럼), 한쪽만 있거나(C처럼), 양쪽 다 있을 수도 있다.
왼쪽 편향 이진 트리(Left-skewed Binary Tree)
A
/
B
/
C
/
D위 그림처럼 모든 내부 노드가 왼쪽 자식만 가지는 트리도 이진 트리다.
각 노드의 오른쪽 자리는 비어 있는데, 이처럼 자식이 없는 자리도 개념적으로 하나의 노드로 취급할 수 있다.
이 빈 자리를 공집합 노드 또는 널 노드(Null Node)라고 생각하는 것이다.
따라서 한쪽에만 실제 자식이 있어도 이진 트리의 구조를 이룰 수 있다.
포화 이진 트리(Perfect Binary Tree)
A
/ \
B C
/ \ / \
D E F G모든 내부 노드가 두 개의 자식 노드를 가지고, 모든 단말 노드가 같은 레벨에 있는 이진 트리다.
즉, 마지막 레벨까지 모든 노드가 빈자리 없이 채워진 형태다.
완전 이진 트리(Complete Binary Tree)
A
/ \
B C
/ \ /
D E F마지막 레벨을 제외한 모든 레벨이 채워져 있고, 마지막 레벨의 노드는 왼쪽부터 빈자리 없이 배치된 이진 트리다.
따라서 마지막 레벨만 채워지지 않을 수 있으며, 오른쪽에 빈자리가 생기기 전에 왼쪽부터 채워져야 한다.
순회(Traversal)
트리 순회란 트리에 있는 모든 노드를 정해진 순서에 따라 한 번씩 방문하는 과정을 말한다.
선형 자료구조에서는 한 원소를 방문한 뒤 다음에 방문할 원소가 하나로 정해져 있었다.
반면 트리는 하나의 노드에서 여러 자식 노드로 가지가 뻗어 나가기 때문에 방문 순서를 정하는 경우의 수가 다양하다.
따라서 현재 노드와 자식 노드들을 어떤 순서로 방문할지를 미리 정해야 한다.
이진 트리의 대표적인 순회 방식에는 전위 순회, 중위 순회, 후위 순회가 있다.
세 방식은 모두 현재 노드와 왼쪽·오른쪽 서브트리를 방문하지만, 현재 노드를 방문하는 시점이 서로 다르다.
각 순회 방식의 결과를 살펴보기 위해 다음 이진 트리를 예시로 사용한다.
1
/ \
2 3
/ \ /
4 5 6전위 순회(Preorder Traversal)
현재 노드를 먼저 방문한 뒤, 왼쪽 서브트리와 오른쪽 서브트리를 차례대로 방문하는 방식이다.
방문 순서는 현재 노드 → 왼쪽 서브트리 → 오른쪽 서브트리다.
1 2 4 5 3 6중위 순회(Inorder Traversal)
왼쪽 서브트리를 먼저 방문한 뒤 현재 노드를 방문하고, 마지막으로 오른쪽 서브트리를 방문하는 방식이다.
방문 순서는 왼쪽 서브트리 → 현재 노드 → 오른쪽 서브트리다.
4 2 5 1 6 3후위 순회(Postorder Traversal)
왼쪽 서브트리와 오른쪽 서브트리를 모두 방문한 뒤 현재 노드를 마지막에 방문하는 방식이다.
방문 순서는 왼쪽 서브트리 → 오른쪽 서브트리 → 현재 노드다.
4 5 2 6 3 1소스 코드
연결 리스트를 구현할 때는 Node 구조체를 선언하고, LinkedList 구조체에서 이를 사용하는 방식으로 구현했다.
이진 트리도 같은 방식으로 구현할 수 있지만, 여기서는 순회에 초점을 맞추기 위해 노드 구조체만 사용해 필요한 최소한의 기능으로 구성해 보겠다.
binary_tree.h
#ifndef BINARY_TREE_H
#define BINARY_TREE_H
typedef struct TreeNode
{
int data;
struct TreeNode* left;
struct TreeNode* right;
} TreeNode;
TreeNode* create_tree_node(void);
void destroy_tree_node(TreeNode* root);
void print_preorder(TreeNode* root);
void print_inorder(TreeNode* root);
void print_postorder(TreeNode* root);
#endif /* BINARY_TREE_H */binary_tree.c
#include <stdio.h>
#include <stdlib.h>
#include "binary_tree.h"
TreeNode* create_tree_node(void)
{
TreeNode* node = malloc(sizeof(TreeNode));
if (node == NULL)
return NULL;
node->data = 0;
node->left = NULL;
node->right = NULL;
return node;
}
void destroy_tree_node(TreeNode* root)
{
if (root == NULL)
return;
destroy_tree_node(root->left);
destroy_tree_node(root->right);
free(root);
}
void print_preorder(TreeNode* root)
{
if (root == NULL)
return;
printf("%d\n", root->data);
print_preorder(root->left);
print_preorder(root->right);
}
void print_inorder(TreeNode* root)
{
if (root == NULL)
return;
print_inorder(root->left);
printf("%d\n", root->data);
print_inorder(root->right);
}
void print_postorder(TreeNode* root)
{
if (root == NULL)
return;
print_postorder(root->left);
print_postorder(root->right);
printf("%d\n", root->data);
}main.c
#include <stdio.h>
#include "binary_tree.h"
int main(void)
{
TreeNode* node1 = create_tree_node();
TreeNode* node2 = create_tree_node();
TreeNode* node3 = create_tree_node();
TreeNode* node4 = create_tree_node();
TreeNode* node5 = create_tree_node();
TreeNode* node6 = create_tree_node();
node1->data = 1;
node2->data = 2;
node3->data = 3;
node4->data = 4;
node5->data = 5;
node6->data = 6;
node1->left = node2;
node1->right = node3;
node2->left = node4;
node2->right = node5;
node3->left = node6;
printf("Preorder\n");
print_preorder(node1);
printf("Inorder\n");
print_inorder(node1);
printf("Postorder\n");
print_postorder(node1);
destroy_tree_node(node1);
return 0;
}