[이코테]트리

Coding Test 12

이코테 12

1. 트리(Tree)

• 트리란? 계층적인 구조를 표현할 때 사용할 수 있는 자료구조
• 트리 관련 용어

  루트 노드 : 최상위 노드
  단말 노드 : 자식이 없는 노드
  크기 : 트리에 포함된 모든 노드 개수(간선은 노드-1)
  깊이 : 루트 노드부터의 거리
  높이 : 깊이 중 최댓값
  차수 : 각 노드의 (자식 방향) 간선 개수

---

2. 이진 탐색 트리 (Binary Search Tree)

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

3. 트리의 순회 (Tree Traversal)

• 전위 순회 : 루트 -> 왼쪽 자식 -> 오른쪽 자식
• 중위 순회 : 왼쪽 자식 -> 루트 -> 오른쪽 자식
• 후위 순회 : 왼쪽 자식 -> 오른쪽 자식 -> 루트

파이썬 코드

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

#전위 순회(Preorder Traversal)
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])

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

#후위 순회(Postorder Traversal)
def post_order(node) :
  if node.left_node != None:
    pre_order(tree[node.left_node])
  if node.right_node != None:
    pre_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'])

입력 예시

7 A B C B D E C F G D None None E None None F None None G None None

출력 예시

A B D E C F G D B E A F C G D E B F G C A