BOJ [트리 순회]

문제

2022-03-29

문제 보기

이런 식으로 각 트리의 data,left,right이 주어지면 root를 A로 지정한 다음 트리를 만들라는 문제

풀이

class를 재귀적으로 선언해서 tree를 만듦. init(self,data,list)로 초기화.

data는 해당 tree의 root의 data, self.left = Tree(left,list) 로 넘기는데 list는

해당 tree 초기화 할때 참조한 list i열을 뺀다음 넘긴다.

주의점

'.' 들어오면 none 처리해주는거랑 나중에 탐색할때도 none이면 안하게 처리하는거 주의

코드

n = int(input())

list = []
for _ in range(n):
  list.append(input().split())

class Tree:
  def __init__(self,data,list):
    for i in range(len(list)):
      if list[i][0] == data:
        
        self.data = list[i][0]
        left = list[i][1]
        right = list[i][2]

        del list[i]
        
        if left != '.':
          self.left = Tree(left,list)
        else:
          self.left = None

        if right != '.':
          self.right = Tree(right,list)
        else:
          self.right = None

        break

tree = Tree('A',list)

pre_arr = []
in_arr = []
post_arr = []

def preorder(tree):
  pre_arr.append(tree.data)
  if tree.left != None:
    preorder(tree.left)
  if tree.right != None:
    preorder(tree.right)

def inorder(tree):
  if tree.left != None:
    inorder(tree.left)
  in_arr.append(tree.data)
  if tree.right != None:
    inorder(tree.right)

def postorder(tree):
  if tree.left != None:
    postorder(tree.left)
  if tree.right != None:
    postorder(tree.right)
  post_arr.append(tree.data)

preorder(tree)
inorder(tree)
postorder(tree)

for i in pre_arr:
  print(i,end='')
print('')
for i in in_arr:
  print(i,end='')
print('')
for i in post_arr:
  print(i,end='')