트리(Tree)

트리란?

배열, 연결리스트, 스택, 큐는 데이터가 한 선으로 연결된 것 같은 형태라 해서 선형 구조라고 한다. 트리는 부모와 자식을 가지고 있는 계층형 구조다. 마치 가계도같은 모양새를 지닌다. 맨 위에 있는 노드를 루트(root) 라고 부르고, 맨 아래 있는 노드들을 리프(leaf) 라고 부른다. 이처럼 노드들이 연결 관계를 가지고 있기 때문에 연결리스트로 구현하면 효과적이다.

 

이진 트리

부모 노드들이 최대 2개의 자식만을 가지는 트리를 이진 트리(binary tree) 라고 부른다. 3개 이상은 Tenary Tree 라고 부른다. 이진트리는 구현하기도 쉬워서 다양한 곳에서 정말 유용하게 사용되니 잘 알아두면 좋다.

 

완전 이진 트리

마지막 레벨을 제외하고 모두 채워져 있으며, 마지막 레벨은 왼쪽부터 채워져 있는 트리를 완전 이진 트리(complete binary tree) 라고 한다.

 

정 이진 트리(Full Binary Tree)

자식을 가지려면 두개를 가지고, 아니라면 아예 안 가지는 트리다.

 

포화 이진 트리(Perfect Binary Tree)

레벨도 맞고 모두 두 개의 자식을 가진 트리다. 레벨이 n 이라면 트리 노드의 개수는 루트 노드만 있는 1레벨을 제외하고 전부 2의 n승개니 아래와 같다.

$$ 2^{n}-1 $$

 

이진 트리 순회

이진 트리에서 데이터를 탐색하는 방법이다. 기본적으로 Left -> Right 순으로 탐색하고, 루트 노드를 제일 먼저 보는지, 중간에 보는지, 제일 나중에 보는지에 따라 다르다. 루트 노드는 검색하는 순간의 서브트리의 루트, 즉 자기 자신으로 본다.

 

중위 순회(Inorder)

Left -> Root - Right 를 반복

 

전위 순회(Preorder)

Root -> Left -> Right 를 반복

 

후위 순회(Postorder)

Left -> Right -> Root 를 반복