문제 바로가기
문제:
이진 트리를 입력받아 전위 순회(preorder traversal), 중위 순회(inorder traversal), 후위 순회(postorder traversal)한 결과를 출력하는 프로그램을 작성하시오.
예를 들어 위와 같은 이진 트리가 입력되면, 전위 순회한 결과 : ABDCEFG // (루트) (왼쪽 자식) (오른쪽 자식) 중위 순회한 결과 : DBAECFG // (왼쪽 자식) (루트) (오른쪽 자식) 후위 순회한 결과 : DBEGFCA // (왼쪽 자식) (오른쪽 자식) (루트)
입력:
첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파벳 대문자로 매겨지며, 항상 A가 루트 노드가 된다. 자식 노드가 없는 경우에는 .으로 표현한다.
출력:
첫째 줄에 전위 순회, 둘째 줄에 중위 순회, 셋째 줄에 후위 순회한 결과를 출력한다. 각 줄에 N개의 알파벳을 공백 없이 출력하면 된다.
풀이 :
재 어려운 재귀,, 재귀풀이에 자신감을 얻을때까지 재귀를 풀어볼 생각이다.
https://www.youtube.com/watch?v=uSSC0aKXbWQ
이 문제를 보고 나도 생각을 좀 바꿔서 해야겠다고 생각했다. 평소 재귀문제를 풀때 재귀를 부르고 나서 상황도 이해하려고 했지만. 그것은 프로그래밍에게만 맡긴다라고 생각하고 풀어본다.
import sys
sys.stdin = open('/Users/song/Desktop/Python/Python/h.txt', 'r')
N = int(sys.stdin.readline())
tree = {}
for i in range(N):
root, left, right = sys.stdin.readline().strip().split()
tree[root] = [left,right]
def solution(root):
if root != ".":
print(root, end="")
solution(tree[root][0])
solution(tree[root][1])
def solution2(root):
if root != ".":
solution2(tree[root][0])
print(root, end="")
solution2(tree[root][1])
def solution3(root):
if root != ".":
solution3(tree[root][0])
solution3(tree[root][1])
print(root, end="")
solution("A")
print()
solution2("A")
print()
solution3("A")
그러면 이런식인데 하나를 보자면
def solution(root):
if root != ".":
print(root, end="")
solution(tree[root][0])
solution(tree[root][1])
Root가 . 이 아니면
1. 루트를 프린트하고
2. 왼쪽루트를 탐색하고
3. 오른쪽을 탐색한다 .
라고 이해 하면 될것 같다.
댓글