이진 트리(binary tree) 중에서 전위 순회(preorder t… | [7급 국가직 자료구조론] 25년 1회차 기출문제 상세 페이지

전위 순회와 중위 순회 결과가 같은 것은 모든 노드가 오른쪽 자식만 갖는 오른쪽 사향 트리(1 → 2 → 3 → 4 → 5)이다.
전위는 루트 → 왼쪽 → 오른쪽, 중위는 왼쪽 → 루트 → 오른쪽 순서이므로, 왼쪽 서브트리가 하나도 없으면 두 순회 모두 루트 → 오른쪽 순서가 되어 결과가 같다. 이 트리는 두 순회 모두 1, 2, 3, 4, 5이다.
5를 루트로 왼쪽 자식만 이어진 왼쪽 사향 트리: 전위는 5, 4, 3, 2, 1, 중위는 1, 2, 3, 4, 5로 정반대이다.
2를 루트로 왼쪽에 1, 오른쪽에 3 → 4 → 5가 이어진 트리: 전위는 2, 1, 3, 4, 5, 중위는 1, 2, 3, 4, 5로 앞부분이 다르다.
3을 루트로 왼쪽에 2 → 1, 오른쪽에 4 → 5가 있는 트리: 전위는 3, 2, 1, 4, 5, 중위는 1, 2, 3, 4, 5로 다르다.