[자료구조] 트리

오늘은 트리에 대해 배웠던 내용들을 정리해보려고 한다.

 

트리란?

트리는 이름처럼 나무랑 비슷하게 생긴 구조이다.

쉽게 예시를 들어보면 어느 조직의 조직도처럼 되어있다고 생각하면 편하다.

 

위 그림은 완전이진트리이다. 위 그림을 바탕으로 기본 용어들을 살펴보자

 

Root Node : 부모가 없는 노드를 의미한다. 즉 맨 위에 위치한 노드를 의미한다 (그림에서는 A)

트리에는 하나밖에 없다.

 

Leaf Node : 자식이 없는 노드로 트리 맨 하단에 위치한 노드를 의미한다. (그림에서는 D ,E ,C)

 

edge / link : 각 노드를 잇는 선을 의미한다.

 

Parent Node : 각 서브트리에서 부모 역할(상단) 에 있는 노드를 의미한다 B D E 트리를 보면 여기서는 B가 부모노드이다.

 

Child Node : 각 서브트리에서 부모 아래에 있는 노드를 의미한다. B D E 트리에서는 D E 가 자식노드이다.

 

Sibling Node : 각 서브트리에서 같은 부모 아래에 있는 노드를 의미한다. D E는 서로 형제노드이다.

 

...

 

이진트리란?

트리에는 여러 종류가 있지만 그 중 이진트리에 대해서 알아보자.

이진트리는 한개의 노드에 2개의 자식노드씩을 가지는 트리를 의미한다. 즉 위에 첨부된 그림 같은 구조이다.

 

이진트리는 또 완전 이진트리와 포화이진트리로 나뉘는데, 위의 그림이 완전 이진트리이다.

완전이진트리는 그림처럼 왼쪽부터 노드가 채워진 트리인데, C 노드의 자식노드가 없는 것 처럼 좀 부족해 보인다.

반대로 포화이진트리는 C 노드의 자식노드도 다 채워져 아래와 같은 구조를 가지면 포화이진트리이다.

포화이진트리

 

이진트리 순회?

이진트리의 각 노드를 순회하는 방법에는 전위순회 중위순회 후위순회가 있다.

 

전위 순회 : Root 에서 시작하여 왼쪽 하위 트리를 먼저 방문하고 오른쪽 하위트리를 방문한다.

A -> B -> D -> E -> C -> F -> G

 

중위 순회 : 왼쪽의 하위 트리부터 시작하여 Root 노드를 방문한뒤 오른쪽 하위트리를 방문한다.

D -> B -> E -> A -> F -> E -> G

 

후위 순회 : 전위 순회와 반대로 하위부터 상단까지 방문하는 순회방식이다.

C -> D -> B -> F -> G -> E -> A