트리(Tree)
트리(Tree)의 개념
트리는 비선형 자료구조의 하나로 그래프의 특수한 형태 중 하나이다. 그래프는 후에 정리할 예정이다.
트리는 위의 사진처럼 간선들이 모두 방향성을 갖고, 어떤 정점을 가리키는 정점의 개수는 최대 1개이다. 어떤 정점에서 다른 정점으로 이동할 수 있는 경로는 1개이며 사이클(순환)을 갖지 않는다.
루트 노드(Root Node)
트리에서 다른 어떠한 정점도 가리키지 않는 정점을 루트 노드라고 한다. 그림의 경우 'F'가 루트 노드이다. 그리고 루트 노드로부터의 거리를 깊이라고 한다.
부모노드(Parent Node), 자식 노드(Child Node)
어떤 정점 A가 다른 정점 B를 가리킬 때 A를 B의 부모 노드라고 하고, B를 A의 자식 노드라고 한다.
예를 들면 위 그림에서 D는 C의 부모 노드이고, E는 D의 자식 노드이다.
리프 노드(Leaf Node)
가리키는 정점이 없는 정점들을 리프 노드라고 한다. A,C,E,B가 해당한다.
트리(Tree)의 종류
1. 이진 트리
각 정점들이 자식 노드를 최대 2개까지만 갖는 트리를 말한다.
2. 포화 이진 트리
리프 노드를 제외한 모든 정점이 항상 자식을 2개씩 갖고 있으면서 모든 리프 노드의 깊이가 동일한 트리를 말한다.
포화 이진 트리의 높이를 h라고 할 때, 정점의 개수는 항상 2^h -1 개이다.
3. 완전 이진 트리
마지막 깊이를 제외한 모든 정점이 완전히 채워져 있고, 마지막 깊이의 정점들이 가능한 왼쪽에 있는 트리를 말한다.
완전 이진 트리의 높이가 h일 떄 정점의 개수는 2^(h-1)개 이상 2^h -1 개 이하이다.
4. 전 이진 트리
리프 노드를 제외한 모든 노드들이 두 개의 자식 노드를 갖고 있는 이진 트리를 말한다.
즉, 모든 정점은 0개 또는 2개의 자식 노드를 갖는다.
트리(Tree)의 구현
트리에서 노드는 다음과 같이 정의되었다.
class Node:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
def __str__(self):
return str(self.data)
class Tree:
def __init__(self):
self.root = None트리(Tree) 순회
DFS(깊이 우선 탐색)
1. 전위 순회(Preorder)
루트 방문 -> 왼쪽 서브 트리 순회 -> 오른쪽 서브 트리 순회
2. 중위 순회(Inorder)
왼쪽 서브 트리 순회 -> 루트 방문 -> 오른쪽 서브 트리 순회
3. 후위 순회(Postorder)
DFS는 재귀 호출을 사용하는 알고리즘이다. 따라서 아래와 같이 구현한다.
def preorderTraversal(self, node):
print(node, end='')
if not node.left == None : self.preorderTraversal(node.left)
if not node.right == None : self.preorderTraversal(node.right)
def inorderTraversal(self, node):
if not node.left == None : self.inorderTraversal(node.left)
print(node, end='')
if not node.right == None : self.inorderTraversal(node.right)
def postorderTraversal(self, node):
if not node.left == None : self.postorderTraversal(node.left)
if not node.right == None : self.postorderTraversal(node.right)
print(node, end='')이진트리 전체 소스코드
class Node:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
def __str__(self):
return str(self.data)
class Tree:
def __init__(self):
self.root = None
def preorderTraversal(self, node):
print(node, end='')
if not node.left == None : self.preorderTraversal(node.left)
if not node.right == None : self.preorderTraversal(node.right)
def inorderTraversal(self, node):
if not node.left == None : self.inorderTraversal(node.left)
print(node, end='')
if not node.right == None : self.inorderTraversal(node.right)
def postorderTraversal(self, node):
if not node.left == None : self.postorderTraversal(node.left)
if not node.right == None : self.postorderTraversal(node.right)
print(node, end='')
def makeRoot(self, node, left_node, right_node):
if self.root == None:
self.root = node
node.left = left_node
node.right = right_node
if __name__ == "__main__":
node = []
node.append(Node('1'))
node.append(Node('2'))
node.append(Node('3'))
node.append(Node('4'))
node.append(Node('5'))
node.append(Node('6'))
node.append(Node('7'))
m_tree = Tree()
for i in range(int(len(node)/2)):
m_tree.makeRoot(node[i],node[i*2+1],node[i*2+2])
print( '전위 순회 : ', end='') ; m_tree.preorderTraversal(m_tree.root)
print('\n' + '중위 순회 : ', end='') ; m_tree.inorderTraversal(m_tree.root)
print('\n' + '후위 순회 : ', end='') ; m_tree.postorderTraversal(m_tree.root)BFS(너비 우선 탐색)
위, 왼쪽 순으로 방문한다.
BFS는 큐 자료구조를 이용하여 구현한다. 이전에 정리한 큐에 대한 게시물을 참고하길 바란다.
BFS 구현 전체 소스코드
from collections import deque
# BFS
def bfs(graph, start, visited):
# 큐 구현을 위해 deque라이브러리 사용
queue = deque([start])
# 탐색 시작 노드를 방문 처리
visited[start] = True
# 큐가 빌 때까지 반복
while queue:
# 큐에서 하나의 원소를 꺼내서 출력
n = queue.popleft()
print(n, end='')
# 꺼낸 원소와 인접노드 확인
for i in graph[n]:
# 아직 방문하지 않은 노드라면
if not visited[i]:
queue.append(i)
visited[i]=True
# 2차원 맵정보 입력받기
graph=[
[], # 0번 노드 비우기
[2,3,8], #1번 노드와 연결된 2,3,8노드
[1,7],
[1,4,5],
[3,5],
[3,4],
[7],
[2,6,8],
[1,7]
]
# 방문 정보
visited = [False]*(8+1) #(총 노드의 갯수)+인덱스 0
# bfs호출
bfs(graph, 1, visited)트리(Tree) 사용하기
이진 탐색 트리
이진 탐색 트리는 항상 정렬된 상태를 유지하는 자료구조이다. 어떤 정점의 왼쪽 서브 트리는 그 정점보다 같거나 작은 정점들로만, 오른쪽 서브 트리는 그 정점의 값보다 큰 정점들로만 이루어져 있다.
이후 추가 예정!
사진 출처
- 구글 검색
- 엘리스 수업자료
참고 문헌
