[2019.04.03] 자료구조-Tree

# Tree

트리는 부모와 자식들 간의 관계를 가지는 노드들의 연결구조를 말한다.

트리 중 대표적인 '이진트리'

위 그림 중 동그라미는 각 노드이고, 노드들간의 선은 관계선이다. 부모는 여러 자식을 가질 수 있고, 자식은 하나의 부모만을 가지는 계층 구조이다.

대표적으로 이진트리가 있다. 이진트리란, 부모노드가 두개 이하의 자식 노드만을 갖는 트리를 말한다. 

• 전 이진 트리 : 위 그림과 같이 순서 상관없이 구조를 이루는 트리
• 완전 이진 트리 : 자식노드가 왼쪽부터 차례대로 노드가 채워진 구조를 이루는 트리
• 포화 이진 트리 : 마지막 레벨의 자식노드들이 하나도 자식 노드를 가지고 있지 않고, 그 외 노드들이 전부 두개의 자식노드를 가지고 있는 트리

트리의 순위 방법

전위순회 : root노드부터 시작하여, 왼쪽으로 노드를 계속 검색한다. 왼쪽 노드가 더 이상 없으면, 오른쪽 노드로 넘어가는 방식이다. 이미 검색한 노드는 다시 검사하지 않고 넘어간다. 

중위 순회 : 제일 왼쪽 노드부터 탐색을 하는 방식. 왼쪽 자식 노드가 탐색되면 부모노드가 탐색되고, 이후에 오른쪽 노드를 탐색한다. 이 방식을 반복하여, 제일 왼쪽에 있는 노드부터 서서히 오른쪽 노드로 탐색을 한다.

후위 순회 : 제일 왼쪽 노드를 탐색하고 오른쪽 노드 탐색, 그리고 부모노드를 탐색한다. 이 방식을 사용하여 서서히 위로 올라가는 탐색을 한다.

 

수도코드