[백준] 트리 순회

https://www.acmicpc.net/problem/1991

1991번: 트리 순회

 

Node class 를 만들어 트리 순회를 해보았다.

 

dic[i] = Node(i) (i 는 'A' ~ 'Z') 를 만들고 주어지는 입력을 바탕으로 dic[i].left = dic[left], dic[i].right = dic[right] 로 왼쪽 자식 노드 또는 오른쪽 자식 노드에 알맞는 노드를 준다. '.' 은 생략한다.

 

다음 재귀를 이용하여 전위 순회, 중위 순회, 후위 순회를 구현한다. 

 

이해를 위해서 3개의 함수로 나눴는데 하나의 함수로도 나타낼 수 있다.

 

import sys

class Node:
    
    def __init__(self, root):
        self.root = root
        self.left = self.right = None

def preorder(node):
    print(node.root, end = '')
    
    if node.left != None: preorder(node.left)
    if node.right != None: preorder(node.right)

def inorder(node):
    if node.left != None: inorder(node.left)
    
    print(node.root, end = '')
    
    if node.right != None: inorder(node.right)

def postorder(node):
    if node.left != None: postorder(node.left)
    if node.right != None: postorder(node.right)
    
    print(node.root, end = '')
            
N = int(sys.stdin.readline())
dic = {}
s = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'

for i in s:
    dic[i] = Node(i)

for i in range(N):
    root, left, right = sys.stdin.readline().split()
    
    if left != '.': dic[root].left = dic[left]
    if right != '.': dic[root].right = dic[right]

preorder(dic['A'])

print()

inorder(dic['A'])

print()

postorder(dic['A'])

 

import sys

preorderArray = []
inorderArray = []
postorderArray = []

class Node:
    
    def __init__(self, root):
        self.root = root
        self.left = self.right = None

def order(node):
    global preorderArray
    global inorderArray
    global postorderArray
    
    preorderArray.append(node.root)
    order(node.left)
    inorderArray.append(node.root)
    order(node.right)
    postorderArray.append(node.root)
    
            
N = int(sys.stdin.readline())
dic = {}
s = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'

for i in s:
    dic[i] = Node(i)

for i in range(N):
    root, left, right = sys.stdin.readline().split()
    
    if left != '.': dic[root].left = dic[left]
    if right != '.': dic[root].right = dic[right]

order(dic['A'])

print(''.join(preorderArray))
print(''.join(inorderArray))
print(''.join(postorderArray))