[ C언어 ] 자료구조_트리(Link)

1. 트리 자료구조란

트리 자료구조는 이름대로 나뭇가지를 모방하여 자료들을 구조화한 것입니다.

이전까지 했던 array, linkedlist, stack, queue, deque 자료구조 들은 선형으로 이루어진 자료구조였지만 이번 Tree 자료구조는 비선형 자료구조입니다.

트리구조는 크게 부모 노드와 자식 노드로 분류할 수 있습니다.

위 트리에서는 A가 부모 노드이고 왼쪽에 연결되어 있는(B) 노드와 오른쪽에 연결되어 있는(C) 노드는 A의 자식노드입니다.

그리고 (B) 노드 입장에서는 (D)와 (E) 노드가 자식노드이고 (B) 노드가 부모노드입니다.

 

가족관계도 와 동일한 구조라고 보시면 됩니다.

 

2. 트리 구성과 용어

트리구조의 명칭을 알아보겠습니다.

 

루트노드: 이는 트리에서 가장 상위에 위치해 있는 단 하나의 노드를 의미합니다. 위 그림에서는 A노드가 루트노드입니다.

 

부모노드: 자식노드 입장에서 한 단계 위에 있는 노드를 의미합니다.

 

자식노드: 부모 노드의 하위에 있는 노드를 의미합니다.

 

후손노드: 이는 자식노드에서 확장된 의미로 특정 노드의 하위에 있는 모든 노드를 의미합니다.

 

형제노드: 이는 같은 레벨에 위치한 노드를 의미합니다. 레벨 2에 위치해 있는  B와 C는 형제노드입니다.

 

단말노드: 이는 자식 노드가 하나도 없는 노드입니다. 위 트리에서는 E, F, G, H, I 가 단말 노드입니다.

 

차수: 이는 자식노드의 개수를 의미합니다. 위 트리에서 C 노드의 자식노드는 F, G, H 3개 이기 때문에 차수는 3입니다.

 

3. 일반트리, 이진트리

일반트리는 자식노드의 개수가 정해지지 않기 때문에 무한하게 구성할 수 있습니다. 이는 장점으로 볼 수 있지만 단점은 프로그램을 만들 때 복잡해질 수 있습니다. 

그래서 효율적이고 쉽게 제어할 수 있는 형태의 이진트리가 만들어졌습니다. 이는 자식 노드를 최대 2개로 제한하여 구성하도록 만든 트리입니다.

 

일반트리는 주로 파일시스템 조직도 등 현실과 관련된 구조를 만들 때 주로 사용되고

이진트리는 탐색 연산 등을 수행할 때 많이 사용됩니다.

 

상황에 따라 일반트리 와 이진트리를 선택해서 사용해야 하지만 이 블로그에서는 구현하기 쉽고 편한 이진트리 만 다루겠습니다.

 

4. 이진트리의 종류와 특징

이진트리에는 특수한 규칙이 있습니다.

 

포화	완전	기타

이진트리는 위와 같이 3가지로 분류할 수 있습니다.

 

그전에 한 가지 규칙을 설명드리겠습니다.

이진트리의 각 노드에는 레벨 순서대로 왼쪽에서 오른쪽으로 순서대로 번호를 붙일 수 있습니다. 위 트리에서 알파벳은 노드번호의 순서대로 부여한 것입니다.

 

포화 이진트리: 각 레벨에 노드가 모두 차있는 트리입니다.

완전 이진트리: 모든 노드가 레벨 순서 그리고 왼쪽부터 오른쪽으로 순서대로 있어야 합니다. 중간에 노드가 하나라도 비어있으면 성립이 안됩니다.

기타 이진트리: 이진트리의 조건만 만족하면 됩니다. 

 

5. 이진트리 구현방법

이진트리의 구조는 간단합니다. 데이터 변수와 양쪽 자식노드의 주소를 담을 포인터 변수를 가질 수 있는 노드를 만들고 노드끼리 연결을 시키면 됩니다. 이중 연결 리스트의 노드와 동일한 구조이지만 노드를 연결하는 방식이 다를 뿐입니다.

 

typedef struct Tree {
	element data;
	struct Tree* left;
	struct Tree* right;

}Tree;

 

이를 구조체로 이렇게 만들면 됩니다.

int main() {

	Tree node7 = { 7, NULL, NULL };
	Tree node6 = { 6, NULL, NULL };
	Tree node5 = { 5, NULL, NULL };
	Tree node4 = { 4, NULL, NULL };
	Tree node3 = { 3, &node6, &node7 };
	Tree node2 = { 2, &node4, &node5 };
	Tree node1 = { 1, &node2, &node3 };

	return 0;
}

그리고 이렇게 연결을 하면 트리구조가 만들어집니다.

 

지금까지 트리 자료구조에 대해 알아보았습니다.

다음에는 이진트리의 순회방법을 포스팅하겠습니다. 감사합니다.