백준-1991 트리 순회
문제😀
이진 트리에 대해 전위순회, 중위순회, 후위순회를 알고리즘으로 구현하는 문제이다. 재귀함수에 대한 공부가 될수 있는 문제이다
여기서 개념들
- 이진트리 : 자식노드가 최대 두개인 노드들로 이루어진 트리
- 재귀함수 : 함수인 자기 자신을 다시 호출하는 함수, stack과 같은 형태로 실행된다.(LIFO)
- 전위순회 : 루트노드 -> left -> right
- 중위순회 : left -> 루트노드 -> right
- 후위순회 : left -> right -> 루트노드
전위 중위 후위순회는 단순히 루트노드를 언제 탐색할지에 따라서 나눈다.
생각😁
- 일단 입력되어지는 트리의 정보는 모든 루트노드에 대한 정보이다. 자식노드가 없어도 모든 루트노드에 대한 정보가 들어있기 때문에 이를 활용하자는 생각이듬.
- 재귀함수를 사용해서 반복해서 호출해야겠단 생각이 들었다.
- 전, 중, 후위순회에 맞게 탐색할 노드의 위치와 재귀함수를 호출할 위치를 바꾸면 되겠다는 생각이듬
코드😃
# 이진트리 - 부모 노드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('')
어려웠던 점🤣
- 재귀함수는 직관적으로 보이지가 않아서 구현하기가 꽤 힘들었다, 하지만 이부분은 나도 어느정도 감으로 '이정도면 되겠지?'라 생각하며 구현하니 감이 잡혔고 전위 순회를 구현하니 중위와 후위도 같은방식으로 구현해서 해결했다.
Author And Source
이 문제에 관하여(백준-1991 트리 순회), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@yjs3819/백준-1991-트리-순회저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)