1. 트리(Tree)
트리(Tree)는 데이터를 부모-자식 관계를 기반으로 계층적으로 표현하는 비선형 자료구조이다.
또한, 트리는 여러 개의 노드(Node)로 구성되며, 가장 위에 있는 노드를 루트 노드 (Root Node)라 부른다. 일반적으로 각 노드는 하나 이상의 자식 노드를 가질 수 있다.
1.1 트리를 사용하는 이유
트리는 데이터를 단순히 저장하는 것보다, 계층적인 관계를 표현하거나 탐색을 효율적으로 하기 위해 사용된다.
그래서 트리는
- 컴퓨터 폴더 구조
- 조직도
같은 구조에서 자주 활용된다.
1.2 배열(Array)과의 차이점
배열과 트리를 크게 3가지를 기준으로 차이점을 정리해보았다.
| 구분 | 배열(Array) | 트리(Tree) |
| 데이터 접근 방식 | 인덱스를 통해 임의 접근 가능 | 노드를 따라 순회해야 함 |
| 크기 | 보통 고정적 | 가변적 |
| 메모리 구조 | 연속적인 메모리 공간 👉 캐시 효율이 좋은 편 |
노드가 개별적으로 연결됨 👉 추가적인 메모리 사용이 발생할 수 있음 |
2. 트리의 주요 용어 정리
트리의 주요 용어를 그림을 기준으로 하나씩 정리해보자.
🔸 노드(Node) : 트리를 구성하는 기본 요소 👉 위의 구조에서 보면 A부터 I까지 전부 노드이다
🔸 루트 노드(Root Node) : 트리의 가장 맨 상단에 있는 노드 👉 A
🔸 Parent(부모 노드) / Child Node(자식 노드)
- 부모 노드 : 자식 노드를 가지고 있는 노드
- 자식 노드 : 특정 부모 노드에 연결되어 있는 노드
👉 B : 부모 노드 / E , F : 자식 노드
🔸 Leaf Node(잎사귀 노드) : 자식 노드가 하나도 없는 노드 (차수가 0인 노드)
👉 E,F,C,I,H
🔸 깊이(Depth) : 트리의 최대 깊이 👉 3
🔸 차수(Degree) : 노드에서 뻗어 나온 자식 노드의 개수
👉 A의 차수 : 3 , B의 차수 : 2. D의 차수 : 2
🔸 트리의 차수 : 노드들의 차수 중 최대 차수 👉 3
✔️ 트리의 종류
트리에도 종류가 여러 가지 있는데, 이번 글에서는 구현할 이진 트리(Binary Tree) 를 중심으로 간단하게 정리해보려고 한다.
🔸 이진트리(Binary Tree)
– 자식이 둘 이하(차수가 2이하)인 노드로만 구성된 트리이다.
아래쪽에 구현한 이진 탐색 트리도 이진 트리의 한 종류이다.
🔸 전 이진 트리(Fulll Binary Tree)
👉 모든 노드가 0개 또는 2개의 자식 노드를 갖는 트리
👉 자식이 하나만 있는 노드는 존재 x
🔸 완전 이진 트리(Complete Binary Tree)
👉 마지막 깊이를 제외한 모든 깊이의 노드가 완전히 채워져 있는 트리, 이때 모든 노드는 왼쪽부터 채워진다.
3. 이진 트리의 순회 방식
트리를 순회하는 방법에는 전위 순회(Preorder), 중위 순회(Inorder), 후위 순회(Postorder) 가 있다.
단순한 구조의 트리라면 괜찮지만, 구조가 복잡해질수록 어떤 순서로 노드를 방문하는지 헷갈릴 수 있다.
나도 처음 전공 수업에서 이 개념을 배울 때 조금 헷갈렸었는데, 교수님께서 알려주신 방법으로 이해하니까 훨씬 쉬웠다.
그래서 이번에는 내가 이해했던 방식대로 순회 방법을 정리해보려고 한다.
3.1 전위 순회(Preorder)
전위 순회(Preorder)의 순서는 Root → Left → Right 이다.
즉, 루트 노드를 먼저 방문한 뒤, 왼쪽 서브트리 → 오른쪽 서브트리 순서로 탐색한다.
처음에는 말만 보면 조금 헷갈릴 수 있는데, 교수님께서 설명해주신 방법이 꽤 이해하기 쉽다.
전위 순회는 손가락 모양을 👉 이렇게 한다고 생각하면 된다.
그리고 손가락이 가장 먼저 닿는 노드를 방문한다고 생각하면 된다.
순회할 때, 손가락(👉)이 가장 먼저 닿는 노드를 방문한다고 생각하면 전위 순서를 이해하기 쉽다.
① 가장 먼저 손가락이 닿는 곳은 A이다.
② 그 다음 손가락을 왼쪽 아래 방향으로 내려가면 B를 만나게 된다.
③ 다시 손가락을 아래로 내려가면 D에 도착한다.
④ 이제 더 이상 내려갈 곳이 없으므로, 다시 올라와 B의 오른쪽 노드인 E로 이동한다.
⑤ 왼쪽 서브트리 순회가 끝났다면 마지막으로 오른쪽 노드 C를 방문한다.
3.2 중위 순회 (Inorder)
중위 순회(Inorder)의 순서는 Left → Root → Right이다.
즉, 왼쪽 서브트리를 먼저 방문한 뒤 현재 노드, 마지막으로 오른쪽 서브트리를 방문한다.
중위 순회에서는 손가락 모양이 👆 이라고 생각하면 이해하기 쉽다.
처음에는 조금 헷갈릴 수 있는데, 손가락이 노드의 가운데를 정확히 찌른다고 생각하면 된다.
① 먼저 손가락을 👆 모양으로 하고 트리를 왼쪽 아래 방향으로 내려간다. 그러면 가장 먼저 D를 만나게 된다
② 그 다음 다시 올라오면 B를 손가락이 가리키게 된다.
③ 계속해서 손가락을 움직여서 B의 오른쪽 노드인 E로 이동한다.
④ 왼쪽 서브트리의 순회가 끝나면 쭉 올라와 루트 노드인 A를 방문한다
⑤ 마지막으로 오른쪽 노드 C를 방문하면 중위 순회가 끝난다.
3.3 후위 순회
후위 순회의 순서는 Left -> Right -> Root 이다.
즉, 자식 노드를 전부 방문한 뒤 가장 마지막에 부모 노드를 방문하는 방식이다.
후위 순회를 할 때의 손가락 모양은 👈 이다.
① 먼저 왼쪽 아래 방향으로 내려가 D 를 방문한다.
② 이후 E 를 방문한다.
③ 이제 자식 노드를 모두 방문했기 때문에 B 를 방문한다.
④ 그 다음 오른쪽 노드인 C 를 방문한다.
⑤ 마지막으로 루트 노드 A 를 방문하면 순회가 끝난다.
4. 이진 탐색 트리(Binary Search Tree, BST) 구현
이제 직접 이진 탐색 트리(Binary Search Tree, BST) 를 파이썬으로 간단하게 구현해보았다.
✔️ 이진 탐색 트리(BST)
앞서 설명했듯이, 이진 탐색 트리는 각 노드가 최대 2개의 자식 노드(왼쪽, 오른쪽)를 가지는 트리 구조이면서 동시에 아래와 같은 규칙을 따른다.
- 왼쪽 서브트리의 값 < 부모 노드의 값
- 오른쪽 서브트리의 값 > 부모 노드의 값
즉, 데이터를 추가할 때마다 현재 노드와 값을 비교하면서 왼쪽 또는 오른쪽 위치를 결정하는 구조이다.
이번 코드에서는 이진 탐색 트리 클래스를 직접 만들고, 숫자들을 넣어본 뒤 전위, 중위, 후위 순회 결과가 어떻게 나오는지 살펴보려고 한다.
numbers 의 숫자들을 순서대로 이진탐색트리(BST)에 추가하게 되면 아래의 트리구조를 가지게 된다.
4.1 Node 클래스 만들기
트리는 여러 개의 노드(Node) 로 구성되어 있기 때문에, 먼저 노드를 표현할 클래스를 만들어주었다.
각 노드는
- 데이터 값(data)
- 왼쪽 자식 노드(left)
- 오른쪽 자식 노드(right)
를 저장하도록 구현해보았다.
# Node 클래스 만들기
class Node:
def __init__(self,data):
self.data=data
self.left=None
self.right=None
4.2 Tree 클래스 – 생성자와 노드 , 노드 추가 함수
class Tree:
def __init__(self):
self.root=None
# ✅ 노드 추가 함수
def insert(self,data):
new_node=Node(data)
if self.root is None: # 루트 노드가 비어있을 때 new_node를 루트로 설정
self.root=new_node
# root부터 시작해서 data가 들어갈 위치를 찾는다
self.insert_recurse(self.root,data)
# ======================================
# ✅ 데이터 추가를 위한 재귀 함수
def insert_recurse(self,current,data):
new_node=Node(data)
# 👉 새로 넣을 data 가 current.data보다 작을 때
if data < current.data:
if current.left is None: # current.left가 비어있으면
current.left=new_node # 그 위치애 new_node를 연결
else: # current.left가 이미 채워져 있으면
self.insert_recurse(current.left,data) # current.left 기준으로 insert_recurse 재귀함수를 실행
# 👉 새로 넣을 data 가 current.data 보다 클 때
elif data > current.data:
if current.right is None: # 만약 current.right이 비어있으면
current.right=new_node # 그 위치에 new_node를 연결
else: # 이미 current.right이 채워져 있으면 이 노드를 기준으로 다시 비교한다.
self.insert_recurse(current.right,data)
트리에 값을 추가하는 함수(insert, insert_recurse)를 구현해보았다.
코드만 보면 재귀 호출 흐림이 조금 헷갈릴 수 있어서 대표적으로 9와 17이 삽입되는 과정을 도식화해보았다.
4.3 노드 순회 파트 (중위, 전위, 후위)
트리에 노드를 추가했으니, 이제 트리에 저장된 값을 순회하면서 출력해보려고 한다.
순회 함수도 재귀 함수를 이용해서 만들었다.
# 🔹 순회 함수
# ✅ 중위 순회 함수
# Left -> Root -> Right 순으로 순회
def inorder_traversal(self):
if self.root is None: # Tree의 root가 비어있으면 비어있다는 메세지 출력
print('트리가 비어있습니다')
return
else:
print("==== inorder 순회 결과 ====")
self.inorder_recurse(self.root) # 중위 순회용 재귀함수를 실행한다.
print()
print("===========================")
# 중위 순회 재귀함수
def inorder_recurse(self,current): # 왼쪽 -> 중앙 -> 오른쪽
if current is None: # 만약 current가 None이면 return
return
else: # current가 None이 아닐 때
# 왼쪽 -> 중앙 -> 오른쪽 순서
# 왼쪽
self.inorder_recurse(current.left)
# 중앙 -> current의 data를 출력
print(current.data,end=' ' )
# 오른쪽
self.inorder_recurse(current.right)
# ✅ 전위 순회 함수
# Root -> Left -> Right 순으로 순회
def preorder_traversal(self):
if self.root is None: # 트리의 root가 None일때
print('트리가 비어있습니다') # 비어있다는 메세지 출력
return
else: # root가 None이 아닐 때
print("==== preorder 순회 결과 ====")
self.preorder_recurse(self.root)
print()
print("============================")
# ✔️ 전위 순회를 위한 재귀함수
def preorder_recurse(self,current): # 중앙 -> 왼쪽 -> 오른쪽
if current is None: # current가 None일 때
return
else: # current가 None이 아닐 때
# 중앙
print(current.data,end=' ')
# 왼쪽
self.preorder_recurse(current.left)
# 오른쪽
self.preorder_recurse(current.right)
# ✅ 후위 순회 함수
# 왼쪽 -> 오른쪽 -> 중앙
def postorder_traversal(self):
if self.root is None: # 트리가 None일 때
print('트리가 비어있습니다')
return
else:
print("==== postordr 순회 결과 ====")
self.postorder_recurse(self.root) # postorder_recurse 함수(재귀함수)를 호출한다
print()
print("============================")
def postorder_recurse(self,current): # 왼쪽 -> 오른쪽 -> 중앙
if current is None :
return
else:
# 왼쪽
self.postorder_recurse(current.left)
# 오른쪽
self.postorder_recurse(current.right)
# 중앙
print(current.data,end=' ')
코드만 보면 재귀호출 순서가 바로 보이지 않아서, 중위 순회를 기준으로 실제 함수가 어떤 순서로 호출되는 지 도식화해 보았다.
중위, 후위 순회도 이런 식으로 재귀 호출의 구조를 이해하면 된다.
4.4 실행 코드
t=Tree() # 트리 객체 t 생성
numbers=[14,3,20,9,7,17,12]
# numbers에 있는 숫자들을 이진트리에 삽입하기
for num in numbers:
t.insert(num)
# 중위 순회
t.inorder_traversal()
# 전위 순회
t.preorder_traversal()
# 후위 순회
t.postorder_traversal()
실행 결과
4.5 전체 코드
# Node 클래스 만들기
class Node:
def __init__(self,data):
self.data=data
self.left=None
self.right=None
# Tree 클래스
class Tree:
def __init__(self):
self.root=None
# ✅ 노드 추가 함수
def insert(self,data):
new_node=Node(data)
if self.root is None: # 루트 노드가 비어있을 때 new_node를 루트로 설정
self.root=new_node
# root부터 시작해서 data가 들어갈 위치를 찾는다
self.insert_recurse(self.root,data)
# ======================================
# ✅ 데이터 추가를 위한 재귀 함수
def insert_recurse(self,current,data):
new_node=Node(data)
# 👉 새로 넣을 data 가 current.data보다 작을 때
if data < current.data:
if current.left is None: # current.left가 비어있으면
current.left=new_node # 그 위치애 new_node를 연결
else: # current.left가 이미 채워져 있으면
self.insert_recurse(current.left,data) # current.left 기준으로 insert_recurse 재귀함수를 실행
# 👉 새로 넣을 data 가 current.data 보다 클 때
elif data > current.data:
if current.right is None: # 만약 current.right이 비어있으면
current.right=new_node # 그 위치에 new_node를 연결
else: # 이미 current.right이 채워져 있으면 이 노드를 기준으로 다시 비교한다.
self.insert_recurse(current.right,data)
# =====================================
# 🔹 순회 함수
# ✅ 중위 순회 함수
# Left -> Root -> Right 순으로 순회
def inorder_traversal(self):
if self.root is None: # Tree의 root가 비어있으면 비어있다는 메세지 출력
print('트리가 비어있습니다')
return
else:
print("==== inorder 순회 결과 ====")
self.inorder_recurse(self.root) # 중위 순회용 재귀함수를 실행한다.
print()
print("===========================")
# 중위 순회 재귀함수
def inorder_recurse(self,current): # 왼쪽 -> 중앙 -> 오른쪽
if current is None: # 만약 current가 None이면 return
return
else: # current가 None이 아닐 때
# 왼쪽 -> 중앙 -> 오른쪽 순서
# 왼쪽
self.inorder_recurse(current.left)
# 중앙 -> current의 data를 출력
print(current.data,end=' ' )
# 오른쪽
self.inorder_recurse(current.right)
# ✅ 전위 순회 함수
# Root -> Left -> Right 순으로 순회
def preorder_traversal(self):
if self.root is None: # 트리의 root가 None일때
print('트리가 비어있습니다') # 비어있다는 메세지 출력
return
else: # root가 None이 아닐 때
print("==== preorder 순회 결과 ====")
self.preorder_recurse(self.root)
print()
print("============================")
# ✔️ 전위 순회를 위한 재귀함수
def preorder_recurse(self,current): # 중앙 -> 왼쪽 -> 오른쪽
if current is None: # current가 None일 때
return
else: # current가 None이 아닐 때
# 중앙
print(current.data,end=' ')
# 왼쪽
self.preorder_recurse(current.left)
# 오른쪽
self.preorder_recurse(current.right)
# ✅ 후위 순회 함수
# 왼쪽 -> 오른쪽 -> 중앙
def postorder_traversal(self):
if self.root is None: # 트리가 None일 때
print('트리가 비어있습니다')
return
else:
print("==== postordr 순회 결과 ====")
self.postorder_recurse(self.root) # postorder_recurse 함수(재귀함수)를 호출한다
print()
print("============================")
def postorder_recurse(self,current): # 왼쪽 -> 오른쪽 -> 중앙
if current is None :
return
else:
# 왼쪽
self.postorder_recurse(current.left)
# 오른쪽
self.postorder_recurse(current.right)
# 중앙
print(current.data,end=' ')
t=Tree() # 트리 객체 t 생성
numbers=[14,3,20,9,7,17,12]
# numbers에 있는 숫자들을 이진트리에 삽입하기
for num in numbers:
t.insert(num)
# 중위 순회
t.inorder_traversal()
# 전위 순회
t.preorder_traversal()
# 후위 순회
t.postorder_traversal()'python' 카테고리의 다른 글
| 자료구조 - 해시 테이블 (Hash Table) (0) | 2026.06.04 |
|---|---|
| 자료구조 - 이중 연결 리스트(Doubly Linked List) (0) | 2026.06.03 |
| 자료구조- 단일 링크드 리스트 (Singly Linked List) (0) | 2026.06.01 |
| 자료구조 -큐(Queue) (0) | 2026.05.30 |
| 자료구조 - 스택(Stack) (0) | 2026.05.30 |