파이썬 공부를 하다보면 데이터를 단순히 순서대로 저장하는것 뿐만 아니라
데이터간의 관계를 표현해야하는 상황도 발생한다.
예를 들어 컴퓨터의 폴더 구조, 회사의 조직도처럼
부모-자식 관계를 가지는 데이터는 일반적인 배열이나 연결리스트로 표현하는데 어려움이 있다.
이때 트리(Tree) 자료구조를 사용할 수 있다.
트리(Tree)란?
트리(Tree)는 데이터를 계층 구조로 저장하고 관리할 수 있는 자료구조이다.
이름 그대로 트리를 생각하면 쉽다.
나뭇가지가 뻗어나가는 것 처럼, 시작점에서 여러 방향으로 데이터가 연결되는 방식이다.
부모-자식 관계를 통해 데이터를 표현하는 방식으로
계층적인 데이터를 표현할 때 많이 사용되고 있는 자료구조이다.
트리의 구조
- 노드(Node) : 트리를 이루고있는 각각의 값
- 루트(Root) : 가장 상단의 시작 노드
- 부모노드(Parent) : 본인 아래에 노드를 가지고 있는 노드
- 자식노드(Child) : 부모 아래에 연결되어 있는 노드
- 리프 노드(Leaf) : 자식이 없는 맨 끝 노드
- 깊이(Depth) : 루트 노드로부터 특정 노드까지의 거리
- 높이(Height) : 트리에서 가장 깊은 노드까지의 거리
- 차수(Degree) : 한 노드가 가지고 있는 자식 노드의 개수
- 서브트리(Subtree) : 트리의 특정 노드를 루트로 하여 아래에 연결된 작은 트리
트리 왜 사용할까?
트리는 계층 관계를 표현하기 위해 사용된다.
데이터가 단순하게 일자로 나열되어 있을땐 리스트만으로 사용해도 문제가 없지만
데이터가 늘 일자로 바르게 나열되어있는것은 아니다.
데이터 사이에 위아래 관계가 있거나,
부모와 자식 관계가 있을 경우 트리구조를 사용하는것이 더 적합하다.
트리가 실제로 활용되는 예시
- 컴퓨터 폴더 구조
- 폴더 안에 여러 하위 폴더와 파일이 존재하는 계층 구조를 표현하기 위해 사용
- 회사 조직도
- 대표, 팀장, 직원등과 같이 상하 관계가 존재하는 조직 체계를 부모-자식 관계로 표현하기 위해 사용
- HTML(DOM) 구조
- HTML 태그 안에 다른 태그가 포함되는 중첩 구조를 관리하기 위해 사용
배열(Array)과 트리(Tree)의 차이점
배열과 트리는 모두 데이터를 저장하는 자료구조지만
데이터를 구성하는 방식에 차이가 존재한다.
배열의 경우 데이터를 순서대로 나열하여 저장하는 선형구조이며,
각 데이터는 인덱스를 통해 접근할 수 있다.
하지만 트리는 부모-자식 관계를 기반으로 데이터를 저장하는 계층구조로,
각 데이터는 노드를 통해 탐색할 수 있다.
| 구분 | 배열(Array) | 트리(Tree) |
| 구조 | 선형 구조 | 계층 구조 |
| 데이터 관계 | 순서만 존재 | 부모-자식 관계 존재 |
| 접근 방식 | 인덱스 사용 | 노드 탐색 |
| 데이터 표현 | 단순한 목록 | 계층적 관계 |
예를 들어 학생들의 이름을 저장하는것처럼
데이터가 순서대로 나열되어 있는경우
인덱스를 통해 쉽게 접근이 가능하기 때문에 배열이 적합하다.
# 배열 자료구조 적합
["김사과", "반하나", "오렌지", "최망고"]
하지만 회사 조직도와 같이 상하 관계가 존재하는 데이터는 트리가 더 적합하다.
# 트리 자료구조 적합
대표
├─ 개발팀장
│ ├─ 개발자A
│ └─ 개발자B
└─ 마케팅팀장
이진 트리 (Binary Tree)
이진 트리는 각각의 노드가 최대 2개의 자식 노드를 가지는 트리 자료구조이다.
왼쪽 자식노드 1개, 오른쪽 자식노드 1개를 가질 수 있으며,
자식이 최대 2개까지를 이진트리라고 하기때문에
자식이 아예 없더라도 이진트리라고 부른다.
💡 이진 트리의 특징
- 각 노드는 최대 2개의 자식 노드를 가진다.
- 왼쪽 자식과 오른쪽 자식을 구분하여 가진다.
- 다양한 트리 구조의 기본이 되는 형태이다.
완전 이진 트리 (Complete Binary Tree)
완전 이진 트리는 위에서부터 아래로, 왼쪽부터 차례대로 빈칸 없이 채워지는 이진 트리이다.
마지막 레벨을 제외한 모든 레벨은 노드가 가득 차 있어야 하며,
마지막 레벨은 일부 비어 있을 수 있지만, 왼쪽부터 채워져 있어야 한다.
A
/ \
B C
/ \ /
D E F
💡 완전 이진 트리의 특징
- 노드가 왼쪽부터 순서대로 채워진다.
- 배열로 표현하기 쉽다.
- 공간 활용 효율이 높은편이다.
포화 이진 트리 (Perfect Binary Tree)
포화 이진 트리는 모든 부모 노드가 정확히 2개의 자식 노드를 가지고 있는 이진 트리로,
노드가 동일한 깊이에 위치하고 있는 구조이다.
즉, 트리의 모든 레벨이 빈칸 없이 가득 채워져있는 형태이다.
자식 노드가 하나만 존재할 수 없으며,
리프 노드를 제외한 모든 노드는 반드시 2개의 자식노드를 가져야 한다.
A
/ \
B C
/ \ / \
D E F G
💡 포화 이진 트리의 특징
- 모든 부모 노드는 2개의 자식 노드를 가진다.
- 모든 리프 노드가 같은 깊이에 있다.
- 완전 이진 트리보다 더 엄격한 조건을 가지고 있다.
완전 이진 트리와 포화 이진 트리 무엇이 다를까?
완전 이진 트리는 마지막 레벨이 일부 비어 있더라도
왼쪽부터 순서대로 채워지기만 한다면 조건을 만족한다.
하지만 포화 이진 트리를 마지막 레벨까지 모든 노드가 채워져있어야하기 때문에
어느 위치에도 빈칸이 존재해선 안된다.
- 완전 이진 트리 : 마지막 레벨이 일부 비어도 가능
- 포화 이진 트리 : 모든 레벨이 100% 다 채워져 있어야 함
즉, 모든 포화 이진 트리는 완전 이진 트리이기도 하다.
하지만 모든 완전 이진 트리는 포화 이진트리가 아니다.
일반 트리를 파이썬 코드로 구현해보면?
1) 클래스 생성
트리의 각 노드를 표현하기 위한 클래스를 생성한다.
생성자엔 노드가 저장할 데이터(data)와 자식 노드들을 저장할 리스트(children)을 만들어준다.
리스트로 만드는 이유?
일반 트리는 하나의 노드가 여러 개의 자식 노드를 가질 수 있기 때문에 자식 노드를 리스트로 관리한다.
class TreeNode:
def __init__(self, data):
# 노드가 가지고 있는 값
self.data = data
# 자식 노드를 저장하는 리스트
self.children = []
2) 자식노드 추가 메서드
부모노드에 자식노드를 추가할 수 있는 메서드를 생성한다.
# 자식노드 생성 메서드
def add_child(parent, child):
# parent 노드의 children 리스트에 child 노드 추가
parent.children.append(child)
3) 트리 출력
트리 구조를 계층적으로 출력하기 위해
현재 깊이(level)만큼 들여쓰기를 적용하는 함수를 추가하였다.
# 트리 출력 메서드
def print_tree(node, level):
# 현재 깊이(level)만큼 빈칸 들여쓰기
space = ' ' * level
# 현재 노드값 출력
print(space + str(node.data))
# 현재 노드의 자식들을 하나씩 꺼냄
for child in node.children:
# 자식 노드는 한 단계 안쪽으로 들어가서 출력
print_tree(child, level + 4)
4) 전체 구현하기
위에서 만든 클래스와 메서드들을 이용하여 일반 트리 구조 생성!
#루트노드
root = TreeNode('A')
#A의 자식이 될 노드
node_b = TreeNode('B')
node_c = TreeNode('C')
node_d = TreeNode('D')
#B의 자식이 될 노드
node_e = TreeNode('E')
node_f = TreeNode('F')
#C의 자식이 될 노드
node_g = TreeNode('G')
# A 밑에 연결
add_child(root,node_b)
add_child(root,node_c)
add_child(root,node_d)
# B 밑에 연결
add_child(node_b, node_e)
add_child(node_b, node_f)
#c 밑에 연결
add_child(node_c, node_g)# 실행 코드
print("일반 트리구조")
print_tree(root, 0)실행 결과 ▶
트리 순회(Tree Traversal), 파이썬으로 트리 순회 구현하기
트리 순회(Tree Traversal)는 트리에 저장된 모든 노드를 한 번씩 방문하는 과정을 말한다.
배열의 경우 인덱스를 이용하여 순서대로 접근할 수 있지만
트리는 부모-자식 관계로 연결되어 있기 때문에 특정한 규칙에 따라 노드를 방문한다.
대표적으로 전위 순회(Preorder), 중위 순회(Inorder), 후위 순회(Postorder)가 있다.
# 순회 예시 트리
A
/ \
B C
/ \ / \
D E F G전위 순회 (Preorder Traversal)
전위 순회는 부모 노드를 가장 먼저 방문한 뒤
차례대로 왼쪽 끝까지 같다가 그다음 오른쪽을 보는 방식이다.
# 방문 순서
부모 → 왼쪽 자식 → 오른쪽 자식
# 순회 결과
A → B → D → E → C → F → G
전위 순회 단계별 설명
- 가장 먼저 루트 A를 읽는다.
- A의 왼쪽 서브트리로 가서 B를 읽는다.
- B의 왼쪽 자식 D를 읽는다.
- 다시 B로 돌아와 오른쪽 자식 E를 읽는다
- 왼쪽 서브트리는 모두 읽었기에 오른쪽 서브트리로 이동하여 C를 읽는다.
- C의 왼쪽 자식 F를 읽는다.
- 다시 C로 돌아와 오른쪽 자식 G를 읽는다.
📌전위 순회 메서드 생성
전위 순회는 루트 → 왼쪽 → 오른쪽 순서로 탐색하기 때문에
노드값을 출력하고 왼쪽 자식, 오른쪽 자식 순서로 순회하는 구조로 메서드를 구현한다.
# 전위 순회(preorder)
def preorder(node):
if node is None:
return #None에 도달하면 끝
# 1. 현재 노드값 출력
print(node.data, end=' ')
# 2. 왼쪽 자식 순회
preorder(node.left)
# 3. 오른쪽 자식 순회
preorder(node.right)
중위 순회 (Inorder Traversal)
중위 순회는 가장 왼쪽의 자식을 먼저 방문한 뒤
부모노드를 향해 올라가며 부모노드를 방문하고 마지막으로 오른쪽 자식을 방문하는 방식이다.
# 방문 순서
왼쪽 자식 → 부모 → 오른쪽 자식
# 순회 결과
D → B → E → A → F → C → GTIP : 중위 순회는 이진 탐색 트리(BST)에서 사용할 경우 데이터를 오름차순으로 출력이 가능하다.
중위 순회 단계별 설명
- 루트 A를 바로 읽지 않고 왼쪽 서브트리로 이동한다.
- 먼저 B의 왼쪽 자식 D를 읽는다.
- 그 다음 부모 B를 읽는다.
- 그리고 B의 오른쪽 자식 E를 읽는다.
- 왼쪽 서브트리 방문이 끝났으므로 루트 A를 읽는다.
- 오른쪽 서브트리로 넘어가 C의 왼쪽 자식 F를 읽는다.
- 그 다음 부모 C를 읽는다.
- 마지막으로 부모 C의 오른쪽 자식 G를 읽는다.
📌중위 순회 메서드 생성
중위 순회는 왼쪽 → 루트 → 오른쪽 순서로 탐색하기 때문에
왼쪽 자식을 먼저 방문한 뒤 현재 노드를 방문하고,
마지막으로 오른쪽 자식을 방문하는 구조로 구현한다.
# 중위 순회(inorder)
def inorder(node):
if node is None:
return
# 1. 왼쪽 자식 순회
inorder(node.left)
# 2. 현재 노드값 출력
print(node.data, end=' ')
# 3. 오른쪽 자식 순회
inorder(node.right)후위 순회 (Postorder Traversal)
후위 순회는 자식 노드를 모두 방문한 뒤
가장 마지막에 부모 노드를 방문하는 방식이다.
# 방문 순서
왼쪽 자식 → 오른쪽 자식 → 부모
# 순회 결과
D → E → B → F → G → C → A
후위 순회 단계별 설명
- 왼쪽 서브트리로 이동한다.
- B의 왼쪽 자식 D를 읽는다.
- B의 오른쪽 자식 E를 읽는다.
- B의 자식방문이 끝났으므로 부모 B를 읽는다.
- 왼쪽 서브트리 방문이 끝났으므로 오른쪽 서브트리로 이동한다.
- C의 왼쪽 자식 F를 읽는다.
- C의 오른쪽 자식 G를 읽는다.
- C의 자식 방문이 끝났으므로 부모 C를 읽는다.
- 마지막으로 루트 A를 읽는다.
📌후위 순회 메서드 생성
후위 순회는 왼쪽 → 오른쪽 → 루트 순서로 탐색하기 때문에
왼쪽 자식과 오른쪽 자식을 먼저 방문한 뒤,
마지막으로 현재 노드를 방문하는 구조로 구현한다.
# 후위 순회(postorder)
def postorder(node):
if node is None:
return
# 1. 왼쪽 자식 순회
postorder(node.left)
# 2. 오른쪽 자식 순회
postorder(node.right)
# 3. 현재 노드값 출력
print(node.data, end=' ')순회 파이썬으로 구현하기
순회 과정을 확인하기 위한 간단한 이진 트리를 생성하고,
각 순회 방식을 파이썬 코드로 구현하여 실제로 순회되는 방식을 볼 수 있다.
# 순회확인용 노드 클래스
class Node:
def __init__(self, data):
self.data = data
# 왼쪽 자식 노드
self.left = None
# 오른쪽 자식 노드
self.right = None
# 전위 순회 : 루트 → 왼쪽 → 오른쪽
def preorder(node):
if node is None:
return #None에 도달하면 끝
# 1. 현재 노드값 출력
print(node.data, end=' ')
# 2. 왼쪽 자식 순회
preorder(node.left)
# 3. 오른쪽 자식 순회
preorder(node.right)
# 중위 순회 : 왼쪽 → 루트 → 오른쪽
def inorder(node):
if node is None:
return
# 1. 왼쪽 자식 순회
inorder(node.left)
# 2. 현재 노드값 출력
print(node.data, end=' ')
# 3. 오른쪽 자식 순회
inorder(node.right)
# 후위 순회 : 왼쪽 → 오른쪽 → 루트
def postorder(node):
if node is None:
return
# 1. 왼쪽 자식 순회
postorder(node.left)
# 2. 오른쪽 자식 순회
postorder(node.right)
# 3. 현재 노드값 출력
print(node.data, end=' ')# 예시 트리 만들기
root = Node('A')
root.left = Node('B')
root.right = Node('C')
root.left.left =Node('D')
root.left.right = Node('E')
root.right.left = Node('F')
root.right.right = Node('G')
# 전위 순회 결과
print("전위 순회 결과")
preorder(root)
# 중위 순회 결과
print("\n중위 순회 결과")
inorder(root)
# 후위 순회 결과
print("\n후위 순회 결과")
postorder(root)실행결과 ▶
순회 정리
- 전위 순회 : 부모를 먼저 본다. (루트 → 왼쪽 → 오른쪽)
- 중위 순회 : 부모를 중간에 본다. (왼쪽 → 루트 → 오른쪽)
- 후위 순회 : 부모를 마지막에 본다. (왼쪽 → 오른쪽 → 루트)
'Python > 자료구조 & 알고리즘' 카테고리의 다른 글
| [자료구조와 알고리즘] 공간 복잡도 (0) | 2026.06.07 |
|---|---|
| [자료구조] 해시 테이블(Hash Table), 해시 함수, 해시 충돌, 해결방법 (0) | 2026.06.04 |
| [자료구조와 알고리즘] 시간 복잡도, 빅오 표기법 (0) | 2026.06.04 |
| [자료구조] 선형 리스트(Linear List), 연결 리스트(Linked List), 이중 연결 리스트(Doubly Linked List) (1) | 2026.06.01 |
| [자료구조] 배열(Array), 스택(Stack), 큐(Queue) 정리 (0) | 2026.05.30 |