https://www.acmicpc.net/problem/1991
이진 트리를 입력 받아 전위 순회(preorder traversal), 중위 순회(inorder traversal), 후위 순회(postorder traversal) 세가지 모두 수행한 결과 물을 출력하는 문제
트리 개념을 익히기 위해서 클래스로 트리를 구현하고 전위, 중위, 후위 순회를 구현해보았다.
노드 클래스 구현
트리는 노드들로 구성되고,
각 노드들은 다음과 같은 정보가 필요하다고 생각했다
1. 본인의 값
2. 왼쪽 자식의 정보
3. 오른쪽 자식의 정보
위 3가지 중 자식들에 대한 정보는 노드의 형태로 저장해 부모에서 자식으로 내려가면서 순회가 가능하도록 작성하였다.
class Node:
def __init__(self, data):
self.data = data
self.left = None
self.right = None본인의 값만 파라미터로 받아 저장하고 왼쪽, 오른쪽 자식들은 None 값으로 초기화 하도록 생성자를 만들었다.
노드에 자식 노드들 연결하기
문제에서 데이터를 입력 받을때,
본인 왼쪽 오른쪽의 값을 한줄로 받아오기 때문에 각각의 입력 한줄을 받아올때 마다 본인 노드를 트리에서 찾고,
1. 존재 한다면 자식 노드들 추가 or 수정
2. 존재 하지 않는다면 본인과 자식 노드를 연결 시켜 트리에 추가
위 2가지 행동이 필요했고 맨위 루트 노드 부터 재귀적으로 트리를 순회하면서 본인의 값이 존재 하는지 찾을 수 있도록 하는 함수를 노드 클래스에 추가 하였다.
def search_data(self, data):
result = None
if self.data == data:
return self
if self.left is not None:
result = self.left.search_data(data)
if result is not None:
return result
if self.right is not None:
result = self.right.search_data(data)
if result is not None:
return result
if self.left is None and self.right is None:
return None트리 순회 하기
1. 전위 순회
전위 순회는 루트, 왼쪽, 오른쪽 순서로 순회하는 방식으로 재귀적으로 트리를 순회하면서 출력하도록 코드를 작성 했다.
def preorder_traversal(self, result):
temp = self.data # 본인
if self.left is not None: # 왼쪽
temp += self.left.preorder_traversal(temp)
if self.right is not None: # 오른쪽
temp += self.right.preorder_traversal(temp)
return temp2. 중위 순회
중위 순회는 왼쪽, 루트, 오른쪽 순서로 순회하는 방식으로 재귀적으로 트리를 순회하면서 출력하도록 코드를 작성 했다.
def inorder_traversal(self, result):
temp = result
if self.left is not None: # 왼쪽
temp = self.left.inorder_traversal(temp)
temp += self.data # 본인
if self.right is not None: # 오른쪽
temp = self.right.inorder_traversal(temp)
return temp3. 후위 순회
후위 순회는 왼쪽, 오른쪽, 루트 순서로 순회하는 방식으로 재귀적으로 트리를 순회하면서 출력하도록 코드를 작성 했다.
def postorder_traversal(self, result):
temp = result
if self.left is not None: # 왼쪽
temp = self.left.postorder_traversal(temp)
if self.right is not None: # 오른쪽
temp = self.right.postorder_traversal(temp)
temp += self.data # 본인
return temp노드 클래스 전체 코드
위와 같은 생성자와 함수들이 추가된 노드 클래스의 전체 코드는 다음과 같다
class Node:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
def search_data(self, data):
result = None
if self.data == data:
return self
if self.left is not None:
result = self.left.search_data(data)
if result is not None:
return result
if self.right is not None:
result = self.right.search_data(data)
if result is not None:
return result
if self.left is None and self.right is None:
return None
def preorder_traversal(self, result):
temp = self.data # 본인
if self.left is not None: # 왼쪽
temp += self.left.preorder_traversal(temp)
if self.right is not None: # 오른쪽
temp += self.right.preorder_traversal(temp)
return temp
def inorder_traversal(self, result):
temp = result
if self.left is not None: # 왼쪽
temp = self.left.inorder_traversal(temp)
temp += self.data # 본인
if self.right is not None: # 오른쪽
temp = self.right.inorder_traversal(temp)
return temp
def postorder_traversal(self, result):
temp = result
if self.left is not None: # 왼쪽
temp = self.left.postorder_traversal(temp)
if self.right is not None: # 오른쪽
temp = self.right.postorder_traversal(temp)
temp += self.data # 본인
return temp문제 풀이
위와 같이 구현해본 노드 클래스를 사용한 코드는 다음과 같다
import sys
def main():
n = int(sys.stdin.readline())
root = Node('')
for i in range(n):
data, left_data, right_data = sys.stdin.readline().rstrip().split()
if i == 0:
root.data = data
if left_data != '.':
root.left = Node(left_data)
if right_data != '.':
root.right = Node(right_data)
else:
temp = root.search_data(data)
if temp is not None:
if left_data != '.':
temp.left = Node(left_data)
if right_data != '.':
temp.right = Node(right_data)
print(root.preorder_traversal(''))
print(root.inorder_traversal(''))
print(root.postorder_traversal(''))
if __name__ == '__main__':
main()마무리
기존에 문제를 풀때 따로 main 함수를 작성하고 프로그램의 시작지점을 main 함수로 지정해 주면서 코드를 작성해보지 않았는데, 기존과 다르게 클래스를 사용하니 클래스의 생성자 부분에서 자꾸 parameter가 여러개 들어갔다고 에러가 발생해 해결하려고 고생하다가 혹시나 해 main 함수로 작성해 풀어보니 동일한 문제는 발생하지 않았다. 해당 부분에 대한 이유를 찾고 정리가 필요하다.
