[알고리즘 개념] 트리

0. 트리란?

• 가계도와 같은 계층적인 구조를 표현할 때 사용할 수 있는 자료구조

[ 트리 관련 용어 ]

• 루트 노드 : 부모가 없는 최상위 노드
• 단말 노드 : 자식이 없는 노드
• 크기 : 트리에 포함된 모든 노드의 개수
• 깊이 : 루트 노드부터의 거리
• 높이 : 깊이 중 최댓값
• 간선 : 노드를 연결하는 선
• 차수 : 각 노드의 간선 개수 - 트리의 크기가 n이면 전체 간선의 수는 n-1개

1. 이진 탐색 트리

이진 탐색이 동작할 수 있도록 고안된 효율적인 탐색이 가능한 자료 구조의 일종

이진 탐색 트리의 특징

왼쪽 자식 노드 < 부모 노드 < 오른쪽 자식 노드

2. 트리의 순회( Tree Traversal )

• 전위 순회(pre-order traverse) : 루트를 먼저 방문하고 다음 노드 탐색(뿌리 -> 왼쪽 자식 -> 오른쪽 자식)
• 중위 순회(in-order traverse) : 왼쪽 자식을 방문한 뒤에 루트를 방문(왼쪽 자식 -> 뿌리 -> 오른쪽 자식)
• 후위 순회(post-order traverse) : 맨 하위 노드부터 방문한 뒤 마지막에 루트를 방문(왼쪽 자식 -> 오른쪽 자식 -> 뿌리)

전위 순회 : A->B->D->E->C->F->G
중위 순회 : D->B->E->A->F->C->G
후위 순회 : D->E->B->F->G->C->A

from sys import stdin as s
from collections import deque

class Node: #이진 탐색 트리를 구현하기 위해선 node 클래스를 장의해야함 이 떄 노드값과 왼쪽 오른 쪽 노드를 설정
    def __init__(self,data,left_node,right_node):
        self.data=data
        self.left_node=left_node
        self.right_node = right_node


#전위 순회(preorder)        
def pre_order(node):
    print(node.data,end='') #루트 노드를 먼저 설정해주고 출력함
    if node.left_node !=None: # 탐색하는 노드의 left node가 있을 경우 다시 탐색
        pre_order(tree[node.left_node])
    if node.right_node !=None: #탐색하는 노드의 right node 가 있을 경우 다시 탐색
        pre_order(tree[node.right_node])
#중위 순회(inorder)
def in_order(node): 
    if node.left_node !=None:
        in_order(tree[node.left_node])
    print(node.data, end='') #제일 왼쪽에 있는 노드를 출력함
    if node.right_node !=None:
        in_order(tree[node.right_node])
# 후위 순회(post-order)
def post_order(node):
    if node.left_node !=None:
        post_order(tree[node.left_node])
    if node.right_node !=None:
        post_order(tree[node.right_node])
    print(node.data, end='') #가장 마지막에 있는 노드를 출력       
            
s=open('input.txt','rt')
n = int(s.readline())
tree ={}

for i in range(n):
    data,left_node, right_node = (s.readline().split())
    if left_node == ".":
        left_node = None
    if right_node ==".":
        right_node = None
    tree[data] = Node(data,left_node,right_node) #tree에 기준이 되는 값과 오른쪽 노드 값, 왼쪽 노드값을 저장
    
        
pre_order(tree['A']) #먼저 시작하는 노드의 값을 지정해줌(항상 A가 루트 노드 조건)
print()
in_order(tree['A'])
print()
post_order(tree['A'])

Ref)
이것이 취업을 위한 코딩테스트다 with Python