후위 순회

안녕하세요! 취업준비생의 알고리즘 공부입니다.😃

저의 공부가 많은 사람들에게 도움이 되었으면 좋겠습니다.

부족한 점에 대한 따끔한 지적도 환영입니다!

겸손한 자세로 배우도록 하겠습니다. 🙇‍♀️

백준1991번

위 링크를 클릭하면 문제를 볼 수 있습니다.

📍 기본 원칙

💘 순회 중요도

전위 순회는 뿌리 > 왼쪽자식 > 오른쪽 자식
중위 순회는 왼쪽 자식 > 뿌리 > 오른쪽 자식
후위 순회는 왼쪽 자식 > 오른쪽 자식 >뿌리 순으로 중요도를 나타냅니다.

• 📌 원칙1
  처음 노드의 시작은 최상위에 있는 노드입니다.

• 📌 원칙2
  현재 노드는 뿌리 노드에 해당합니다.

• 📌 원칙3
  현재 노드에서 중요한 노드로 이동한다.

• 📌 원칙4
  현재 노드에서 더 이상 중요한 노드가 없을 시 탐색을 한다.

• 📌 원칙5
  탐색한 노드는 탐색하지 않는다.

• 📌 원칙6
  더 이상의 탐색 노드가 존재하지 않으면 부모 노드로 돌아간다.

🏞 그림을 통해 알아보자!

후위 순회

왼쪽 자식 > 오른쪽 자식 >뿌리

🌟 시작 노드 A

• 현재 노드 A
  -> 현재 노드에서 가장 중요한 노드 = 왼쪽 자식 = B 로 이동합니다.
• 현재 노드 B
  ->현재 노드에서 가장 중요한 노드 = 왼쪽 자식 = D 로 이동합니다.
• 현재 노드 D
  -> 더 이상 탐색 노드가 없기 때문에 탐색한다. D
  -> 더 이상 탐색 노드가 없기 이전 노드 = B 로 돌아갑니다.
• 현재 노드 B
  -> 더 이상 탐색 노드가 없기 때문에 탐색한다. B
  -> 더 이상 탐색 노드가 없기 이전 노드 = A 로 돌아갑니다.
• 현재 노드 A
  -> 현재 노드에서 왼쪽 자식은 탐색했고, 다음으로 중요한 노드 = 오른쪽 자식 =C 이동
• 현재 노드 C
  -> 현재 노드에서 중요한 노드 = 왼쪽 자식 = E 로 이동합니다.
• 현재 노드 E
  -> 더 이상 탐색 노드가 없기 때문에 탐색한다. E
  -> 더 이상 탐색 노드가 없기 이전 노드 = C 로 돌아갑니다.
• 현재 노드 C
  -> 현재 노드에서 탐색한 노드를 제외한 가장 중요한 노드 = 오른쪽 자식 = F 로 이동합니다.
• 현재 노드 F
  -> 현재 노드에서 탐색한 노드를 제외한 가장 중요한 노드 = 오른쪽 자식 = G 로 이동합니다.
• 현재 노드 G
  -> 더 이상 탐색 노드가 없기 때문에 탐색한다. G
  -> 더 이상 탐색 노드가 없기 이전 노드 = F 로 돌아갑니다.
• 현재 노드 F
  -> 뿌리를 제외하고 중요 노드를 모두 탐색했기 때문에 현재 노드 = 뿌리 를 탐색합니다. F
  -> 더 이상 탐색 노드가 없기 이전 노드 = C 로 돌아갑니다.
• 현재 노드 C
  -> 뿌리를 제외하고 중요 노드를 모두 탐색했기 때문에 현재 노드 = 뿌리 를 탐색합니다. C
  -> 더 이상 탐색 노드가 없기 이전 노드 = A 로 돌아갑니다.
• 현재 노드 A
  -> 뿌리를 제외하고 중요 노드를 모두 탐색했기 때문에 현재 노드 = 뿌리 를 탐색합니다. A

📝 정리

🔍 중위 순회 탐색 순서

D -> B -> E -> G -> F -> C -> A