자료구조5 - 트리

여태까지 선형 자료구조에 대해 공부했었다면, 이 글에서는 대표적인 비선형 자료구조에 대해 다뤄보고자 한다. 

비선형 자료구조란, 선형 구조(순서O & 연속)에 해당하지 않는 모든 자료구조이다. 

비선형 자료구조에는 대표적으로 트리와 그래프가 있다.

여기서 트리는 그래프의 특수한 형태로 그래프의 한 종류라고 생각해도 된다.

그렇다면, 그래프는 무엇일까?

 

 

 

<그래프>

이처럼 트리는 여러 노드가 관계를 가지고 이루어져 있는 자료구조이다.

어떤 노드에서 다른 노드로 이동하기 위해 거치는 모든 노드를 경로라고 하며, 여러 가지 경로가 존재한다.

어떤 노드에서 출발하여 다시 자기 자신 노드로 돌아오는 경로가 있을 수도 있는데 이를 사이클이라고 한다.

여기서 노드 간의 관계를 나타내는 간선은 방향이 존재할수도, 존재하지 않을 수도 있는데 방향이 존재하는 간선을 포함한 그래프를 유향 그래프라고 한다.

유향 그래프에서는 방향이 존재하는 간선은 항상 그 방향으로만 지나갈 수 있고, 방향이 없는 간선은 자유자재로 지나다닐 수 있다.

 

 

 

 

<트리>

트리의 특징들을 잘 기억해두자!

 

임의의 노드 A가 다른 노드 B를 가리킬 때 => A는 B의 부모노드 /B는 A의 자식노드

가리키는 노드가 없는 노드들(즉, 마지막에 끝에 위치하는 노드들) =>리프 노드

 

활용 예시)

디렉터리(폴더) - 운영체제에서 파일을 분류하기 위해 사용하는 폴더는 트리 구조의 대표적인 예시이다.

 

<트리의 종류>

1. 이진 트리

 

2. 포화 이진 트리

3. 완전 이진 트리

 

4. 정 이진 트리