반응형
Java로 구현하는 법을 며칠 전에 공부했다.
2023.04.08 - [Language/Java] - [Java] 트리 구현하기 (이진트리, 전위순회, 중위순회, 후위순회)
오늘은 Python으로 트리를 구현해 보자.
우선 Java의 구조체를 담당하는 부분으로
class Node:
def __init__(self, data, leftNode, rightNode):
self.data = data
self.leftNode = leftNode
self.rightNode = rightNode
class를 선언하고 안에 __init__ 함수를 만들어 준다.
tree는 어느 구조에 담느냐면
n = int(input())
tree = {}
class Node:
def __init__(self, data, leftNode, rightNode):
self.data = data
self.leftNode = leftNode
self.rightNode = rightNode
for _ in range(n):
data, left, right = map(str, input().split())
if left == '.':
left = None
if right == '.':
right = None
tree[data] = Node(data, left, right)
tree = {}에 담는다.
이후 전위, 중위, 후위 순회는 Java와 동일하게 재귀로 처리한다.
def preOrder(node):
print(node.data, end="")
if node.leftNode != None:
preOrder(tree[node.leftNode])
if node.rightNode != None:
preOrder(tree[node.rightNode])
def inOrder(node):
if node.leftNode != None:
inOrder(tree[node.leftNode])
print(node.data, end="")
if node.rightNode != None:
inOrder(tree[node.rightNode])
def postOrder(node):
if node.leftNode != None:
postOrder(tree[node.leftNode])
if node.rightNode != None:
postOrder(tree[node.rightNode])
print(node.data, end="")
전체 코드
(백준 1991번 - 트리 순회의 정답 코드)
https://www.acmicpc.net/problem/1991
import sys
input = sys.stdin.readline
n = int(input())
tree = {}
class Node:
def __init__(self, data, leftNode, rightNode):
self.data = data
self.leftNode = leftNode
self.rightNode = rightNode
def preOrder(node):
print(node.data, end="")
if node.leftNode != None:
preOrder(tree[node.leftNode])
if node.rightNode != None:
preOrder(tree[node.rightNode])
def inOrder(node):
if node.leftNode != None:
inOrder(tree[node.leftNode])
print(node.data, end="")
if node.rightNode != None:
inOrder(tree[node.rightNode])
def postOrder(node):
if node.leftNode != None:
postOrder(tree[node.leftNode])
if node.rightNode != None:
postOrder(tree[node.rightNode])
print(node.data, end="")
for _ in range(n):
data, left, right = map(str, input().split())
if left == '.':
left = None
if right == '.':
right = None
tree[data] = Node(data, left, right)
preOrder(tree['A'])
print()
inOrder(tree['A'])
print()
postOrder(tree['A'])
반응형
'Language > Python' 카테고리의 다른 글
[Python] 진법 변환 정리 (0) | 2023.04.27 |
---|---|
[Python] 리스트에 특정 값이 있는지 체크하기 (0) | 2022.10.02 |
[Python] sys.stdin.readline 입력 받기 (0) | 2022.09.30 |
[Python] reverse, reversed 차이 (0) | 2022.09.13 |
[Python] 현재 날짜 가져오기 (0) | 2022.08.08 |
댓글