트리

자료구조 트리에 대한 개념

 

트리는 그래프의 한 종류이며 비선형 자료구조로 계층적 관계를 표현한다.

- DAG(Directed Acyclic Graph; 방향성이 있는 비순환 그래프)의 한 종류이다.

 

트리는 하나의 루트 노드를 가지며 루트 노드는 0개 이상의 자식 노드를 가지고 있다(즉, 루트 노드만 있어도 트리)

트리는 노드와 노드를 연결하는 간선으로 구성되어 있으며 트리에는 사이클이 존재하지 않는다.

 

• 노드: 트리를 구성하는 기본 요소
  (노드의 구성요소: key, value, 하위 노드에 대한 포인터)
• 간선(링크, 엣지, 브랜치): 노드와 노드를 잇는 연결 
  간선의 수는 노드의 수  - 1이다.
• 루트 노드: 트리 내에서 단 한 개 존재, 부모 노드가 없는 노드
• 리프(말단, 외) 노드: 자식 노드가 없는 노드
• 형제 노드: 같은 부모 노드를 가지는 노드
• 내부 노드: 리프 노드가 아닌 노드
• 레벨 level: 트리의 특정 깊이를 가지는 노드의 집합 => 루트 노드의 레벨은 0
• 깊이 depth: 루트 노드에서 어떤 노드에 도달하기 위해 거쳐야 하는 간선의 수 => B의 깊이는 1
• 높이 height: 노드부터 말단 노드까지 중 가장 깊은 깊이를 높이라고 함 
• 차수 degree: 각 노드가 가진 간선의 수, 즉 자식의 수(트리의  차수: 각 노드의 차수 중 가장 큰 값)
• 크기 size: 자신을 포함한 자손 노드의 수

 

이진 트리란,

 

각 노드가 최대 두개의 자식 노드를 가지는 트리

 

이진 트리 순회 방식

1) 전위순회(pre-order traversal):  V => L => R

2) 중위순회(in-order traversal): L => V => R

3) 후위순회(post-order traversal): L => R => V

 

이진 트리의 종류

전 이진 트리

완전 이진 트리

포화 이진 트리

모든 노드의 자식노드는 0 또는 2개

마지막 레벨 제외하고 모든 레벨 채워짐

전 이진 트리면서 완전 이진 트리

노드는 왼쪽에서 오른쪽으로 채워져야 함

노드 수: 2^(k-1) => k: 트리 높이 모든 내부노드가 2개의 자식 노드를 가짐 모든 말단 노드가 동일한 깊이, 레벨 가짐