[BOJ] 1991번 트리 순회

정재욱·2023년 5월 16일

레벨 순회 이진트리 전위 순회 중위 순회 후위 순회

Algorithm

목록 보기

28/33

백준 1991번 트리 순회 (실버 1)

문제

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

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

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

가 된다.

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

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

위 문제를 풀 기 위해선 트리와 이진트리에 대한 개념을 우선 알아야 한다.

트리 , 이진트리

트리는 empty이거나, empty가 아니면 루트 R과 트리의 집합으로 구성되는데 각 트리의 루트는 R의 자식노드이다. 단, 트리의 집합은 공집합일 수도 있다.

정점(or 노드) : 트리에서의 각 원소
루트 : 트리의 제일 꼭대기에 위치한 정점. 위 그림에서는 1번 정점이 루트다.
리프 : 제일 말단에 위치해서 아래로 뻗은게 없는 정점
간선(Edge) : 정점을 연결하는 선
부모 자식 관계 : 간선으로 연결된 위 아래의 관계
- 위 그림에서 3번 정점은 7, 8번 정점의 부모 정점이고 7, 8번 정점은 3번 정점의 자식 정점이다.
차수(Degree) : 자식노드의 수
서브트리 : 어떤 한 정점에 대해 그 밑에 있는 정점과 간선만을 모은 트리
- 위 그림에서는 2, 4, 5, 6, 9 노드가 2번 정점에 대한 서브트리이다.
레벨(깊이) : 트리가 위 아래로 뻗어있는 정도
- 노드가 1개만 있을 때의 높이를 1로 두느냐 0으로 두느냐에 따라서 위 그림의 트리 높이가 3일 수도 있고 4일 수도 있긴 한데 크게 중요한 부분은 아니다.

이진 트리란 각 노드의 자식 수가 2 이하인 트리이다.
- 즉, empty 이거나 empty가 아니면, 루트와 2개의 이진트리인 왼쪽 서브트리와 오른쪽 서브트리로 구성된다.

트리의 순회

그 다음으로 다룰 주제는 이진 트리에서의 순회이다. 지금까지 우리가 아는 순회 방식으로는 BFS와 DFS가 있지만 특별히 이진 트리에 대해 따로 이름이 붙은 순회들이 있다.
바로 레벨 순회와 전위/중위/후위 순회이다. 이 4가지 순회를 익혀보자.

하지만 그 전에 선행되어야 할 것이 있다. 바로 이진 트리를 코드에서 표현하는 방법이다.
물론 이진 트리도 트리의 일종이자 더 나아가 그래프의 특수한 모습이기 때문에 그냥 그래프에서 쓰던 방법이랑 똑같이 graph에 넣어서 저장을 할 수는 있다.
하지만 이렇게 처리를 해버리면 왼쪽 자식과 오른쪽 자식을 구분할 수가 없다.

그렇기 때문에 인접 리스트를 이용한 방법 대신에 왼쪽 자식과 오른쪽 자식을 저장하게끔 코드를 구성해두는게 좋다. 예쁘게 짜려면 클래스를 만들고 left, right라는 이름의 인스턴스 변수를 두는 방법이 있다. 해당 방식을 선호하시면 그렇게 구현해도 상관은 없지만 저는 클래스를 별도로 정의해서 두는 것 보다는 그냥 배열 혹은 딕셔너리를 가지고 처리하는 방식이 간편하다.

예를 들어 위 사진처럼 이진트리가 존재한다 하자.

tree = {} 처럼 딕셔너리를 선언해준다.
tree 딕셔너리에서 key는 부모가 될 것이고, value는 자식이 될 것이다.

전위 순회

노드 N에 도착했을 때 N을 먼저 방문한다. 그 다음에 N의 왼쪽 자식노드로 순회를 계속한다. N의 왼쪽 서브트리의 모든 노드들을 방문한 후에는 N의 오른쪽 서브트리의 모든 후손 노드들을 방문한다.
전위순회 순서를 NLR로 표현하기도 한다. ( N = 노드 방문, L은 왼쪽 R은 오른쪽 서브트리로 순회)

