[자료구조] 트리(Tree)와 이진 트리(Binary tree)란?

 

트리(Tree)란?

트리(Tree)란, 계층적인 구조를 나타내는 자료구조이다.

조직도, 파일 디렉터리 구조에서 이러한 트리 구조가 많이 사용된다.

 

트리의 구성 요소

트리는 노드(node)와 간선(edge, link)로 이루어진다.

노드(node)는, 트리의 데이터를 저장하는 단위이며, 위 사진에서의 숫자가 저장되어 있는 부분이 노드라고 볼 수 있다.

간선(edge, link)는, 노드와 노드를 연결하는 선이며, 트리에서의 간선은 부모-자식 계층 관계만을 나타낸다.

위 사진에서 볼 수 있듯이, 간선이 상하관계로만 연결되어 있고, 좌우로는 연결되어있지 않은 모습을 확인할 수 있다. 이 부분에 대해서는 뒤에서 추가적으로 설명하도록 하겠다.

또한 노드의 개수가 N개일 때, 간선의 개수는 항상 N-1개이다. 

 

트리 구조에서 사용되는 용어들

트리 구조에서 사용되는 용어들을 본격적으로 설명하기 전에, 예시 트리를 하나 준비했다.

후술할 트리 구조에서의 용어들을 예시 트리와 함께 살펴보도록 하겠다.

트리 구조에서 사용되는 용어들은 다음과 같다.

 

• 루트(root) : 트리 구조에서의 맨 위에 위치한 노드 - 예시 트리에서의 A
• 부모(parent)-자식(child) : 간선으로 연결된 노드끼리의 관계 - 예시 트리에서의 A-B, A-C, C-F, F-G 등등의 관계
• 리프(leaf) : 자식 노드가 존재하지 않는 노드(트리) - 예시 트리에서의 D, E, G, H
• 내부 노드(internal node) : 자식 노드가 하나라도 존재하는 노드로, 리프 노드가 아닌 노드 - 예시 트리에서의 A, B, C, F
• 형제(sibling) : 같은 레벨에 위치한 노드들의 관계 - 예시 트리에서의 B-C, D-E-F, G-H 관계
• 조상(ancestor)-후손(descendant) - 예시 트리에서, D의 조상은 A, B가 되고,  H의 조상은 A, C, F가 된다
• 차수(degree) : 자식 노드의 개수 - 예시 트리에서, F의 차수는 2, G의 차수는 0
• 레벨(level) : 루트 노드로부터 얼마나 떨어져 있는지를 나타내며, 루트 노드는 레벨 0 - 예시 트리에서 B와 C는 레벨 1
• 높이(height) : 루트 노드부터 시작해서 리프 노드까지의 거리 : 예시 트리의 높이는 4
• 서브트리(subtree) : 트리 안의 트리, 특정 노드를 기준으로 하여 해당 노드의 후손들로 구성한 트리

 

 

이진 트리(Binary tree)란?

이진 트리(Binart tree)는 트리의 한 종류로써, 모든 노드가 최대 두 개의 자식을 가지는 트리이다.

즉 다음과 같은 성질을 가진다

• 모든 노드의 차수가 2 이하이다.
• 모든 노드가 2개의 서브트리를 가지고 있다.(서브트리는 빈 트리일 수 있다.)

위에서 제시된 예시 트리도 이진 트리라고 할 수 있다. 이러한 이진 트리에는 여려 종류가 있는데, 하나씩 살펴보도록 하겠다.

정 이진 트리(Full binary tree)

모든 노드가 0개 또는 2개의 자식 노드를 가지는 이진 트리이다. 즉, 리프 노드를 제외한 모든 노드는 자식 노드가 2개이다.

정 이진 트리

포화 이진 트리(Perfect binary tree)

트리의 모든 레벨에서 노드가 모두 채워져 있는 이진 트리로, 높이가 $h$일때, 노드 개수는 $2^{h+1}$이다.

포화 이진 트리

완전 이진 트리(Complete binary tree)

마지막 레벨을 제외한 모든 레벨에 노드가 완전히 채워져 있고, 마지막 레벨에는 노드가 왼쪽부터 채워져 있는 이진 트리

완전 이진 트리

편향 트리(Skewed tree)

리프 노드를 제외한 모든 노드가 하나의 자식 노드만 가지는 트리

