1991번: 트리 순회 (트리, 재귀) - Fastcampus

www.acmicpc.net/problem/1991

1991번: 트리 순회

# 전위 순회 (parent, 왼쪽, 오른쪽)
def pre_order(parent):
    lc, rc = graph[parent]

    global visited
    visited += parent
    if lc != ".":
        pre_order(lc)
    if rc != ".":
        pre_order(rc)


# 중위 순회 (왼쪽, parent, 오른쪽)
def in_order(parent):
    lc, rc = graph[parent]

    if lc != ".":
        in_order(lc)
    global visited
    visited += parent
    if rc != ".":
        in_order(rc)


# 후위 순회 (왼쪽, 오른쪽, parent)
def post_order(parent):
    lc, rc = graph[parent]

    if lc != ".":
        post_order(lc)
    if rc != ".":
        post_order(rc)
    global visited
    visited += parent


N = int(input())
graph = {}
for _ in range(N):
    p, lc, rc = input().split()
    graph[p] = (lc, rc)  # {'A': ('B','C'), 'B': ('D','.'), 'C': ('.','.') }


visited = ""
pre_order("A")
print(visited)

visited = ""
in_order("A")
print(visited)

visited = ""
post_order("A")
print(visited)

 

다른 풀이: 연결정보를 (노드 클래스)로 표현

 

class Node:
    def __init__(self, p, lc, rc):
        self.data = p
        self.lc = lc
        self.rc = rc


# 전위 순회 (parent, 왼쪽, 오른쪽)
def pre_order(parent):
    node = graph[parent]

    global visited
    visited += node.data
    if node.lc != ".":
        pre_order(node.lc)
    if node.rc != ".":
        pre_order(node.rc)


# 중위 순회 (왼쪽, parent, 오른쪽)
def in_order(parent):
    node = graph[parent]

    if node.lc != ".":
        in_order(node.lc)
    global visited
    visited += node.data
    if node.rc != ".":
        in_order(node.rc)


# 후위 순회 (왼쪽, 오른쪽, parent)
def post_order(parent):
    node = graph[parent]

    if node.lc != ".":
        post_order(node.lc)
    if node.rc != ".":
        post_order(node.rc)
    global visited
    visited += node.data


N = int(input())
graph = {}
for _ in range(N):
    p, lc, rc = input().split()
    # {'A': Node('A','B','C'), 'B': Node('B','D','.'), 'C': Node('C','.','.') }
    graph[p] = Node(p, lc, rc)


visited = ""
pre_order("A")
print(visited)

visited = ""
in_order("A")
print(visited)

visited = ""
post_order("A")
print(visited)