[자료구조] 트리[Tree]

 

https://ko.wikipedia.org/wiki/%ED%8A%B8%EB%A6%AC_%EC%88%9C%ED%9A%8C

 

 

 먼저, 트리 관련 용어를 알아보자.

(나동빈의 '이것이 취업을 위한 코딩 테스트다'를 참고했다.)

 

• 루트 노드:  부모가 없는 최상위 노드
• 단말 노드: 자식이 없는 노드
• 크기: 트리에 포한된 모든 노드의 개수
• 깊이: 루트 노드부터의 거리 ( 예) 노드 F의 깊이는 0이다.  예) 노드 A번의 깊이는 2이다. )
• 레벨 : 특정 깊이를 가지는 노드의 집합
• 높이: 깊이 중 최댓값
• 차수: 각 노드의 (자식 방향) 간선 개수

 

1. 트리

트리는 자료구조의 일종이며, 1. 사이클이 없이 2. 모든 정점이 연걸되어 있는 그래프이다.

사이클이 없는 그래프이기 때문에, 트리의 크기가 N이면 간선의 개수는 N-1개이다.

 

조건 1, 2만 만족하면 트리이다. 따라서 루트 노드의 존재여부는 트리 여부의 영향을 미치지 않는다.

 

 

1)  루트 없는 트리

 

루트 없는 트리

 

 

2)  루트 있는 트리

모든 정점이 루트 노드로 사용될 수 있다. 보통 1번 정점이 루트 노드로 많이 사용된다.루트 노드가 정해지면 가능한 일이 생긴다.

 

1. 트리의 방향을 정할 수 있다.

루트 노드를 보통 최상위 노드라고 한다.

그 이유는 루트 노드를 맨 위에 두고, 아래로 뻗어나가게 방향을 정했기 때문이다.

 

2. 부모-자식 관계를 만들 수 있다.

루트 노드만 부모가 없는 노드이다. 자식 노드가 없는 노드는 터미널 노드라고 한다.  

( 부모 노드가 같은 노드끼리는 형제 노드라고 한다. )

 

루트 있는 트리는 가계도와 같은 계층적 구조를 표현할 때 사용한다.

 

 

2. 트리의 순회

트리 자료구조에 포함된 노드를 특정한 방법으로 한 번씩 방문하는 방법이다.

(위키백과 '트리 순회'를 참고했다.)

 

 

https://ko.wikipedia.org/wiki/%ED%8A%B8%EB%A6%AC_%EC%88%9C%ED%9A%8C

 

 

1) 전위 순회 (pre-order traverse)

1.  노드를 방문한다.

2.  왼쪽 서브 트리를 전위 순회한다.

3. 오른쪽 서브 트리를 전위 순회한다.

 

F->B->A->D->C->E->G->I->H (root, left, right)

 

 

2)  중위 순회 (in-order traverse)

1. 왼쪽 서브 트리를 중위 순회한다.

2. 노드를 방문한다.

3. 오른쪽 서브 트리를 중위 순회한다.

 

A->B->C->D->E->F->G->H->I (left, root, right)

 

3) 후위 순회 (post-order traverse)

1. 왼쪽 서브 트리를 후위 순회한다.

2. 오른쪽 서브 트리를 후위 순회한다.

3. 노드를 방문한다.

 

A->C->E->D->B->H->I->G->F (left, right, root)

 

4) 레벨 순서 순회 [너비 우선 순회] 

모든 노드를 낮은 레벨부터 차례대로 순회한다.

 

F->B->G->A->G->I->C->E->H

 

 

트리는 이진 탐색 트리, 균형 트리 (AVL 트리, red-black 트리), 이진 힙(최대힙, 최소힙)등이 있다.

이것은 다른 게시글에서 자세히 알아보자.