C++ 기초 : tree (1)

---

list는 노드를 관리합니다.

 

노드를 vertex(정점)라고 부르기도 합니다.

 

이러한 노드 간의 연결 관계를 표현할 수 있으면

이것은 그래프입니다.

 

예를 들어 지하철 노선 같은 경우도

그래프라고 볼 수 있죠.

 

 

---

 

 

아래 그림을 보시죠.

 

그래프의 연결 관계를 봤을 때

처음 노드에서 한 바퀴를 돌아

다시 처음 노드로 돌아올 수 있다면

이를 순환(Circuit, Cycle) 가능하다고 표현합니다.

 

 

그러나 트리는 아래 그림처럼

 

이러한 순회가 불가능한 그래프입니다.

 

연결 관계를 보면 맨 아래 노드에서

처음 노드로 갈 방법이 없죠?

 

 

---

 

 

그래프(Graph)와 트리(Tree)는 모두 자료 구조이며,

트리는 그래프의 일종입니다.

 

포함 관계를 그림으로 표현하자면 위 그림과 같죠.

 

 

트리는 부모 노드와 자식 노드를 연결한 구조로

가족 관계나 회사 조직도처럼 계층 구조를

표현하는데 용이합니다.

 

컴퓨터에서 대표적인 트리가 폴더입니다.

폴더에 들어가면 또 다른 폴더가 나오고

그 폴더 안에 또 폴더가 있을 수 있죠.

 

이러한 트리 중에서 자식을 두 개 이하로 

제한한 트리를 이진 트리라고 합니다.

 

그럼 아래 그림과 같은 트리는

 

이진 트리가 아닐까요?

 

저 상태를 기준으로 판단하면 이진 트리가 맞습니다.

 

이진 트리는 자식이 두 개 이하로 제한된 트리지,

자식이 반드시 두 개가 있어야 하는 트리가 아니기 

때문이죠. 그래서 자식이 2개를 넘지만 않는다면 이진 트리입니다.

 

 

---

 

 

 

트리에 Level이라는 개념이 있습니다.

부모 노드로부터 자식 노드까지의 깊이를 표현하는 것입니다.

 

아래 그림을 보시죠.

 

현재 그림 기준,

가장 맨 위의 있는 노드를 레벨 0으로 보면 (1로 보는 경우도 있습니다.)

가장 마지막에 있는 노드를 레벨 3으로 볼 수 있습니다.

 

가장 높은 레벨을 기준으로 높이를 판단하므로

해당 트리의 높이는 3이라고 볼 수 있습니다.

 

 

또한 맨 위에 있는 노드, 즉 부모 노드가 없는

노드를 루트 노드(root node)라고 하고,

자식이 없는 노드를 리프 노드(leaf node)

또는 단말 노드라고 합니다.

 

 

 

 

강의 출처 : https://www.youtube.com/watch?v=PFc4g8mxOiI&list=PL4SIC1d_ab-aOxWPucn31NHkQvNPHK1D1&pp=iAQB

---