어제 배운 [백준 1991, 이진 트리 순회] 문제 풀기

트리 순회 

 

문제

이진 트리를 입력받아 전위 순회(preorder traversal), 중위 순회(inorder traversal), 후위 순회(postorder traversal)한 결과를 출력하는 프로그램을 작성하시오.

예를 들어 위와 같은 이진 트리가 입력되면,

• 전위 순회한 결과 : ABDCEFG // (루트) (왼쪽 자식) (오른쪽 자식)
• 중위 순회한 결과 : DBAECFG // (왼쪽 자식) (루트) (오른쪽 자식)
• 후위 순회한 결과 : DBEGFCA // (왼쪽 자식) (오른쪽 자식) (루트)

가 된다.

입력

첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파벳 대문자로 매겨지며, 항상 A가 루트 노드가 된다. 자식 노드가 없는 경우에는 .으로 표현한다.

출력

첫째 줄에 전위 순회, 둘째 줄에 중위 순회, 셋째 줄에 후위 순회한 결과를 출력한다. 각 줄에 N개의 알파벳을 공백 없이 출력하면 된다.

 

---

 

입력은 되지만 출력이 안되는 내 불쌍한 코드...

# input 잘 모르겠어서 겁색 이런게 있어야 한다고 함
import sys

# 딕셔너리에 담기
def make_tree(edges):
    tree = {}
    for node, left, right in edges:
        tree[node] = (left, right)
    return tree


def preorder(tree, node):
    # 만약 노드가 없거나 자식이 없으면
    if node == '.':
        # 빈 문자열 반환
        return ''
    # 트리 딕셔너리에서 자식 노드를 찾고 없으면 . 반환
    left, right = tree.get(node, ('.', '.'))
    # 루트 방문 > 왼쪽 순회 > 오른쪽 순회
    return node + preorder(tree, left) + preorder(tree, right)

def inorder(tree, node):
    if node == '.':
        return ''
    left, right = tree.get(node, ('.', '.'))
    return inorder(tree, left) + node + inorder(tree, right)

def postorder(tree, node):
    if node == '.':
        return ''
    left, right = tree.get(node, ('.', '.'))
    return postorder(tree, left) + postorder(tree, right) + node

# sys.stdin.read() 구글링.. 표준 입력에서 모든 데이터를 읽어오는 sys 모듈에 포함된 함수라고 함
# 노드의 수랑 엣지를 나누기 위해 splitlines() 사용
input = sys.stdin.read().strip().splitlines()

N = int(input[0]) # 노드 수: 인풋의 첫번째 줄 (스플릿라인 인덱스 첫번째 값)
edges = [line.split() for line in input[1:N + 1]] # 인풋의 두번째 인덱스값부터 끝까지

# 트리 생성
tree = make_tree(edges)

# 루트 노드 고정
root = 'A'

# 순회 결과 출력
print(preorder(tree, root))
print(inorder(tree, root))
print(postorder(tree, root))

 

시간이 다 된 관계로... 찜찜하게 마무리 한 채.. 다시 스쿼드로.. 출발..

 우재튜터님한테 배워왔다! 이해가 너무 잘 됨😊

 

이제 혼자 풀어봐야 한다. 

• N: 우리가 입력받을 노드 수 → 숫자니까 int(input()) 으로 받고
• 우리는 저 이진트리를 딕셔너리에 넣어줄거기 때문에 bt = {} 빈 이진트리 딕셔너리 하나를 만들어준다. 

N = int(input())
bt = {}

 

이제 input으로 받은 값을 쪼개서 넣을건데, 우리가 입력받을 예시 입력값을 예로 들면

7
A B C
B D .
C E F
E . .
F . G
D . .
G . .

 

• 처음 숫자 7 은 아까 말한 노드 수 → 즉, 노드를 순회하면서 트리를 탐색할 반복 횟수 
• 우리는 그 다음 줄부터 쭉 딕셔너리 bt = {} 에 넣어줄거다.
• 딕셔너리의 키 → 각 줄에 있는 맨 앞 애들이면서 node의 이름
• 딕셔너리의 밸류 → B C, D .  처럼 각 줄의 두번째, 세번째 있는 애들이고, 각각 node의 왼쪽 자식, 오른쪽 자식 

