[data structure] 이진 트리 순회(전휘, 중위, 후위 탐색)

모든 트리 순회의 기준은 부모 노드로 한다.

 

탐색 방법

전위 순회(preorder traversal) : 부모노드 -> 왼쪽 자식 노드 -> 오른쪽 자식 노드 순서로 루트 노드 부터 시작한다.

 

중위 순회(inorder traversal) : 왼쪽 자식 노드 -> 부모노드 -> 오른쪽 자식 노드 순서로 맨 왼쪽 노드를 방문하고 부모노드를 방문한다.

 

후위 순회(postorder traversal) : 왼쪽 자식 노드 -> 오른쪽 자식 노드 -> 부모노드 순서로 마지막 래벨의 노드들 부터 방문한다.

 

예시

이진트리

위 사진에서 전위, 후위, 중위 탐색방법

• 전위 순회한 결과 : A -> B -> D -> C -> E -> F -> G
• 중위 순회한 결과 : D -> B -> A -> E -> C -> F -> G
• 후위 순회한 결과 : D -> B -> E -> G -> F -> C -> A