TIL_37 : 트리

🙄 트리

---

➡ 트리란?

• 데이터의 상-하 관계를 저장하는 자료 구조
• 링크드 리스트처럼 데이터와 다음 노드를 가리키는 레퍼런스를 가짐
• 트리 노드는 하위 관계가 있는 노드들을 가리키는 레퍼런스를 가짐

➡ 트리 용어

• root 노드 : 트리에서 가장 위에 있는 노드, 트리의 시작 노드
• 부모 노드 : 특정 노드의 직속 상위 노드
• 자식 노드 : 특정 노드의 직속 하위 노드
• 형제 노드 : 같은 부모를 갖는 노드
• leaf 노드 : 자식 노드를 갖고 있지 않은, 가장 말단에 있는 노드
• 깊이 : 특정 노드가 root 노드에서 떨어져 있는 거리
• 레벨 : 깊이 + 1, 특정 깊이인 노드들을 묶어서 표현할 때 사용
• 높이 : 트리에서 가장 깊이 있는 노드의 깊이
• 부분 트리 : 현재 트리의 일부분을 이루고 있는 더 작은 트리

➡ 트리의 활용

• 계층적 관계가 있는 데이터를 컴퓨터에서 사용
• 컴퓨터 과학의 다양한 문제들을 기발하게 해결할 수 있음
  ex) 정렬, 압축
• 다양한 추상 자료형 구현
  ex) 딕셔너리, 세트, 우선순위 큐

🙄 이진 트리

---

➡ 이진 트리란?

• 각 노드가 최대 2개의 자식 노드를 가질 수 있는 트리
• 노드마다 자식 노드가 최대 두 개씩 밖에 없기 때문에 두 노드를 왼쪽 자식, 오른쪽 자식으로 구별

➡ 이진 트리 구현

class Node:
    """이진 트리 노드 클래스"""

    def __init__(self, data):
        """데이터와 두 자식 노드에 대한 레퍼런스를 갖는다"""
        self.data = data
        self.left_child = None
        self.right_child = None

# 노드 인스턴스 생성
root_node = Node(2)
node_B = Node(3)
node_C = Node(5)
node_D = Node(7)
node_E = Node(11)

# B와 C를 root 노드의 자식으로 지정
root_node.left_child = node_B
root_node.right_child = node_C

# D와 E를 B의 자식으로 지정
node_B.left_child = node_D
node_B.right_child = node_E

# root 노드에서 왼쪽 자식 노드 받아오기
test_node_1 = root_node.left_child

print(test_node_1.data)

# 노드 B의 노드에서 오른쪽 자식 노드 받아오기
test_node_2 = node_B.right_child

print(test_node_2.data)

# 3
# 11

➡ 이진 트리 종류

정 이진 트리 (Full Binary Tree)

• 모든 노드가 2개 또는 0개의 자식을 갖는 이진 트리

완전 이진 트리 (Complete Binary Tree)

• 노드의 깊이를 레벨이라고 할 때, 마지막 직전의 레벨까지 모든 노드들이 다 채워진 트리
• 마지막 레벨에서는 노드들이 왼쪽부터 오른쪽 방향으로 다 채워져야 함

완전 이진 트리의 높이

• 저장된 노드가 $n$개라고 할 때, 높이는 항상 $lg(n)$이 비례함

포화 이진 트리 (Perfect Binary Tree)

• 모든 레벨이 빠짐없이 다 노드로 채워져 있는 트리
• 정 이진 트리와 완전 이진 트리의 특성을 모두 가짐
• 트리의 높이를 $h$, 노드 수를 $n$이라고 하면 관계는
  $n= 2^h*2-1$

🙄 트리 순회

---

➡ 순회란?

• 자료 구조에 저장된 모든 데이터를 도는 것
• 선형적 자료 구조를 순회할 때는 보통 반복문을 쓰지만, 트리에서는 재귀 함수 사용

트리 순회의 3가지 기본 동작

1. 재귀적으로 왼쪽 부분 트리 순회
2. 재귀적으로 오른쪽 부분 트리 순회
3. 현재 노드 데이터를 출력

👉 순서를 어떻게 하냐에 따라 순회가 조금씩 달라짐

➡ 트리 순회 : pre-order

1. 현재 노드 데이터를 출력
2. 재귀적으로 왼쪽 부분 트리 순회
3. 재귀적으로 오른쪽 부분 트리 순회

➡ 트리 순회 : post-order

1. 재귀적으로 왼쪽 부분 트리 순회
2. 재귀적으로 오른쪽 부분 트리 순회
3. 현재 노드 데이터를 출력

➡ 트리 순회 : in-order

1. 재귀적으로 왼쪽 부분 트리 순회
2. 현재 노드 데이터를 출력
3. 재귀적으로 오른쪽 부분 트리 순회

👉 트리를 순회하면 노드들 사이에 선형적 순서를 만들 수 있다

class Node:
    """이진 트리 노드를 나타내는 클래스"""

    def __init__(self, data):
        """이진 트리 노드는 데이터와 두 자식 노드에 대한 레퍼런스를 갖는다"""
        self.data = data
        self.left_child = None
        self.right_child = None

def traverse_inorder(node):
    """in-order 순회 함수"""
  
    if node is not None:
        traverse_inorder(node.left_child)
        print(node.data)
        traverse_inorder(node.right_child)
        
    
# 여러 노드 인스턴스 생성
node_A = Node("A")
node_B = Node("B")
node_C = Node("C")
node_D = Node("D")
node_E = Node("E")
node_F = Node("F")
node_G = Node("G")
node_H = Node("H")
node_I = Node("I")

# 생성한 노드 인스턴스들 연결
node_F.left_child = node_B
node_F.right_child = node_G

node_B.left_child = node_A
node_B.right_child = node_D

node_D.left_child = node_C
node_D.right_child = node_E

node_G.right_child = node_I

node_I.left_child = node_H

# 노드 F를 root 노드로 만든다
root_node = node_F

# 만들어 놓은 트리를 in-order로 순회한다
traverse_inorder(root_node)

# A
# B
# C
# D
# E
# F
# G
# H
# I