🌳 Tree

개념

• 노드(node)와 간선(edge)로 이루어진 자료구조
• 데이터가 바로 아래에 있는 하나 이상의 데이터에 무방향으로 연결된 계층적 자료구조

🌿 특징

• 부모-자식 관계로 표현
• 단방향 그래프의 일종
  • 하나의 뿌리로부터 가지가 사방으로 뻗은 형태가 나무와 닮아서 Tree 구조라고 부름
• 비선형 구조
  • 하나의 데이터 아래에 여러 개의 데이터가 존재할 수 있음
• 계층적으로 표현되고 아래로만 뻗어나가기 때문에 사이클 X
  • 사이클이 있으면 그래프
• 루트(Root)라는 하나의 꼭짓점 데이터를 시작으로 여러 개의 데이터를 간선(edge)로 연결
• 두 개의 노드가 상하 계층으로 연결되면 부모/자식 관계를 가짐
• 루트에서 한 노드로 가는 경로는 오직 하나
• 노드의 개수 N개, 간선의 개수 N-1개

🌿 용어

• 깊이 (Depth)
  • 루트로부터 하위 계층의 특정 노드까지의 거리
  • 루트 노드에서 해당 노드까지 도달하는데 사용한 간선(edge)의 개수

• 레벨 (Level)
  • 같은 깊이를 가지고 있는 노드를 묶어서 레벨로 표현
  • 노드의 깊이 + 1

• 높이 (Height)
  • 트리 구조에서 리프 노드를 기준으로 루트까지의 높이
  • 깊이 중 최댓값

• 크기 (Size)
  • 트리에 포함된 모든 노드의 개수

• 차수 (Degree)
  • 노드의 자식 수

• 서브 트리 (Sub Tree)
  • 트리 구조의 root에서 뻗어 나오는 큰 트리의 내부에 트리 구조를 갖춘 작은 트리

• 노드 (Node)
  • 트리 구조를 이루는 모든 개별 데이터

• 루트 노드 (Root Node)
  • 트리 구조의 시작점이 되는 노드
  • 트리의 최상위 노드
  • 유일함

• 부모 노드 (Parent Node)
  • 두 노드가 상하관계로 연결되어 있을 때 상대적으로 루트에서 가까운 노드
  • 부모-자식 관계에서 상위 계층에 있는 노드
  • 상위 계층에 있을수록 노드의 깊이, 레벨 ↓

• 자식 노드 (Child Node)
  • 두 노드가 상하관계로 연결되어 있을 때 상대적으로 루트에서 먼 노드
  • 부모-자식 관계에서 하위 계층에 있는 노드

• 내부 노드 (Internal / Nonterminal Node)
  • 자식이 있는 노드

• 외부 노드 (단말 노드, 잎새 노드, Leaf / External / Terminal Node)
  • 트리 구조의 끝 지점이고 자식 노드가 없는 노드

• 형제 노드 (Sibling Node)
  • 같은 레벨에 나란히 있는 노드
  • 부모가 동일한 노드

• 조상 노드
  • 해당 노드의 부모 노드로부터 루트 노드까지 가는 경로에 존재하는 노드들

• 후손 노드
  • 해당 노드를 루트로 하는 서브 트리에 있는 모든 노드

종류

이진 탐색 트리 (Binary Search Tree)

개념

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

특징

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

순회 (Traversal)

• 트리 자료구조에 포함된 노드를 특정 방법으로 한 번씩 방문하는 방법
  

1. 전위 순회 (pre-order traverse)

1. 현재 노드 방문
2. 왼쪽 자식 탐색
3. 오른쪽 자식 탐색

• 방문 순서 : A - B - D - E - H - C - F - G

2. 중위 순회 (in-order traverse)

1. 왼쪽 자식 탐색
2. 현재 노드 방문
3. 오른쪽 자식 탐색

• 방문 순서 : D - B - H - E - A - F - C - G

3. 후위 순회 (post-order traverse)

1. 왼쪽 자식 탐색
2. 오른쪽 자식 탐색
3. 현재 노드 방문

• 방문 순서 : D - H - E - B - F - G - C - A

구현 (Python)

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:
    	in_order(tree[node.left_node])
    print(node.data, end=' ')
    if node.right_node != None:
    	in_order(tree[node.right_node])

# 후위 순회 (Postorder Traversal)
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)