백준-1991 트리 순회

문제😀

이진 트리에 대해 전위순회, 중위순회, 후위순회를 알고리즘으로 구현하는 문제이다. 재귀함수에 대한 공부가 될수 있는 문제이다
여기서 개념들

• 이진트리 : 자식노드가 최대 두개인 노드들로 이루어진 트리
• 재귀함수 : 함수인 자기 자신을 다시 호출하는 함수, stack과 같은 형태로 실행된다.(LIFO)
• 전위순회 : 루트노드 -> left -> right
• 중위순회 : left -> 루트노드 -> right
• 후위순회 : left -> right -> 루트노드

전위 중위 후위순회는 단순히 루트노드를 언제 탐색할지에 따라서 나눈다.

생각😁

1. 일단 입력되어지는 트리의 정보는 모든 루트노드에 대한 정보이다. 자식노드가 없어도 모든 루트노드에 대한 정보가 들어있기 때문에 이를 활용하자는 생각이듬.
2. 재귀함수를 사용해서 반복해서 호출해야겠단 생각이 들었다.
3. 전, 중, 후위순회에 맞게 탐색할 노드의 위치와 재귀함수를 호출할 위치를 바꾸면 되겠다는 생각이듬

코드😃

# 이진트리 - 부모 노드1개, 자식노드 2개
# 전위순회 : root -> left -> right
# 중위순회 : left -> root -> right
# 후위순회 : left -> right -> root
# root를 언제 순회할지가 기준이다.
# 1991번

# 재귀함수로 풀어야할듯 딱 느낌이옴
# 입력되는 데이터도 많지않아서 구현에만 신경쓰면 될거같다

import sys
sys.setrecursionlimit(3000)

N = int(input())

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

visited = []
frontTree = []

for t in tree:
  frontTree.append(t[0])

def search(nodes):
  if nodes[0] != '.':
    visited.append(nodes[0])

  if nodes[1] != '.':
    leftIndex = frontTree.index(nodes[1])
    search(tree[leftIndex])
  if nodes[2] != '.':
    rightIndex = frontTree.index(nodes[2])
    search(tree[rightIndex])

search(tree[0])
for node in visited:
  print(node, end='')
print('')

visited=[]

def search2(nodes):
  if nodes[1] != '.':
    leftIndex = frontTree.index(nodes[1])
    search2(tree[leftIndex])
  if nodes[0] != '.':
    visited.append(nodes[0])
  if nodes[2] != '.':
    rightIndex = frontTree.index(nodes[2])
    search2(tree[rightIndex])

search2(tree[0])
for node in visited:
  print(node, end='')
print('')

visited = []

def search3(nodes):
  if nodes[1] != '.':
    leftIndex = frontTree.index(nodes[1])
    search3(tree[leftIndex])
  if nodes[2] != '.':
    rightIndex = frontTree.index(nodes[2])
    search3(tree[rightIndex])
  if nodes[0] != '.':
    visited.append(nodes[0])

search3(tree[0])
for node in visited:
  print(node, end='')
print('')

어려웠던 점🤣

• 재귀함수는 직관적으로 보이지가 않아서 구현하기가 꽤 힘들었다, 하지만 이부분은 나도 어느정도 감으로 '이정도면 되겠지?'라 생각하며 구현하니 감이 잡혔고 전위 순회를 구현하니 중위와 후위도 같은방식으로 구현해서 해결했다.