[자료구조] Python Tree

Tree

• 트리란 항상 루트(root)에서 시작된다.
• 루트는 자식 노드를 가지고, 간선(Edge) 으로 연결되어 있다.
• 자식 노드의 개수는 차수라고 한다.
• 크기는 자신을 포함한 모든 자식 노드의 개수이다.
• 높이는 현재 위치에서부터 리프까지의 거리, 깊이는 루트에서부터 현재 노드까지의 거리이다.

이진트리

• 트리 자료구조는 이진 트리와 이진 탐색트리 이다.
• 이진 트리는 한 노드가 자식 노드를 두 개 이하만 갖는 트리입니다.
• 이진 트리의 노드도 데이터부분과 참조 부분으로 이루어져 있습니다.
• 왼쪽 자식 노드를 가리키는 참조와 오른쪽 자식 노드를 가리키는 참조가 있습니다.

트리 노드 구현

이진 트리는 Node클래스로 만들어집니다.
class Node는

• data: 데이터가 담기는 공간
• left: 왼쪽 자식노드
• right: 오른쪽 자식노드

class Node:

    def __init__(self, data):
        self.left = None
        self.right = None
        self.data = data

    def insert(self, data):
        if self.data: # 이미 공간에 데이터가 있을경우
            if data < self.data: # 들어온 데이터가 원래 데이터보다 작다면 왼쪽으로
                if self.left is None: # 왼쪽에 데이터가 비어있다면
                    self.left = Node(data) # 데이터 저장
                else: # 데이터가 비어있지 않으면 다음 왼쪽 노드로
                    self.left.insert(data)
            elif data > self.data: # 들어온 데이터가 현재 데이터보다 크다면 오른쪽으로
                if self.right is None: # 오른쪽에 데이터가 비어있다면
                    self.right = Node(data) # 데이터 저장
                else: # 데이터가 차있다면 다음 오른쪽 노드로
                    self.right.insert(data)
        else: # 데이터가 없다면 그대로 추가
            self.data = data

    def PrintTree(self): # 가장 왼쪽 데이터부터 
        if self.left:
            self.left.PrintTree()
        print(self.data)
        if self.right:
            self.right.PrintTree()

root = Node(10)
root.PrintTree()

백준 트리 기본문제

https://www.acmicpc.net/problem/1991

[1991번: 트리 순회

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

n = int(input())
inputs = []
for _ in range(n):
    inputs.append(input().split())

class Node():
    def __init__(self, item, left, right):
        self.item = item
        self.left = left
        self.right = right

def preorder(node):
    print(node.item, end = '')
    if node.left != '.':
        preorder(tree[node.left])
    if node.right != '.':
        preorder(tree[node.right])

def inorder(node):
    if node.left != '.':
        inorder(tree[node.left])
    print(node.item, end = '')
    if node.right != '.':
        inorder(tree[node.right])

def postorder(node):
    if node.left != '.':
        postorder(tree[node.left])
    if node.right != '.':
        postorder(tree[node.right])
    print(node.item, end = '')

tree = {}
for item, left, right in inputs:
    tree[item] = Node(item, left, right)
preorder(tree['A'])
print()
inorder(tree['A'])
print()
postorder(tree['A'])

참조

https://velog.io/@ash3767/python-Data-Structure