트리의 순회(traversal)

트리의 순회(traversal)란, 정해진 순서에 따라 트리의 모든 노드를 한 번씩 방문하는 작업을 말한다.

트리의 순회 방법은 크게 4가지가 있는데,

• 깊이 우선 탐색(depth first traversal)
  • 전위 순회(preorder traversal)
  • 중위 순회(inorder traversal)
  • 후위 순회(postorder traversal)
• 너비 우선 탐색(breadth first traversal)
  • 레벨 순서 순회(level order traversal)

로 이루어져 있다. 위에서 제시된 예시 트리와 함께 하나씩 살펴보도록 하겠다.

 

전위 순회(Preorder traversal)

전위 순회는 다음과 같은 우선순위를 가진다.

1. 현재 노드(상위 노드)
2. 왼쪽 서브트리
3. 오른쪽 서브트리

즉, 가운데에 위치한 노드부터 보고, 왼쪽 오른쪽 순서로 본다는 것이다.

예시 트리와 함께 살펴보겠다.

다음과 같은 트리에서, 전위 순회를 통해 탐색한다고 하면, 가장 먼저 탐색될 노드는 어떤 것일까? 바로 A이다.

그 다음, 전위 순회의 우선순위에 따라 왼쪽 서브트리로 이동한다. 왼쪽 서브트리에서도 상위 노드인 B가 존재하기 때문에, 우선순위에 따라 B를 탐색한다.

이후, 다시 왼쪽 서브트리로 이동한다. 이 서브트리의 상위 노드는 D이기 때문에 D를 탐색한다.

이 서브트리에는 다른 자식 노드가 없기 때문에 이전에 탐색했던 B를 상위 노드로 하는 서브트리로 돌아간다. 아직 탐색하지 못한 오른쪽 서브트리가 남아있기에 이동하여 탐색한다.

 B를 상위노드로 하는 서브트리도 탐색이 완료되었으니, A를 상위 노드로 하는 서브트리로 돌아간 다음, 탐색하지 못한 오른쪽 서브트리를 탐색한다.

 

이러한 규칙에 의거하여 해당 트리를 탐색하면 다음과 같은 순서로 탐색이 진행된다.

이러한 과정은 재귀를 통해 구현될 수 있다. 전위 순회를 C++로 구현해보면 다음과 같다.

// 각 노드를 구조체로 선언
struct Node
{
	char data;
	Node* left;
	Node* right;

	Node(char d) : data(d), left(nullptr), right(nullptr) {}
};

void preorder(Node* node)
{
	if (node) {
    	// 전위 순회
		std::cout << node->data << ", ";
       	// 재귀를 이용하여 탐색 구현
		preorder(node->left);
		preorder(node->right);
	}
}

 

중위 순회(Inorder traversal)

중위 순회는 다음과 같은 우선순위를 가진다.

1. 왼쪽 서브트리
2. 현재 노드(상위 노드)
3. 오른쪽 서브트리

즉, 왼쪽부터 보고, 가운데, 오른쪽 순서로 본다는 것이다.

예시 트리를 중위 순회로 탐색하면 다음과 같은 결과가 나온다.

마찬가지로 재귀를 통해 구현할 수 있고, 다음과 같다

// 전위 순회에서 노드를 구조체로 구현하여 여기서는 생략
void inorder(Node* node)
{
	if (node) {
    	// 재귀를 통해 구현
		inorder(node->left);
		std::cout << node->data << ", ";
		inorder(node->right);
	}
}

 

후위 순회(Postorder traversal)

후위 순회는 다음과 같은 우선순위를 가진다.

1. 왼쪽 서브트리
2. 오른쪽 서브트리
3. 현재 노드(상위 노드)

즉, 왼쪽, 오른쪽, 가운데 순서로 본다는 것이다.

예시 트리를 후위 순회로 탐색하면 다음과 같은 결과가 나온다.

구현은 다음과 같다.

void postorder(Node* node)
{
	if (node) {
		postorder(node->left);
		postorder(node->right);
		std::cout << node->data << ", ";
	}
}

 

레벨 순서 순회(Level order traversal)

레벨 순서 순회는, 낮은 레벨에 있는 노드들을 모두 방문한 이후, 큰 레벨로 이동하여 방문을 반복한다.

즉, 예시 트리에서는 다음과 같은 결과가 나온다.