[1128] 자바 - Tree traversal(트리 순회)

#트리 순회

1.  전위 순회 (preorder traverse)

• 가장 먼저 방문하는 노드인 루트를 기준으로 왼쪽의 노드들을 차례대로 둘러본 뒤, 왼쪽의 노드 탐색이 끝나면 오른쪽 노드를 탐색한다.
• 부모 노드가 제일 먼저 방문되는 순회방식.
• 주로 트리를 복사할 때 사용한다.
• 위 그래프를 전위 순회한다면 순서는 다음과 같다.
  A →  G → H → B → I → J → D → K → M → F → N → O

 

2.  중위 순회 (inorder traverse)

• 루트를 가운데에 두고 순회한다. 제일 왼쪽 끝에 있는 노드부터 순회하기 시작하여, 루트를 기준으로 왼쪽에서 오른쪽 방향으로 노드를 탐색한다.
• 부모 노드는 서브 트리의 방문 중간에 방문되는 순회방식.
• 주로 이진 탐색 트리의 오름차순으로 값을 가져올 때 쓰인다.
• 위 그래프를 중위 순회한다면 순서는 다음과 같다.
  G → A → H → I → G → J → K → D → M → N → F → O

 

3.  후위 순회 (postorder traverse)

• 루트를 가장 마지막에 순회. 왼쪽 끝에 있는 노드부터 순회하기 시작해, 루트를 거치지 않고 오른쪽으로 이동하며 순회한 뒤 제일 마지막에 루트를 방문.
• 트리를 삭제할 때 사용 (자식 노드의 삭제 뒤에 상위 노드의 삭제가 가능함)
• 위 그래프를 후위 순회한다면 순서는 다음과 같다.
  G → H → A → I → J  → B → K → M → D → N → O → F