본문 바로가기
Language/Python

[Python] 트리 구현 하기

by 애기 개발자 2023. 4. 11.
반응형

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

 

2023.04.08 - [Language/Java] - [Java] 트리 구현하기 (이진트리, 전위순회, 중위순회, 후위순회)

 

[Java] 트리 구현하기 (이진트리, 전위순회, 중위순회, 후위순회)

트리 구현 위와 같은 형태를 갖추며 각 노드는 (Data, Left, Right)의 구조체를 갖는다. public static class Node { char data; Node leftNode; Node rightNode; //Node에 값 넣고 초기화 public Node(char data) { this.data = data; this

baby-dev.tistory.com

 

오늘은 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번: 트리 순회

첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파

www.acmicpc.net

 

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'])
반응형

댓글