[알고리즘 과제] 이진 트리 순회 및 표기식(전위, 중위, 후위)

 

문제: 아래의 이진 트리(Binary Tree)를 전위, 중위, 후위 순회하시오.

 

1. 전위 순회(Pre-order Traversal)

ㄱ. 의사 코드(Pseudo Code)

① Parent 노드를 방문한다. (Start: Root 노드)
② 왼쪽 하위 트리를 방문한다.
③ 오른쪽 하위 트리를 방문한다. (End: 오른쪽 터미널 노드)

 

ㄴ. 전위 순회 결과

 

순회 순서: ① - ② - ③ - ④ - ⑤ - ⑥ - ⑦

전위 표기식: + * 1 2 – 7 8

 

2.  중위 순회(In-order Traversal)

ㄱ. 의사 코드(Pseudo Code)

① 왼쪽 하위 트리를 방문한다. (Start: 왼쪽 터미널 노드)
② Parent 노드를 방문한다.
③ 오른쪽 하위 트리를 방문한다. (End: 오른쪽 터미널 노드)

 

ㄴ. 중위 순회 결과

순회 순서: ① - ② - ③ - ④ - ⑤ - ⑥ - ⑦

중위 표기식: (1 * 2) + (7 – 8)

 

3. 후위 순회(Post-order Traversal)

ㄱ. 의사 코드(Pseudo Code)

① 왼쪽 하위 트리를 방문한다. (Start: 왼쪽 터미널 노드)
② 오른쪽 하위 트리를 방문한다.
③ Parent 노드를 방문한다. (End: Root 노드)

 

ㄴ. 후위 순회 결과

 

 

순회 순서: ① - ② - ③ - ④ - ⑤ - ⑥ - ⑦

후위 표기식: 1 2 * 7 8 - +