트리의 용어, 종류, 트리 순회

 

 

트리 용어설명

 

●트리의 용어

 

-트리 : 나무형태의 자료구조, 부모-자식의 관계로 이루어져있다.

-루트(root) : 최상위 부모

 

-이진트리(binary tree) : 부모가 자식을 최대 2개 가지는 트리구조

cf)삼진트리 : 부모가 자식을 최대 3개 가진다.

 

-서브트리 : 자식이 부모가 되어 다시 자식을 가지게 되면 서브트리가 형성되었다 라고 말한다.

위의 그림을 보면 D, E 노드는 B의 자식이다. 그런데 D는 다시 H, I 자식이 있으니 서브트리가 형성되었다.

 

-리프(leaf) : 더이상 자식이 없는 노드를 말한다.

위의 그림을 보면 H, I, J, F, G는 그 밑에 자식이 없으니 리프이다.

나무를 거꾸로 만들어 놓았다고 생각하면 용어 이해가 쉽다.

나무의 맨 위의 자리에 뿌리가 있고 끝에는 잎사귀가 있다. 그래서 용어 그대로 leaf 잎사귀이다.

다른말로 말단, 단말 노드라고도 부른다.

 

-간선(edge) : 노드에서 노드를 연결할 때 그 길을 간선이라고 한다.

-레벨 : 루트에서 거친 간선의 갯수로 레벨을 판별한다.

그림을 보면 루트에서 C로 갈 때 간선 1개를 거쳤다. 1개 거쳤으므로 레벨 1이라고 부른다.

F는 루트에서 C를 거쳐서 간선 2개를 지났다. 그래서 레벨 2이다.

 

-트리의 최대 높이 : 레벨의 최대 차수

그림에서 최대 레벨은 3단계이다. 그래서 트리의 최대 높이도 3이다.

 

 

---

 

 

●이진트리의 종류

 

-완전 이진 트리(complete binary tree)

-정 이진 트리(full binary tree)

-포화 이진 트리(perfect binary tree)

 

 

 

완전이진트리

 

-완전 이진 트리(complete binary tree) : 두가지 조건이 필요하다.

조건1. 말단을 제외하고 모든 노드가 전부 채워져 있는 상태. 즉 말단을 제외하고 나머지 노드들이 모두 2개의 자식노드를 가지고 있어야한다,

조건2. 그리고 마지막 레벨은 왼쪽부터 차례대로 채워져야 된다.

 

만약 E노드가 존재하지 않는다면 B노드는 D노드 1개밖에 가지지 않기 때문에 조건1에 의해 완전이진트리가 될 수 없다.

F노드는 L노드 하나밖에 없지만 자식이 말단노드이므로 완전이진트리가 될 수 있다.

그리고 만약 J노드가 존재하지 않는다면 말단노드들이 왼쪽부터 차례대로 채워지지 않았기 때문에 조건2에 의해 완전이진트리가 될 수 없다.

 

 

 

정 이진 트리

 

-정 이진 트리(full binary tree) : 각 노드가 모두 0개 또는 2개의 자식이 있어야 된다. 다시 말해서 자식 노드가 1개일 때는 불가능하다.

예를 들어 위 그림에서 6번노드가 사라진다면 5번노드는 7번노드 한개만 가지게 되므로 정 이진 트리가 되지 못한다.

 

 

 

포화 이진 트리

 

-포화 이진 트리(perfect binary tree) : 모든 리프의 레벨이 같고 모든 노드들이 채워져 있어야 된다.

즉 완벽한 피라미드 형태로 이루어져 있어야 한다.

쉽게 생각해서 전부 채워져 있으면 포화이진트리이다.

위 그림에서 만약 노드 한개라도 빠지게 되면 포화이진트리가 되지 못한다.

 

포화이진트리는 완전이진트리도 맞다.

완전이진트리는 말단을 제외하고 모든 노드들이 채워져 있다는 조건이 있는데 포화이진트리는 말단까지 포함해서 모든 노드들이 채워져 있기 때문이다.

포화이진트리 ⊂ 완전이진트리

 

 

---

 

 

-순회 : 모든 노드들을 빠짐없이 방문하는 것

 

●순회하는 방식 : 부모를 언제 방문하냐에 따라

-중위 순회 : 왼쪽 자식 -> 부모 -> 오른쪽 자식

-전위 순회 : 부모 -> 왼쪽 자식 -> 오른쪽 자식

-후위 순회 : 왼쪽 자식 -> 오른쪽 자식 -> 부모

 

 

 

 

이진트리

 

-중위 순회 : 왼쪽 자식을 다 방문하고 부모를 들리고 오른쪽 자식을 전부 방문

B -> A -> C 순으로 방문을 하려고 한다.

그런데 B가 sub tree를 형성하고 있다.

그래서 B를 방문하기 전에 D -> B -> E 순으로 방문한다.

그런데 여기서 또 D도 sub tree를 형성하고 있다.

 

그래서 결과적으로 H -> D -> I -> B -> J -> E -> A -> F -> C -> G 순서로 방문하게 된다.

 

 

 

이진트리

 

-전위 순회 : 부모먼저 방문 -> 왼쪽자식  방문 -> 오른쪽자식 방문

A -> B -> C 순으로 방문을 하려고 한다.

아까와 마찬가지로 서브트리를 형성하고 있기 때문에

 

결과적으로 A -> B -> D -> H -> I -> E -> J -> C -> F -> G 순서가 된다.

 

 

 

이진트리

 

-후위 순회 : 왼쪽 자식 -> 오른쪽 자식 -> 마지막에 부모 방문

B -> C -> A 순으로 방문한다.

아까와 마찬가지로 서브트리를 형성하기 때문에

 

결과적으로 H -> I -> D -> J -> E -> B -> F -> G -> C -> A 순으로 방문한다.