[백준] 1991번 : 트리 순회 (python)

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

1991번: 트리 순회

---

아이디어

• Node class와 BinaryTree class를 이용하여 각각의 node를 따로 저장해두고 root node로부터 엮어나가기

n = int(input())
i = 0

class Node:
    def __init__(self, item):
        self.item = item
        self.left = None
        self.right = None
        
class BinaryTree():
    def __init(self):
        self.root = None
    
    # 전위 순회
    def preorder(self, n):
        if n != None: # node가 있으면
            print(n.item, '', end='') # root node
            if n.left:
                self.preorder(n.left) # left node
            if n.right:
                self.preorder(n.right) # right node
    #중위 순회           
    def inorder():
        if n != None:
            if n.left:
                self.inorder(n.left) # left node
            print(n.item, '', end='') # root node
            if n.right:
                self.inorder(n.right) # right node
    #후위 순회
    def postorder():
        if n != None:
            if n.left:
                self.postorder(n.left) # left node
            if n.right:
                self.postorder(n.right) # right node
            print(n.item, '', end='') # root noe

# node 저장
for _ in range(n):
    
    o,r,l = input().split()#루트 / 왼쪽 / 오른쪽
    i += 1
    globals()['n'+str(i)]  = Node(o)
    i += 1
    globals()['n'+str(i)]  = Node(l)
    i += 1
    globals()['n'+str(i)]  = Node(r)
    

# 순서에 맞게 node 엮기
tree = BinaryTree()
tree.root = n1

# 변수 명 불러오기 --> 어떻게?
for x in range(1,n+1):
    eval('n'+str(i)).left = eval('n'+str(i*2))
    eval('n'+str(i)).right = eval('n'+str(i*2+1))
    
# 변수 값 불러오기
for i in range(n*3):
    print(eval('n'+str(i)))

 

어려웠던 점:

• loop를 이용해서 변수 명을 지정하고, 변수를 불러와서 변수.left를 지정해야 한다는 점이 어려웠다. 그래서 이 문제는 배열을 이용해서 푸는 것이 훨씬 간단하고 쉬울 것 같다.
• node class를 만들어서 푸려고 했는데, 이 문제같은 경우에는 [root, left, right] 순서로 입력을 받고, 위에서 left node 자리에 적은 알파벳을 나중에 또 root node로 입력받을 수 있다는 특징이 있었다. 그래서 이 방식으로 풀면 안될것이라 생각했다. (위의 코드는 연관없는 값들을 순차적으로 입력받고, 나중에 입력받은 순서대로 left ndoe와 right node의 관계를 엮어주는 방식이기 때문. )

---

• 다른 풀이

구글링을 해보니, 아래와 같은 방식의 풀이가 대부분인 것 같다.

 

아이디어1

• key = root node, value = left, right node 형식으로 tree dictionary에 입력받은 값들 저장

아이디어2

• preorder, inorder, postorder 함수를 각각 만들고, 내부에서 재귀를 통해 node 순회하기
• node = '.' 일때 pass
• 처음 재귀함수를 호출할 때에, 아래와 같이 호출할 수 있었던 이유 = A가 항상 root node가 된다는 조건이 있기 때문.

코드

import sys
input = sys.stdin.readline
N = int(input().strip())
tree = {}
 
for n in range(N):
    root, left, right = input().strip().split()
    tree[root] = [left, right]
#print(tree)



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
 
 
preorder('A')
print()
inorder('A')
print()
postorder('A')

 

---

참고

https://boleumdal.tistory.com/entry/Python-%EB%B0%98%EB%B3%B5%EB%AC%B8%EC%97%90%EC%84%9C-%EB%B3%80%EC%88%98-%EC%84%A0%EC%96%B8%ED%95%98%EB%8A%94-%EB%B2%95

[Python] 반복문에서 변수 선언하는 법

https://qqplot.github.io/python/2021/09/18/binary_tree.html

파이썬으로 이진트리 구현하기