자료구조) 트리(Tree)

트리(Tree)

 

트리구조는 계층적 구조이다.
비순차적 구조이기도 하다.

가장 최상단(Root)에서 계속적인 하위 노드를 추가해가는 구조이다,

즉 트리는 하위 계층구조를 표현할때 사용한다. 그래서  탐색에서 가장 많이 사용된다.

 

차수(Degree) 자식 노드의 개수
높이(Height) 루트 노드로부터 최하위 노드까지의 높이
레벨(Level) 트리의 계층의 층수 루트는 -1

 

트리의 종류는 다음과 같다.

 

Left Child-Right Sibling 표현법
 -왼쪽은 하위 노드들을 표현 오른쪽은 자신과 레벨이 동등한 노드들을 표현한다.

 

Binary Tree(이진트리)
 -이진트리는 루트를 제외한 모든 노드는 최대 2개의 노드만 가질 수 있다.

 
 완전 이진트리(complete binary tree)
   포화 이진트리에서 끝 부분을 제외하고 다른 것이 남아 있는 트리이다.
   포화 이진트리의 각 노드에 부모에서 자식으로, 왼쪽에서 오른쪽으로 번호를 매겼을 때 포화 이진트리는 아니지만
   그 번호가 연속되어 있는 경우 완전 이진트리가 된다.
 
 포화 이진트리(perfect binary tree)
   모든 단말 노드의 깊이가 같은 전 이진트리이다.

이진트리의 모든 노드를 방문하는 것 혹은 방문하여 어떤 작업을 하는 것을 이진 트리 탐색이라고 한다.
이진 트리 탐색의 방법에는 여러 가지가 있으며, 다음의 방법들이 유명하다.

1.in-order : 왼쪽 자식 노드, 내 노드, 오른쪽 자식노드 순서로 방문한다. (중위)
2.pre-order : 내 노드, 왼쪽 자식노드, 오른쪽 자식노드 순서로 방문한다. (전위)
3.post-order : 왼쪽 자식노드, 오른쪽 자식노드, 내 노드 순서로 방문한다. (후위)
4.level-order : 내 노드, 내 노드로부터 깊이 1인 노드들, 내 노드로부터 깊이 2인 노드들,. .. , 내 노드로부터 깊이 N인 노드들 (N: 나(트리)의 깊이)
 

 

 

 

★★☆☆☆