트리 순회 결과 출력하기

문제

루트가 0인 이진트리가 주어질 때, 이를 전위순회, 중위순회, 후위순회한 결과를 각각 출력하는 프로그램을 작성하시오.

 

입력

첫 번째 줄에 트리의 노드 개수 n이 주어진다. ( 1 ≤ n ≤ 100 ) 두 번째 줄부터 트리의 정보가 주어진다. 각 줄은 3개의 숫자 a, b, c로 이루어지며, 그 의미는 노드 a의 왼쪽 자식노드가 b, 오른쪽 자식노드가 c라는 뜻이다. 자식노드가 존재하지 않을 경우에는 -1이 주어진다.

 

출력

첫 번째 줄에 전위순회, 두 번째 줄에 중위순회, 세 번째 줄에 후위순회를 한 결과를 출력한다.

 

예제 입력

6

0 1 2

1 3 4

2 -1 5

3 -1 -1

4 -1 -1

5 -1 -1

예제 출력

0 1 3 4 2 5

3 1 4 0 2 5

3 4 1 5 2 0

 

#코드

import sys
 
class Tree:
  left  = [0 for _ in range(100)]
  right = [0 for _ in range(100)]
 
def preorder(tree, x): 
  # x를 루트로 하는 서브트리를 전위순회 하여 출력하는 함수
  # 기저조건
  if tree.left[x] == -1 and tree.right[x] == -1:
    print(x, end=' ')
  else:
    # Root -> left -> right (전 중 후)
    print(x, end=' ')
    if tree.left[x] != -1:
      preorder(tree, tree.left[x])
    if tree.right[x] != -1:
      preorder(tree, tree.right[x])
      
def inorder(tree, x):
  if tree.left[x] == -1 and tree.right[x] == -1:
    print(x, end=' ')
  else:
    if tree.left[x] != -1:
      inorder(tree, tree.left[x])
    print(x, end=' ')
    if tree.right[x] != -1:
      inorder(tree, tree.right[x]) 
    
def postorder(tree, x):
  if tree.left[x] == -1 and tree.right[x] == -1:
    print(x, end=' ')
  else:
    if tree.left[x] != -1:
      postorder(tree, tree.left[x])
    if tree.right[x] != -1:
      postorder(tree, tree.right[x]) 
    
    print(x, end=' ')
  
 
if __name__ == "__main__": 
  n = int(sys.stdin.readline())
  getInfo = []
  tree = Tree()
  
  for i in range(n):
    a, b, c = map(int, sys.stdin.readline().split()) 
    tree.left[a] = b
    tree.right[a] = c  
  
  preorder(tree, 0)
  print()
  inorder(tree, 0)
  print()
  postorder(tree, 0)

 

#복습

import sys
 
def preorder(x):
  # x를 루트로 하는 서브트리를 전위순회 하여 출력하는 함수
  # 기저조건 : 노드의 자식 노드가 없을 때
  if myTree[x][0] == -1 and myTree[x][1] == -1:
    print(x, end=' ')
  else:
    print(x, end=' ')
    if myTree[x][0] != -1:
      preorder(myTree[x][0])
    if myTree[x][1] != -1:
      preorder(myTree[x][1])
      
def inorder(x):
  if myTree[x][0] == -1 and myTree[x][1] == -1:
    print(x, end=' ')
  else:
    if myTree[x][0] != -1:
      inorder(myTree[x][0])
    print(x, end=' ')
    if myTree[x][1] != -1:
      inorder(myTree[x][1])
      
def postorder(x):
  # 왼쪽 - 오른쪽 - 중간
  if myTree[x][0] == -1 and myTree[x][1] == -1:
    print(x, end=' ')
  else:
    if myTree[x][0] != -1:
      postorder(myTree[x][0])
    if myTree[x][1] != -1:
      postorder(myTree[x][1])
    print(x, end=' ')
 
 
if __name__ == "__main__":
  input = sys.stdin.readline 
  n = int(input()) 
  myTree = [[] for _ in range(n)] 
  for _ in range(n):
    a, b, c = map(int, input().split()) 
    myTree[a].append(b)
    myTree[a].append(c)
   
  preorder(0)
  print()
  inorder(0)
  print()
  postorder(0)