트리
트리는 노드의 연결형태가 재귀적으로 구현되는 추상데이터타입이다.
특징
- 하나의 노드에서 다른 노드로 이동하는 경로는 유일
- 부모 노드에서 자식 노드로 가는 길이 여러개가 존재할 수 있지 않느냐 할 수 있는데, 특정 a라는 노드에서 b라는 지정된 노드로 이동할 때 갈 수 있는 경로가 유일하다는 것이다. 이 말은 결국 분기가 되어도 다시 길이 합쳐지는 경우가 없다는 것이다.
- Acyclic하다. (Cycle이 존재하지 않는다)
- 모든 노드는 서로 연결되어 있다. (외딴 섬이 존재하지 않는다.)
- 하나의 Edge를 끊으면 두개의 Sub-Tree로 분리된다. (재귀적이다)
- Edge의 수는 [Node의 수 - 1]이다.
이진트리
이진트리는 자식노드의 수를 최대 두 개 가지는 트리를 말한다. 0개, 1개, 2개의 자식노드를 가질 수 있다.
이진트리의 종류
정 이진트리(Full binary tree)
특정 height 에서 모든 자식노드가 가득 차 있는 트리 상태를 말한다.
완전 이진트리
모든 자식노드가 왼쪽부터 차례대로 차 있는 트리 상태를 말한다.
균형 이진트리
특정 height가 주어졌을 때 height - 1 까지의 모든 트리가 가득 차 있는 트리 상태를 말한다.
이진트리의 순회
이진트리를 순회하면서 탐색하는 방법을 구현해야 한다.
3가지 방법이 있는데 preorder, inorder, postorder가 있다. preorder이 가장 중요하다.
preoder
preorder은 현재 노드 탐색 -> left 노드로 이동 -> 현재 노드 탐색 -> left 노드가 존재할 경우 다시 left로 이동 -> 존재하지 않을 경우 오른쪽 노드로 이동
이 순서를 반복하는 것이 preorder 이다. 전위 탐색이라고도 한다.
inorder
inorder은 left 노드로 이동 -> left 노드가 존재한다면 left 노드로 이동 -> 없다면 현재 노드 탐색 -> 오른쪽 노드가 존재한다면 오른쪽 노드로 이동
이 순서를 반복한다.
postorder
postorder은 left노드로 이동 -> left 노드가 존재한다면 다시 left 노드로 이동 -> 없다면 오른쪽 노드로 이동 -> 존재하면 다시 left 노드가 있는지 확인 -> 계속 left 타고 들어가다가 없으면 다시 right -> 이동할 노드가 없다면(left, right) 현재 노드를 탐색
순으로 구현되는게 postorder 순회 방식이다.
dfs(depth first search)
preorder과 똑같다. 다만 다른 것은 preorder가 데이터를 출력만 했다면 dfs는 특정 데이터를 탐색해서 해당 데이터의 인덱스를 반환한다거나, 그 값을 반환한다거나 하는 작업이 추가적으로 필요하다.
bfs(breadth first search)
height를 기준으로 모든 노드를 탐색한다. root 노드를 탐색하면 1번째 height에 있는 모든 노드를 탐색하고 2번째 height에 있는 모든 노드를 탐색하는 순으로 검색한다.
queue 자료구조를 이용해 구현한다.
구현
배열 기반 이진트리의 구현
import array
class BinaryTree:
def __init__(self, arr):
self.array = array.array('l', arr)
def preorder(self):
def preorder_traversal(index):
if index > len(self.array):
return False
else:
print(index, end=" ")
preorder_traversal(index * 2)
preorder_traversal(index * 2 + 1)
root = 1
preorder_traversal(root)
print()
def inorder(self):
def inorder_traversal(index):
if index > len(self.array):
return False
else:
inorder_traversal(index * 2)
print(index, end=" ")
inorder_traversal(index * 2 + 1)
root = 1
inorder_traversal(root)
print()
def postorder(self):
def postorder_traversal(index):
if index > len(self.array):
return False
else:
postorder_traversal(index * 2)
postorder_traversal(index * 2 + 1)
print(index, end=" ")
root = 1
postorder_traversal(root)
print()
def bfs(self, value): # 배열 기반의 경우 모든 노드가 순서대로 배열에 들어가 있으므로 for문만 돌리면 된다.
for i in range(len(self.array)):
if self.array[i] == value:
print(i)
return
print(False)
return
def dfs(self, value):
answer = -1
def dfs_traversal(index):
nonlocal answer
if index >= len(self.array):
return
if answer >= 0:
return
elif self.array[index-1] == value:
answer = index-1
return
else:
dfs_traversal(index * 2)
dfs_traversal(index * 2 + 1)
return
root = 1
dfs_traversal(root)
if answer == -1:
print(False)
else:
print(answer)노드 기반의 이진트리 구현
from _collections import deque
class Node:
def __init__(self, value, left, right):
self.value = value
self.left = left
self.right = right
class BinaryTree:
def __init__(self, array):
node_list = [Node(value, None, None) for value in array]
for ind, node in enumerate(node_list):
left = 2 * ind + 1
right = 2 * ind + 2
if left < len(node_list):
node.left = node_list[left]
if right < len(node_list):
node.right = node_list[right]
self.root = node_list[0]
def preorder(self):
def recursive(node):
print(node.value, end=" ")
if node.left == None:
return
else:
recursive(node.left)
if node.right == None:
return
else:
recursive(node.right)
recursive(self.root)
print()
def inorder(self):
def recursive(node):
if node.left == None:
print(node.value, end=" ")
return
else:
recursive(node.left)
print(node.value, end=" ")
if node.right == None:
return
else:
recursive(node.right)
recursive(self.root)
print()
def postorder(self):
def recursive(node):
if node.left == None:
print(node.value, end=" ")
return
else:
recursive(node.left)
if node.right == None:
print(node.value, end=" ")
return
else:
recursive(node.right)
print(node.value, end=" ")
recursive(self.root)
print()
def bfs(self, value): # 큐를 이용한 구현을 한다.
dq = deque([]) # 큐 라이브러리 중 deque
dq.append(self.root)
while dq: # 현재 노드에서 접근할 수 있는 모든 원소를 큐에 넣어주면 먼저 들어온 노드들을 먼저 처리하기 때문에 bfs가 구현된다.
num = dq.popleft()
if num.value == value:
return True
else:
if num.left is not None:
dq.append(num.left)
if num.right is not None:
dq.append(num.right)
return False
def dfs(self, value):
answer = False
def recursive(node):
nonlocal answer
if node.value == value:
answer = True
return
if node.left == None:
return
else:
recursive(node.left)
if node.right == None:
return
else:
recursive(node.right)
recursive(self.root)
return answer
return False
