[자료구조] 6일차 비선형 구조와 트리

트리

: 트리는 그래프의 특수한 형태 중 하나

그래프

• 정점과 간선으로 이루어져 있는 자료구조간선 - 정점 간의 관계를 나타냄
• 정점 - 자료, 상태 등 뭔가를 담고 있음. (노드라고도 표현)
• 어떤 정점에서 간선을 통해 다른 정점으로 이동할 수 있음.
• 다른 정점으로 이동하기 위해 거치는 모든 정점을 경로라고 함.

 

• 정점 4에서 정점 6으로 이동하는 경로들 중 하나는 4→5→3→6이 될 수 있음.

 

- 그래프의 간선은 방향이 있을 수도, 없을 수도 있다. - 방향이 있는 간선이 있는 그래프를 유향 그래프 라고 함.

- 처음시작한 정점으로 다시 돌아오는 경로를 ‘사이클’ 이라고 함. - 3 → 6 → 7 → 3 은 사이클

 

 

트리

: 그래프 중 특별한 성질을 갖는 그래프를 트리라고 함. = 사이클을 갖지 않는 그래프

 

특별한 성질

• 트리의 간선들은 모두 방향성을 갖는다.
• 어떤 정점을 가리키는 정점의 개수는 최대 1개이다.
• 어떤 정점에서 다른 정점으로 이동할 수 있는 경로는 1개다
• 트리는 사이클을 갖지 않는다.

• 어떠한 정점도 가리키지 않는 정점 = 루트 노드
• 루트 노드로부터의 거리를 깊이 라고 함.

 

• 정점 a가 정점 b를 가리킬 때 a는 b의 부모노드라고 하고 b는 a의 자식노드라고 함.
• 가리키는 정점이 없는 정점들은 리프노드 라고 함.

 

 

이진 트리 각 정점들이 자식 노드를 최대 2개까지만 갖는 트리

포화 이진 트리 리프 노드를 제외한 모든 정점이 항상 자식을 2개씩 갖고 있으면서 모든 리프 노드의 깊이가 동일한 트리 높이를 h라고 할 때, 정점의 개수는 항상 2h(제곱) - 1

 

 

완전 이진 트리 마지막 깊이를 제외하고 모든 정점이 완전히 채워져 있으며, 마지막 깊이의 정점들이 가능한 왼쪽에 있는 트리 포화 이진 트리에서 마지막 깊이의 정점이 오른쪽에서부터 일부 제거된 트리라고 볼 수 있음.

정 이진 트리 리프 노드를 제외한 모든 노드들이 두 개의 자식 노드를 갖고 있는 이진 트리. 모든 정점은 0개 또는 2개의 자식 노드를 가짐.