728x90
이진 트리를 입력 받아 preorder traversal, inorder traversal, postorder traversal한 결과를 출력하는 프로그램
풀이 1: tree를 딕셔너리로 표현, 재귀 이용
import sys
input = sys.stdin.readline
n = int(input().strip())
tree = {}
for _ in range(n):
parent, left, right = input().split()
tree[parent] = (left, right)
root = 'A'
def preorder(tree, node):
if node == '.':
return ""
return node + preorder(tree, tree[node][0]) + preorder(tree, tree[node][1])
def inorder(tree, node):
if node == '.':
return ""
return inorder(tree, tree[node][0]) + node + inorder(tree, tree[node][1])
def postorder(tree, node):
if node == ".":
return ""
return postorder(tree, tree[node][0]) + postorder(tree, tree[node][1]) + node
print(preorder(tree, root))
print(inorder(tree, root))
print(postorder(tree, root))각 노드를 딕셔너리의 키로 사용하고, 그 자식 노드를 값으로 저장하는 방식을 활용한다.
풀이2: Node 클래스 정의
class Node:
def __init__(self, key):
self.key = key
self.left = None
self.right = None
def preorder(node):
if node is None:
return ""
return node.key + preorder(node.left) + preorder(node.right)
def inorder(node):
if node is None:
return ""
return inorder(node.left) + node.key + inorder(node.right)
def postorder(node):
if node is None:
return ""
return postorder(node.left) + postorder(node.right) + node.key
# 입력
import sys
input = sys.stdin.readline
n = int(input().strip())
nodes = {}
for _ in range(n):
parent, left, right = input().split()
if parent not in nodes:
nodes[parent] = Node(parent)
if left != '.':
if left not in nodes:
nodes[left] = Node(left)
nodes[parent].left = nodes[left]
if right != '.':
if right not in nodes:
nodes[right] = Node(right)
nodes[parent].right = nodes[right]
root = nodes['A'] # 루트 노드는 항상 'A'
# 순회 결과 출력
print(preorder(root))
print(inorder(root))
print(postorder(root))Node 클래스로 트리의 각 노드를 정의하고,
preorder, inorder, postorder를 각각 재귀적으로 구현한다.
각 노드 정보를 입력 받을 때, nodes 딕셔너리를 사용하여 노드를 생성하고 연결한다.
left와 right 자식 노드가 .이 아니면 해당 노드를 생성하고 부모 노드에 연결한다.
마지막으로 루트 노드를 기준으로 순회를 수행하여 결과를 출력한다.
728x90