이걸 이제 코드로 짜보면

# N번 반복
for _ in range(N):
    # 딕셔너리 키, 밸류값 지정
    node_str = input().strip().split()
    node = node_str[0]
    left = node_str[1]
    right = node_str[2]
    bt[node] = [left, right]  # build binary tree

 

 

이제 전위, 중위, 후위 순회를 해주면 끝난다.

• 중요한 건 자식이 없을 때, 즉 if node == '.' 으로 쩜 일 때, 그냥 지나가도록 해준다.
• 전위는 루트노드를 처음에 프린트하고 왼쪽 순회하고 오른쪽 순회하면 되는데 이때 자기자신을 재귀로 불러서 순회시키면 된다.

def preorder(node):
    if node == ".": # 자식이 없으면 그냥 지나가기
        return

    print(node, end='')
    preorder(bt[node][0]) # 재귀함수로 왼쪽 순회
    preorder(bt[node][1]) # 재귀함수로 오른쪽 순회

 

preorder("A")

 

preorder("A")만 프린트해보면 잘 나온다.

7
A B C
B D .
C E F
E . .
F . G
D . .
G . .
ABDCEFG

 

• 이제 inorder(중위)와 postorder(후위) 코드는 프린트 순서만 바꿔주면 된다. 
• inorder : 왼쪽  → 나(프린트) → 오른쪽
• postorder : 왼쪽 → 오른쪽 → 나(프린트)  

def inorder(node):
    if node == ".": # 자식이 없으면 그냥 지나가기
        return
    inorder(bt[node][0])
    print(node, end='')
    inorder(bt[node][1])

def postorder(node):
    if node == ".": # 자식이 없으면 그냥 지나가기
        return
    postorder(bt[node][0])
    postorder(bt[node][1])
    print(node, end='')

 

 

그리고 문제에서 항상 A가 루트노드가 된다고 했으므로 프리오더, 인오더, 포스트오더 안에 'A'를 넣어준다.

노드의 이름은 A부터 차례대로 알파벳 대문자로 매겨지며, 항상 A가 루트 노드가 된다. 자식 노드가 없는 경우에는 .으로 표현한다.

 

preorder('A')
inorder('A')
postorder('A')

 

실행해서 입력해보면 잘 나오는데 전위, 중위, 후위에 따른 줄바꿈이 안되어 있다. 

7
A B C
B D .
C E F
E . .
F . G
D . .
G . .
ABDCEFGDBAECFGDBEGFCA

 

preorder랑 inorder 사이, inodre랑 postorder 사이에 print()를 넣어서 줄바꿈 해주면 된다.

preorder('A')
print()
inorder('A')
print()
postorder('A')

 

그럼 실행시 이렇게 줄바꿈 되어서 잘 나오는 걸 볼 수 있다.

7
A B C
B D .
C E F
E . .
F . G
D . .
G . .
ABDCEFG
DBAECFG
DBEGFCA

 

 

[전체 코드]

N = int(input())
bt = {}

# N번 반복
for _ in range(N):
    # 딕셔너리 키, 밸류값 지정
    node_str = input().strip().split()
    node = node_str[0]
    left = node_str[1]
    right = node_str[2]
    bt[node] = [left, right]  # build binary tree


def preorder(node):
    if node == ".": # 자식이 없으면 그냥 지나가기
        return

    print(node, end='')
    preorder(bt[node][0]) # 재귀함수로 왼쪽 순회
    preorder(bt[node][1]) # 재귀함수로 오른쪽 순회


def inorder(node):
    if node == ".": 
        return
        
    inorder(bt[node][0])
    print(node, end='')
    inorder(bt[node][1])


def postorder(node):
    if node == ".":
        return
        
    postorder(bt[node][0])
    postorder(bt[node][1])
    print(node, end='')


preorder('A')
print()
inorder('A')
print()
postorder('A')