정처기 필기특강 - 트리운행법

출처: 유튜브 - 흥달쌤 - 정보처리 필기 특강 (전위순회 / 중위순회/ 후위순회)

---

# 트리운행법

- 트리운행법은 2과목에서 2~3문제 무조건 나오는 부분

트리운행법

• 전위 운행 Preorder: 부모부터 방문>왼쪽>오른쪽
• 중위 운행 Inorder: 왼쪽>부모>오른쪽
• 후위 운행 Postorder:왼쪽>오른쪽>부모

 

---

# 중위순회

<중위순회 문제풀이>

번호	문제	풀이
1		왼쪽을 다 끝내고나서 부모로 가기 D→B→A→E→C→F 왼쪽→부모→자식
2	다음 이진 트리의 노드를 중위 순회(inorder traversal)할 때, 4, 5, 6번째 방문 노드를 순서대로 바르게 나열한 것은?	F→D→G→B→A→E→C 정답 :  B,A,E
3	다음 이진트리를 중위 순회(inorder traversal)하는 경우 노드 방문 순서는?	4→2→5→1→6→3→7

---

# 전위순회

<전위순회 문제풀이>

전위순회: 부모먼저 방문

번호	문제	풀이
1	다음 트리를 전위 순회한 결과는?	A→B→D→E→C→F→G
2	다음 트리를 전위 순회(preorder traversal)한 결과는?	**잘나오는문제! 부모부터 방문 + 그다음 왼쪽자식 * 왼쪽아래 다끝내고 오른쪽으로! +→*→*→/→A→B→C→D→E
3	다음 트리를 전위 순회(Preorder Traversal)한 결과는?	A→B→D→C→E→F
4	다음 이진 트리의 노드를 전위 순회(preorder traversal)할 경우의 방문 순서는?	A→B→D→E→G→C→F→H

---

# 후위순회

<후위순회 문제풀이>

후위순회 : 왼쪽 →오른쪽→마지막에 부모 방문

번호	문제	풀이
1	다음 트리를 후위 순회(Post-order) 방법으로 운행한 결과는?	**이문제는 어려운 문제 (공무원) 왼쪽 다끝나고→오른쪽 다끝나고→부모를 가장 나중에 방문한다! I→E→J→F→C→G→K→L→H→D→B→A
2	다음 트리를 후위 순회(Postorder Traversal)한 결과는?	D→B→E→F→C→A
3	다음 그림과 같은 이진 트리를 후위 순회(postorder traversal) 한 결과는?	**잘나옴 A→B→/→C→*→D→*→E→+
4	다음 트리를 후위 순회(Post Traversal)할 경우 가장 먼저 탐색되는 것은?	가장 먼저 탐색 : D D→E→B→F→C→A
5	다음 이진 트리에 대하여 후위 순회를 하는 경우 다섯 번째 방문하는 노드는?	다섯 번째 방문: F D→G→E→B→F→C→A
6	<보기>의 이진트리(binary tree)를 후위순회(postorder traversing)한 결과는? (단, 루트노드(root node)는 F이다.)	E→C→K→A→H→B→G→D→F
7	다음 트리 구조에 대해 후위(Postorder) 순회로 처리한 결과는?	D→G→C→B→F→E→A