트리는 마치 나무를 거꾸로 한 모습과 비슷하다고 해서 붙여진 자료구조의 이름입니다.
트리와 관련된 용어 정리
트리에서 맨 위에 존재하는 노드 (최상위 노드) : root node
트리에서 뻗어 가는 가지 = branch
트리의 레벨 = 맨 위의 루트 노드부터 레벨 1, 그 다음줄이 레벨 2, 그 다음줄이 레벨 3, ….
(일부 책에서는 맨 위의 루트 노드부터 레벨 0, 그 다음 1, 2, … 로 매기는 경우도 있음.)
트리의 깊이(depth) = 맨 마지막 줄 레벨과 동일한 값을 가짐. (값만 동일하다 뿐이지 레벨 = 깊이라는 의미가 아니다.)
아래로 또 다른 노드가 연결되어 있지 않는 노드를 단말 노드 혹은 잎사귀 노드(leaf node)라고 한다.
서브 트리 : 큰 트리는 작은 트리들의 모음으로 구성되어 있는데, 이 큰 트리에 속하는 작은 트리들을 서브 트리라고 한다.
이진트리와 관련한 개념 정리
- 이진 트리 : 루트 노드 중심으로 두 개의 서브 트리로 나뉘며, 그 서브 트리도 이진 트리일 것. (자식 노드가 2개
이진 트리는 공노드(empty)도 허용한다. 이 말의 의미는, 어떤 루트 노드에 자식 노드가 하나만 있더라도, 남은 자식노드의 자리에는 공노드(empty)가 있다고 생각해서 전체적으로 이진 트리라고 볼 수 있다.
트리는 배열이나 연결리스트로 구현하는 것이 보편적이다.
- 배열로 트리를 구현할 때는 노드 넘버링을 할 때 통상 인덱스 1부터 시작함에 유념한다.
- Full Binary Tree : 이진트리가 완전히 꽉 찬 것 (노드에 자식 노드가 두 개로 다 차 있을 경우)
- Complete Binary Tree : 이진트리가 왼쪽부터 차곡 차곡 쌓인 것
이진 트리의 순회
- 이진트리의 순회 : 이진 트리의 모든 노드를 방문하는 것.
중위순회(inorder) : 위 그림에서 B-A-C 순으로 도는 것 (루트 노드를 중간에)
후위순회(postorder) : 위 그림에서 B-C-A 순으로 도는 것 (루트 노드를 마지막에)
전위순회(preorder) : 위 그림에서 A-B-C 순으로 도는 것 (루트 노드가 맨 처음에)
순회는 재귀적임을 유념한다.
이진 트리의 구현
이진 트리를 구현할 때에는 배열이나 연결리스트 등을 이용한다. 아래에서는 연결리스트를 이용하여 구현했다.
기본적으로 구현 시에는 양방향 연결리스트를 사용한다고 생각하면 된다.
간단하게 위와 같은 이진 트리를 구현하고 inorder 로 순회하면서 출력해 보도록 한다.
= 기대 결과 : B A C
- A : root node, B : left child, C : right child, B와 C는 레벨이 2로 같으며, 전체 트리의 깊이는 2이다.
- 각 노드는 다른 노드들을 가리킬 수 있게끔 right, left 포인터가 있어서 전체적으로 양방향 연결 리스트의 성격을 띤다.
소스코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <stdio.h>
#include <stdlib.h>
typedef struct _node{
int data;
struct _node * rightChild;
struct _node * leftChild;
}Node;
typedef Node * treePointer;
treePointer Create() { // 신규 노드 생성 함수
treePointer node = (treePointer)malloc(sizeof(*node));
node->rightChild = NULL;
node->leftChild = NULL; // 신규노드 생성 시 일단 left/right NULL로 초기화
return node;
}
void Inorder(treePointer ptr) { // 중위순회 함수. 재귀적으로 구현했음에 유의한다.
if (ptr) // ptr이 NULL이 아닐 때만 if문을 돈다.
{
Inorder(ptr->leftChild);
printf("%c ", ptr->data);
Inorder(ptr->rightChild); // 왼쪽 - 중간 - 오른쪽 순으로 생각하면 편함
}
}
int main(void)
{
treePointer root = Create();
treePointer N1 = Create();
treePointer N2 = Create();
root->data = 'A'; N1->data = 'B'; N2->data = 'C'; // 값 저장
root->leftChild = N1; root->rightChild = N2; // root 노드에 N1, N2 연결
Inorder(root);
}