[자료구조 멘토링] 트리 (feat.Python)

1. 트리란?

트리는 계층적 구조를 가진 비선형 자료구조로, 노드와 간선으로 이루어져 있다. 트리는 하나의 루트 노드를 중심으로 여러 개의 자식 노드와 부모 노드로 연결된다. 

 

2. 트리의 기본 용어

https://engineerinsight.tistory.com/316

루트 노드 - 트리의 최상위 노드

부모 노드 - 자식 노드를 가지는 노드

자식 노드 - 부모 노드로 부터 연결된 하위 노드

형제 노드 - 같은 부모를 가지는 노드

리프 노드 - 자식 노드가 없가 없는 노드

서브 트리 - 트리의 일부를 이루는 작은 트리

레벨 - 루트 노드를 기준으로 특정 노드까지의 깊이

높이 - 트리의 최대 레벨

 

3. 이진 트리

https://jiwondh.github.io/2017/10/15/tree/

3-1. 완전 이진트리

마지막 레벨을 제외한 모든 레벨이 노드로 가득 차있음

마지막 레벨의 노드는 왼쪽부터 순서대로 채워짐

3-2. 포화 이진트리

모든 노드가 두 개의 자식 노드를 가지거나, 하나도 가지지 않음

3-3. 편향 이진트리

모든 노드가 한쪽 방향으로만 연결된 트리

 

3-4. 이진트리의 순회

대표적인 방법으로는 아래와 같이 있다.

https://m.blog.naver.com/rlakk11/60159303809

전위 순회 ( Root → Left → Right ) - 0 1 3 7 8 4 9 10 2 5 11 6

중위 순회 ( Left → Root → Right ) - 7 3 8 1 9 4 10 0 11 5 2 6

후위 순회 ( Left → Right → Root ) - 0 1 2 3 4 5 6 7 8 9 10 11

 

4. 파이썬에서 트리 표현하기

트리는 다양한 방법으로 표현할 수 있다. 파이썬에서는 클래스를 사용한 노드 기반 트리 표현이 일반적이지만, 리스트, 딕셔너리, 네임드 튜플 등을 활용하는 방식도 있다.

 

대표적으로 클래스를 사용한 트리

# 트리 클래스 정의
class Node:
    def __init__(self, value):
        self.value = value
        self.left = None  # 왼쪽 자식 노드
        self.right = None  # 오른쪽 자식 노드

# 트리 생성
root = Node("A")
root.left = Node("B")
root.right = Node("C")
root.left.left = Node("D")
root.left.right = Node("E")
root.right.right = Node("F")

# 트리 구조:
#        A
#       / \
#      B   C
#     / \   \
#    D   E   F