[BOJ] 1991번: 트리 순회

나동빈 님의 코딩 테스트를 위한 트리(Tree) 자료구조 10분 핵심 요약 과 여러 블로그를 참고하면서 트리에 대해 공부했다. 개념을 봤다면 백준에서 바로 적용해보는 것이 알고리즘에 대한 예의라고 생각한다. 😎  

---

 

문제

 

입출력 예시

 

클래스 및 순회 결과 출력을 위한 함수 구현

트리 구현은 처음이라 나동빈 님의 코드를 참고했다.

# 트리 구조 표현을 위한 노드 클래스 생성
class Node:
    def __init__(self, root, left_node, right_node):
        self.root = root		# 부모 노드
        self.left_node = left_node	# 왼쪽 노드
        self.right_node = right_node	# 오른쪽 노드
    
# 전위 순회
def preorder(node):
    print(node.root, end='')
    
    # 자식 노드가 있을 때 왼쪽 노드부터 방문 후 출력
    if node.left_node != ".":
        preorder(tree[node.left_node])
    
    if node.right_node != ".":
        preorder(tree[node.right_node])

def inorder(node):
    if node.left_node != ".":
        inorder(tree[node.left_node])
    
    print(node.root, end='')

    if node.right_node != ".":
        inorder(tree[node.right_node])

def postorder(node):
    if node.left_node != ".":
        postorder(tree[node.left_node])
    
    if node.right_node != ".":
        postorder(tree[node.right_node])
    
    print(node.root, end='')

 

각 순회 방식의 큰 차이점은 노드 출력 순서이다. 전위/중위/후위 순회 방식에 따라 노드를 방문하고 결과를 출력하는데 트리는 큰 트리 안에 서브 트리가 존재하기 때문에 재귀의 개념도 들어간다. 클래스를 많이 써보지 않아서 노드 클래스 구현 부분이 생소했지만 클래스에 익숙한 사람이라면 이 문제를 쉽게 해결할 것 같다.

 

 

전체 코드

# Silver 1

class Node:
    def __init__(self, root, left_node, right_node):
        self.root = root
        self.left_node = left_node
        self.right_node = right_node
    
def preorder(node):
    print(node.root, end='')
    
    if node.left_node != ".":
        preorder(tree[node.left_node])
    
    if node.right_node != ".":
        preorder(tree[node.right_node])

def inorder(node):
    if node.left_node != ".":
        inorder(tree[node.left_node])
    
    print(node.root, end='')

    if node.right_node != ".":
        inorder(tree[node.right_node])

def postorder(node):
    if node.left_node != ".":
        postorder(tree[node.left_node])
    
    if node.right_node != ".":
        postorder(tree[node.right_node])
    
    print(node.root, end='')

# 노드 개수
n = int(input())

# 부모/자식 노드 관계 표현을 위한 딕셔너리
# ex) A(부모): [B, C](자식)
tree = {}

for i in range(n):
    root, left_node, right_node = input().split()
    
    tree[root] = Node(root, left_node, right_node)

preorder(tree['A'])
print()
inorder(tree['A'])
print()
postorder(tree['A'])