[자료구조] 트리(Tree)

트리(Tree)

계층적인 구조를 표현할 때 사용

 

 

루트 노드 : 부모가 없는 최상위 노드

단말 노드 : 자식이 없는 노드

크기 : 트리에 포함된 모든 노드의 개수

깊이 : 루트 노드부터의 거리

높이 : 깊이 중 최댓값

차수 : 각 노드의 간선 개수

 

트리의 크기가 N일 때, 전체 간선의 개수는 N - 1개

 

 

이진 탐색이 동작에 효율적임

이진 탐색 트리의 특징 : 왼쪽 자식 노드 < 부모 노드 < 오른쪽 자식 노드

(부모 노드보다 왼쪽 자식 노드가 작음, 부모 노드보다 오른쪽 자식 노드가 큼)

 

 

 

트리 순회 방법

 

 

 

전위 순회 : 루트 먼저 방문

중위 순회 : 왼쪽 자식 방문 뒤 루트 방문

후위 순회 : 왼쪽 - 오른쪽 - 루트

 

 

 

 

class Node:
  def __init__(self, data, left_node, right_node):
    self.data = data
    self.left_node = left_node
    self.right_node = right_node

# 전위순회
def pre_order(node):
  print(node.data, end=' ')
  if node.left_node != None:
    pre_order(tree[node.left_node])
  if node.right_node != None:
    pre_order(tree[node.right_node])

# 중위순회
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])

# 후위순회
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 = ' ')
    
n = int(input())
tree = {}

for i in range(n):
  data, left_node, right_node = input().split()
  if left_node == 'None':
    left_node = None
  if right_node == 'None':
    right_node = None
  tree[data] = Node(data, left_node, right_node)

pre_order(tree['A'])
print()
in_order(tree['A'])
print()
post_order(tree['A'])