트리 순회(Tree Traversal)

특정 목적을 위해 트리의 모든 노드를 한 번씩 방문하는 것

• ex. 1에서 10까지 정수로 구성된 트리에서 3이라는 숫자를 찾기 위해 모든 노드를 방문하는 것.
• 트리 구조는 계층적 구조이므로, 모든 노드를 순회하는 방법엔 크게 3가지가 있다.
  • 전위 순회, 중위 순회, 후위 순회

    순회 방식과는 논외로, 트리 구조에서 노드를 순차적으로 조회할 때의 순서는 항상 왼쪽부터 오른쪽이다.

🌲 트리 순회 방법

전위 순회 (preorder traverse)

• 깊이 우선 순회(DFT, Depth-First Traversal)
• 트리를 복사하거나 전위 표기법을 구할 때 주로 사용한다.
• 순회 방법
  1. Root 노드를 방문한다.
  2. 왼쪽 서브 트리를 순차적으로 둘러본 뒤(=전위 순회한 뒤)
  3. 오른쪽 서브 트리를 전위 순회한다.
• 즉, 부모 노드가 제일 먼저 방문되는 순회 방식이다.
  
• 전위 순회 결과 : A→B→D→E→C→F→G

중위 순회(Inorder Traversal)

• 왼쪽 오른쪽 대칭 순서로 순회를 하기때문에 대칭 순회(symmetric traversal)라고도 한다.
• 이진 탐색트리(BST)에서 오름차순 또는 내림차순으로 값을 가져올 때 사용한다.
• 순회 방법
  1. 루트를 가운데에 두고 순회한다.
  2. 제일 왼쪽 끝에 있는 노드부터 순회하기 시작하여, 루트를 기준으로 왼쪽에 있는 노드의 순회가 끝나면 루트를 거쳐
  3. 오른쪽에 있는 노드로 이동하여 마저 탐색한다.
     
• 중위 순회 결과 : D→B→E→A→F→C→G

후위 순회 (Postorder Traversal)

• 트리를 삭제하는데 주로 사용된다.
  • 부모 노드를 삭제하기 전, 자식 노드를 삭제하는 순으로 삭제해야 하기 때문에
• 순회 방법
  루트를 가장 마지막에 순회한다.
  1. 제일 왼쪽 끝에 있는 노드부터 순회하기 시작하여,
  2. 루트를 거치지 않고 오른쪽으로 이동해 순회한 뒤,
  3. 제일 마지막에 루트를 방문한다.
     
• 후위 순회 결과 : D→E→B→F→G→C→A

---