046 이진 트리의 운행법

 

• 전위 ( Preorder ) 운행 : Root → Left → Right 순으로 운행함 A, B, C
• 중위 ( Inorder ) 운행 : Left → Root → Right 순으로 운행함 B, A, C
• 후위 ( Postorder ) 운행 : Left → Right → Root 순으로 운행함 B, C, A

---

ex. 다음 트리를 Inorder, Preorder, Postorder 방법으로 운행했을 때 각 노드를 방문한 순서는?

< Preorder 운행법의 방문 순서 >

서브 트리를 하나의 노드로 생각할 수 있도록 다음 그임과 같이 서브 트리 단위로 묶는다. Preorder, Inorder, Postorder 모두 공통으로 사용한다.

① Preorder는 Root → Left → Right이므로 A13이 된다.

② 1은 B2E이므로 AB2E3이 된다.

③ 2는 DHI이므로 ABDHIE3이 된다.

④ 3은 CFG이므로 ABDHIECFG가 된다.

∴ 방문 순서 : ABDHIECFG

---

< Inorder 운행법의 방문 순서 >

① Inorder는 Left → Root → Right이므로 1A3이 된다.

② 1은 2BE이므로 2BEA3이 된다.

③ 2는 HDI이므로 HDIBEA3이 된다.

④ 3은 FCG이므로 HDIBEAFCG가 된다.

∴ 방문 순서 : HDIBEAFCG

---

< Postorder 운행법의 방문 순서 >

① Postorder는 Left → Right → Root이므로 1A3이 된다.

② 1은 2EB이므로 2EB3A가 된다.

③ 2는 HID이므로 HIDEB3A가 된다.

④ 3은 FGC이므로 HIDEBFGCA가 된다.

∴ 방문 순서 : HIDEBFGCA

---

길벗알앤디 (강윤석, 김용갑, 김우경), 정보처리 산업기사 필기 1권 핵심요약, 길벗(2019), p 50.