1991 - 트리 순회
📚 1991 - 트리 순회
풀이
문제는 전형적인 트리 순회 알고리즘 문제이다.
전위 순회(preorder traversal
), 중위 순회(inorder traversal
), 후위 순회(postorder traversal
)
만약, 전위, 중위, 후위에 대해 모른다면
전위, 중위, 후위 설명
이를 참고하면 될 것 같다.
Pre-order(전위순회)
1) 루트노드 방문
2) 왼쪽 자식 노드를 루트로 하는 서브 트리를 프리오더(재귀)
3) 오른쪽 자식 노드를 루트로 하는 서브 트리를 프리오더(재귀)In-order(중위순회)
1) 왼쪽 자식 노드를 루트로 하는 서브 트리를 인오더(재귀)
2) 루트노드 방문
3) 오른쪽 자식 노드를 루트로 하는 서브 트리를 인오더(재귀)Post-order(후위순회)
1) 왼쪽 자식 노드를 루트로 하는 서브 트리를 포스트오더(재귀)
2) 오른쪽 자식 노드를 루트로 하는 서브 트리를 포스트오더(재귀)
3) 루트노드 방문
소스
# 트리 순회
import sys
n = int(sys.stdin.readline())
# 문자열 배열일 때는 딕셔너리 사용하기
tree = {}
def pre_order(root):
if root != ".":
print(root, end="")
pre_order(tree[root][0])
pre_order(tree[root][1])
def mid_order(root):
if root != ".":
mid_order(tree[root][0])
print(root, end="")
mid_order(tree[root][1])
def post_order(root):
if root != ".":
post_order(tree[root][0])
post_order(tree[root][1])
print(root, end="")
for _ in range(n):
node, left, right = sys.stdin.readline().split()
tree[node] = [left, right]
pre_order('A')
print()
mid_order('A')
print()
post_order('A')
print()
채점 결과
Author And Source
이 문제에 관하여(1991 - 트리 순회), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@chang626/1991-트리-순회저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)