[2022 1학기] 12주차 - 트리

1. 트리(Tree)란?

그래프의 한 종류로 방향성을 가지며 사이클이 없는 하나의 연결 그래프

DAG(Directed Acyclic Graph, 방향 비순환 그래프)의 한 종류

노드로 이루어진 비선형 자료구조로서

하나의 루트 노드를 갖고, 루트 노드는 0개 이상의 자식 노드를 가진다.

루트 노드를 제외한 나머지 노드들은 각각 루트의 부분트리(재귀적 정의)

 

-노드 용어

루트 노드: 부모가 없는 노드, 하나의 루트만을 가짐

부모 노드: 어떤 노드에 연결된 이전 레벨의 노드

자식 노드: 어떤 노드에 연결된 다음 레벨의 노드

조상 노드: 루트에서부터 특정 노드에 이르기까지 있는 모든 노드

단말 노드: 자식이 없는 노드, =잎 노드

간선: 노드를 연결하는 선

형제 노드: 같은 부모를 가지는 노드

 

-트리 용어

노드의 크기(size): 자신을 포함한 모든 자손 노드의 개수

깊이(depth): 루트에서 어떤 노드에 도달하기 위해 거쳐야 하는 간선의 수

레벨(level): 트리의 특정 깊이를 가지는 노드의 집합

노드의 차수(degree): 하위 트리 개수(특정 노드에서 자식 노드로 나가는 간선 개수)

트리의 차수(degree): 트리의 최대 차수

트리의 높이(height): 루트 노드에서 가장 깊숙히 있는 노드의 깊이

서브 트리(sub-tree): 자식 노드를 루트로 하는 트리

 

-트리 종류

이진 트리: 부모 노드로부터 이어진 자식 노드가 0개부터 2개까지인 트리

완전 이진 트리: 마지막 레벨을 제외한 모든 높이에서 노드가 완전히 채워져 있는 이진 트리

전 이진 트리: 모든 노드가 0개 또는 2개의 자식 노드를 갖는 트리

포화 이진 트리: 전 이진 트리이면서 완전 이진 트리

이진 탐색 트리: 이진 트리의 성질을 만족하고 '모든 왼쪽 자식<현재 노드<모든 오른쪽 자식'을 만족하는 트리

균형 이진 탄색 트리: 편향된지 않고 좌우의 높이 차가 같은 이진 탐색 트리 -> AVL-TREE, Red-Black-Tree

 

 

2. 동작 원리

-트리의 성질

'최소 연결 트리'라고도 불리며 계층 모델이다

노드가 N개인 트리는 항상 N-1개 간선을 가진다

임의의 두 노드 간의 경로는 유일해야 하기 떄문에 두 정점 사이에 반드시 1개의 경로만을 가진다

 

-트리 순회 

전위 순회(pre-order): <현재 노드, 왼쪽 자식 노드, 오른쪽 자식 노드>

중위 순회(in-order): <왼쪽 자식 노드, 현재 노드, 오른쪽 자식 노드>

후위 순회(post-order): <왼쪽 자식 노드, 오른쪽 자식 노드, 현재 노드>

레벨 순위 순회(level-order): 낮은 레벨부터 순서대로 모든 노드 순회

 

 

3. 코드

//트리 순회 코드
typedef pair<char, char> PCC;

pair<char, PCC> tree[26];
int N;

void preorder(char node) {
	//root left right
	if (node == '.')return;

	printf("%c", node);
	preorder(tree[node - 'A'].second.first);
	preorder(tree[node - 'A'].second.second);
}


void inorder(char node) {
	//left root right
	if (node == '.')return;

	inorder(tree[node - 'A'].second.first);
	printf("%c", node);
	inorder(tree[node - 'A'].second.second);
}

void postorder(char node) {
	//left right root
	if (node == '.') return;

	postorder(tree[node - 'A'].second.first);
	postorder(tree[node - 'A'].second.second);
	printf("%c", node);
}


int main() {
	scanf("%d", &N);

	while (N--) {
		char parent, left, right;
		scanf("\n%c \n%c \n%c", &parent, &left, &right);
		
		tree[parent - 'A'].first = parent;
		tree[parent - 'A'].second.first = left;
		tree[parent - 'A'].second.second = right;
	}

	preorder('A');
	printf("\n");
	inorder('A');
	printf("\n");
	postorder('A');
	printf("\n");



	return 0;
}

 

 

※공부 중 작성한 내용이기에 틀린 부분이 있을 수도 있습니다!