[Python] 트리 구현 하기

Java로 구현하는 법을 며칠 전에 공부했다.

 

2023.04.08 - [Language/Java] - [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

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'])