[Data Structure] 이진트리 순회 (깊이우선탐색) : 전위순회, 중위순회, 후위순회 | Tree traversal : preorder, inorder, postorder

Tree는 부모노드와 왼쪽 자식노드, 오른쪽 자식도드가 있는 구조다. 이렇게 하나가 기본 단위다.

이진트리를 순회하는 방법은 3가지가 있다.

전위순회(pre-order traversal), 중위순회(in-order traversal) 그리고 후위순회(post-order traversal)

 

 

아래 이진트리로 연습을 해보겠다. 노드는 1 ~ 7까지다. Root node는 1

전위순회를 먼저 알아보겠다.

전위순회로 돌았을 때 Result는 위와 같이 나온다.

 

 

어떻게 1 2 4 5 3 6 7 이 나오는 것일까? 그 과정을 정리해봤다.

012345678910111213

 

슬라이드를 천천히 보면서 설명을 읽어본다면 이해할 수 있을것이다. 트리는 stack과 재귀를 이용해서 탐색한다는것을 이해했다.

 

 

 

 

 

중위순회(in-order traversal)

 

 

 

후위순회(post-order traversal)

 

 

원리만 안다면 쉬운데 ^_^  이해하는데 시간이 조금 걸렸다. 그래도 이렇게 정리하고 보니 

절대 까먹지 않겠지? ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ

와 진짜 정리하는데 너무 오래걸린다. 개발 블로그 정말 어렵다.