트리(Tree)

트리 : 사이클이 없는 그래프, 정점의 개수 : V, 간선의 개수 : V-1

 

루트가 있는 그래프 : 루트를 1번이라고 하며, 루트부터 아래로 방향을 정할 수 있다.

부모(Parent)

자식(Children)

단말 정점(Leaf Node, Terminal Node) : 자식이 없는 노드

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

깊이(Depth) : 루트에서 부터 거리(루트의 깊이는 0 or 1로 표기가능)

높이(Height) : 깊이중 가장 큰값

조상(Ancestor) : 자기자신을 포함하여 루트와 이어지는 노드

자손(Descendent) : 조상과 반대

트리의 지름(Diamater) : 트리에 존재하는 모든 경로 중에서 가장 긴 것의 길이

 - 2번의 탐색으로 구할 수 있다.

 - 1. 루트에서 모든 정점까지의 거리를 구한다.

 - 2. 가장 먼거리의 정점을 루트로 잡고 모든 정점까지의 거리를 구한다.

 - 이 때 구한 가장 먼거리가 지름이다.

 

이진트리(Binary Tree) : 자식을 최대 2개만 가지고 있는 트리

 - 힙, 세그먼트 트리는 이진트리에 해당

 - 이진트리중 성질에 따라 이진검색트리

 

트리의 표현(Representation of Tree)

트리는 그래프이기 때문에, 그래프의 표현과 같은 방식으로 저장할 수 있다.

하지만 인접행렬의 경우 구조적으로 비효율적인 경우가 생길 수 있다.

최대비효율 일경우 V개를 저장할 때, 2^V의 공간 복잡도를 가진다.

 

트리의 성질을 이용하여 저장하는 방법이 몇가지있다.

1. 부모만 사용

 - 어떤 노드의 부모를 찾을 경우 시간 복잡도 : O(1)

 - 어떤 노드의 자식을 찾을 경우 시간 복잡도 : O(V)

ex)parent[i]

2. 2x+1(이진트리의 경우)

 - 부모노드가 x인 경우에 자식의 노드는 2*x, 2*x+1로 나타내면 된다.

 

3. 인접리스트의 변형된 방식을 사용하는것.
 - A[i][0]에 i의 왼쪽자식, A[i][1]에 i의 오른쪽 자식을 저장할 수 있다.(인접리스트의 변형된 방식)

 - 일반적으로 트리의 자식의 개수를 알 수 없으므로, 그냥 인접리스트를 사용하는것이 더 좋다.

 

 

그래프(트리)

트리의 순회(Tree Traversal)

트리의 모든 노드를 방문하는 순서이다.

그래프의 경우에는 DFS와 BFS가 있었지만, 트리에서는 노드의 방문 시기에따라 세가지 방법이 있다.

 

1. 전위순회(Pre-order)

 - 노드방문

 - 왼쪽자식 서브트리 전위순회

 - 오른쪽자식 서브트리 전위순회

 - DFS와 같은 방식

 - ex)ABDGHECFI

 

2. 중위순회(In-order)

 - 왼쪽자식 서브트리 중위순회

 - 노드방문

 - 오른쪽자식 서브트리 중위순회

 - 이진트리가 아닐경우 모호함

 - ex)GDHBEACFI

 

3. 후위순회(Post-order)

 - 왼쪽자식 서브트리 후위순회

 - 오른쪽자식 서브트리 후위순회

 - 노드방문

 - ex)GHDEBIFCA

//트리의 순회
int treeArr[255][2]; //[i][0]을 왼쪽, [i][1]을 오른쪽 

void pre_order(int node) {
	if (node == 0) return;
	printf("%c", node + 'A' - 1);
	pre_order(treeArr[node][0]);
	pre_order(treeArr[node][1]);
}

void in_order(int node) {
	if (node == 0) return;
	in_order(treeArr[node][0]);
	printf("%c", node + 'A' - 1);
	in_order(treeArr[node][1]);
}

void post_order(int node) {
	if (node == 0) return;
	post_order(treeArr[node][0]);
	post_order(treeArr[node][1]);
	printf("%c", node + 'A' - 1);
}

 

 

트리의 탐색

트리는 사이클이 없고 임의의 두 정점 사이의 경로는 1개이다. 고로 BFS 알고리즘을 이용해서 최단거리를 구할 수 있다.(경로가 1개이므로)