위 그림에서 보면 ABDCEFG 순으로 방문을 하게 된다.

간단한 전위순회 구현 코드는 아래와 같다.

def preorder(root):
	if root != None:
    	print(root) # 노드 N 방문
    	preorder(left_node)  # 왼쪽 서브트리 방문
        preorder(right_node) # 오른쪽 서브트리 방문

중위 순회

노드 N에 도착하면 N의 방문을 보류하고 N의 왼쪽 서브트리로 순회를 진행한다. 그리고 왼쪽 서브트리의 모든 노드들을 방문한 후에 N을 방문한다. N을 방문한 후에는 N의 오른쪽 서브트리를 같은 방식으로 방문한다.
중위순회 순서를 LNR로 표현한다.

위 그림에서 보면 DBAECFG 순으로 방문을 하게 된다.

간단한 중위순회 구현 코드는 아래와 같다.

def inorder(root):
	if root != None:
    	inorder(left_node)  # 왼쪽 서브트리 방문
    	print(root) # 노드 N 방문
    	inorder(right_node) # 오른쪽 서브트리 방문

후위 순회

노드 N에 도착하면 N의 방문을 보류하고 N의 왼쪽 서브트리로 순회를 진행한다. N의 왼쪽 서브트리를 방문한 후에는 N의 오른쪽 서브트리를 같은 방식으로 방문한다. 그리고 마지막에 N을 방문한다.
후위순회 순서를 LRN으로 표현한다.

위 그림에서 보면 DBEGFCA 순으로 방문을 하게 된다.

간단한 후위순회 구현 코드는 아래와 같다.

def postorder(root):
	if root != None:
    	postorder(left_node)  # 왼쪽 서브트리 방문
        postorder(right_node) # 오른쪽 서브트리 방문
    	print(root) # 노드 N 방문

레벨 순회

루트가 있는 최상위 레벨부터 시작하여 각 레벨마다 좌에서 우로 노드들을 방문한다.

위 그림에서 보면 ABCDEFG 순으로 방문을 하게 된다.

레벨 순회는 큐 자료구조를 활용한다.

간단한 레벨순회 구현 코드는 아래와 같다.

from collections import deque

def levelorder(root):
	queue = deque()
    queue.append(root)

    while queue:
    	n = queue.popleft() # 큐에서 첫 항목 삭제
        print(n) 		# 삭제된 노드 방문

        # 이후 왼쪽, 오른쪽 자식들을 큐에 삽입
        if n.left != None:
        	queue.append(n.left)
        if n.right != None:
        	queue.append(n.right)

이진트리의 높이

추가적으로 이진 트리의 높이를 구하는 방법을 알아보자.

트리의 높이 = 1 + max(루트의 왼쪽 서브트리의 높이, 루트의 오른쪽 서브트리의 높이)이다.
여기서 1은 루트 자신을 계산에 반영한 것이다.

def height(root):
	if root == None:
    	return 0
    return max(height(root.left), height(root.right)) + 1  # 두 자식노드의 높이 중 큰 높이+1

문제 풀이

해당 문제는 위 내용을 기반으로 아주 간단하게 풀 수 있다.

우선 트리를 사전으로 간단하게 표현하자.
즉, A가 부모이고 그 자식노드가 B,C 라면 -> {A : [B, C]}

import sys


def preorder(root):
    if root != ".":
        print(root, end="")  # root
        preorder(tree[root][0])  # left
        preorder(tree[root][1])  # right


def inorder(root):
    if root != ".":
        inorder(tree[root][0])  # left
        print(root, end="")  # root
        inorder(tree[root][1])  # right


def postorder(root):
    if root != ".":
        postorder(tree[root][0])  # left
        postorder(tree[root][1])  # right
        print(root, end="")  # root


if __name__ == "__main__":
    input = sys.stdin.readline

    N = int(input().strip())
    tree = {}

    for n in range(N):
        root, left, right = input().strip().split()
        tree[root] = [left, right]

    preorder("A")
    print()
    inorder("A")
    print()
    postorder("A")