기타치는 개발자의 야매 가이드

트리의 모든 노드를 한번씩 방문하여 모든 정보에 대한 선형 순서를 만들어 내는 방법을 알아보자

트리, 이진트리에 대해서는 이전글을 참고자도록 하자.

2016/10/18 - [Yame Programmer/자료구조&알고리즘] - 야매 개발자 자료구조 가이드[트리(tree)]

이진트리나 이진트리의 순회방법을 난 이제 알았는데 컴공 학생들은 2학년때 배운단다... 부럽...

순회방법에는 3가지가 있다.

1. 전위 순회(Preorder Traversal)

2. 중위 순회(Inorder Traversal)

3. 후위 순회(Postorder Traversal)

1. 전위 순회(Preorder Traversal)

<전위 순회의 탐색 순서 : A B D E C F G>

전위 순회의 특징은 루트 노드를 가장 먼저 탐색 한다.

루트 노드 부터 시작해 왼쪽 하위트리를 탐색하고 왼쪽 트리의 탐색이 끝나면 오른쪽 하위 트리를 탐색하는 방식 입니다.

2. 중위 순회(Inorder Traversal)

<중위 순회 탐색 순서 : D B E A F C G>

중위 순회의 특징은 루트노드가 탐색 순서의 중앙에 위치 합니다.

왼쪽 하위트리 부터 시작해 루트를 거쳐 오른쪽 하위 트리를 탐색 합니다. 

3. 후위 순회(Postorder Traversal)

<후위 순회 탐색 순서 : D E B F G C A>

후위순위의 특징은 루트가 가장 마지막에 탐색 됩니다.

왼쪽 하위 트리에서 시작해 오른쪽 하위트리를 탐색하고 루트 노드를 탐색합니다.

구현된 코드를 참조하실분은

http://songeunjung92.tistory.com/29

http://marobiana.tistory.com/83

이분들의 포스팅을 참고하지면 좋을 것 같습니다.

<트리는 위와 같은 구조를 가지고 있다.>

부모자식관계 : B의 부모는 A , B의 자식은 D,E 

루트 : 트리구조에서 가장 위에 있는 노드, 부모가 없다.

노드 : 트리를 이루는 한 요소 (ex 위 그림의 A, B, C , D ....)

차수 : 어떤 노드가 가지고 있는 자식의 노드 개수를 말한다. 예를 들어 B노드의 차수는 2이다.

        (트리의 차수를 말할땐 가장 높은 차수를 말한다. 예를들어

         D노드에 자식이 하나 더 생긴다면 위 트리의 차수는 3이다)

레벨 : 트리를 이루는 각 층의 번호이다. 깊이 내려갈 수록 레벨이 높아진다. 

높이,깊이 : 루트 노드부터 가장 끝에 있는 노드 까지의 깊이(경로의 길이) 

               위 트리의 깊이는 3이다.

Left chaild-right Sibling 표현법

트리의 표현법이다. 아래의 그림처럼 한개의 노드에 자식과 형제의 포인터를 지니는 구조이다.

Child : 자식노드를 가르킨다

Sibling : 형제노드를 가르킨다

가장 위에 있는 노드부터 시작해 왼쪽에 있는 자식노드를 구하고 그 노드의 자식노드와 형제 노드를 구한다

이렇게 반복을 하면 모든 자식 노드를 찾을 수 있게 된다.

이진 트리 (Binary Tree)

최대 2개의 자식 노드를 가질 수 있는 트리이다.

한 노드당 자식을 1개만 가질 수도 있고 아무것도 없을수도 있고 2개를 가질수도 있다.

이진트리의 종류에는

완전 이진 트리(Complete Binary Tree)와 사향 이진 트리(Skewed Binary Tree), 포화 이진 트리(Full Binary Tree)가 있다.

<완전 이진트리(Complete Binary Tree)>

완전 이진트리는 어떤 노드 두개의 레벨차가 1이하 이며 왼쪽부터 오른쪽으로 채워지는 트리 이다.

만약 왼쪽에서 오른쪽으로 가다가 중간에 노드가 비어있다면 그건 완전 이진트리가 아니다.

예를들어 위의 그림에서 E노드 아래에 자식노드가 생성되면 완전 이진트리가 아니게 된다.

<사향 이진트리(Skewed Binary Tree)>

사향 이진트리는 루트노드를 제외한 모든 노드가 부모 노드의 왼쪽 자식 노드이거나 반대로 오른쪽 자식 노드인 것을 말한다. 즉 노드의 방향이 한쪽 방향으로만 치우쳐진 트리이며 다른말로 경사,편향 이진트리 라고 불리기도 한다.

<포화 이진트리(Full Binary Tree)>

포화 이진트리는 완전이진트리와는 다르게 최대한 노드가 가득차 있는 트리를 말한다. 가장 마지막 노드를 제외한 모든 노드가 자식노드를 2개씩 가지고 있다. 

(모든 포화 이진트리는 완전 이진트리 라고 부를수 있지만 그 반대는 성립하지 않는다.). 

이러한 뭔가 당연한것 같은(따로 공부하지 않아도 될것 같은) 트리구조를 왜 알아야 하는지 얼마 전까진 사실 잘 몰랐다. 

그러나 후에 포스팅할 트리의 순회구조와 그 다음 위상정렬(DFS 깊이 우선 탐색), 너비 우선탐색(BFS)를 거쳐

다익스트라 알고리즘과 같은 조금더 난이도 있는 알고리즘을 이해하기 위해선 이 트리구조에 대해서

기본적인 이해가 필요하기 떄문이라는걸 근 일주일간의 삽질 끝에 체감했다.

역시 기초가 중요하다.

참조: http://blog.eairship.kr/215