트리
크리스마스 트리
트리란?
트리는 계층적인 구조를 나타내는 자료구조이다. 뒤집어진 나무를 생각하면 된다.
트리의 용어
트리는 다음과 같이 생겼는데 각 하나의 원을 노드라고 부른다. 노드는 linkedlist에서도 사용해봐서 알 것이라 생각한다. 사실 트리는 또다른 형태의 linkedlist라고 봐도 무방할지도 모른다.
A노드는 Root node, 즉 뿌리노드라고 부른다. 그리고 E, F, J, K, H, I 등 각 말단에 있는 노드는 말단노드 혹은 leaf node라고 부른다.
B는 E, F의 부모노드이며, E와 F는 서로의 형제노드이다.
트리의 깊이를 레벨 또는 높이라고 부른다. (책에 따라 루트가 0 혹은 1에서 시작한다).
이진 트리
Binary트리는 모든 노드가 2개의 서브트리를 가지는 트리이다. 이때 서브트리는 공집합일 수도 있다. 이진트리는 자식간에도 순서가 있어서 왼쪽 자식, 오른쪽 자식을 구분해야한다.
이진 트리의 종류
포화 이진 트리
모든 레벨의 노드가 가득차 있는 이진트리이다.
이때 깊이를 h라 할때, 전체 노드의 갯수는 summation for i in range(1~h) 2^h 이다.
완전 이진 트리
노드가 왼족부터 순서대로 차 있는 상태의 이진트리를 말한다. 포화처럼 가득 차 있을 필요는 없으나, 중간에 비어있는 공간이 있어서는 안된다.
이진트리의 구현
이진트리는 배열, 혹은 노드를 통한 링크를 이용해 구현할 수 있다. 배열방식은 추후 다른 트리에서 다루도록 하고
from CircularQueue import *
class TNode:
def __init__(self, data, left, right):
self.data = data
self.left = left
self.right = right
def __str__(self):
return str(self.data)
class BinaryTree:
def __init__(self):
self.root = None
def isEmpty(self):
return self.root is None
def clear(self):
self.root = None
def preorder(self, node):
if node is not None:
print(node.data, end=' ')
self.preorder(node.left)
self.preorder(node.right)
def inorder(self, node):
if node is not None:
self.inorder(node.left)
print(node, end=' ')
self.inorder(node.right)
def postorder(self, node):
if node is not None:
self.postorder(node.left)
self.postorder(node.right)
print(node.data, end=' ')
def levelorder(self, root):
qu = CircularQueue()
qu.enqueue(root)
while not qu.isEmpty():
node = qu.dequeue()
if node is not None:
print(node.data, end=' ')
qu.enqueue(node.left)
qu.enqueue(node.right)
def count_node(self, n):
if n is None:
return 0
else:
return 1 + self.count_node(n.left) + self.count_node(n.right)
def count_leaf(self, n):
if n is None:
return 0
elif n.left is None and n.right is None:
return 1
else:
return self.count_leaf(n.left) + self.count_leaf(n.right)
def calc_height(self, n):
if n is None:
return 0
hleft = self.calc_height(n.left)
hright = self.calc_height(n.right)
if hleft > hright:
return hleft + 1
else:
return hright + 1
# ----------------------------------------------------------------
# Driver code
# Creating Tree
g = TNode('G', None, None)
h = TNode('H', None, None)
d = TNode('D', None, None)
f = TNode('F', None, None)
e = TNode('E', g, h)
c = TNode('C', e, f)
b = TNode('B', d, None)
a = TNode('A', b, c)
T = BinaryTree()
print("In-Order : ", end='')
T.inorder(a)
print()
print("Pre-Order : ", end='')
T.preorder(a)
print()
print("Post-Order : ", end='')
T.postorder(a)
print()
print("Level-Order : ", end='')
T.levelorder(a)
print()
print("노드의 개수 = ", end='')
print(T.count_node(a))
print("단말의 개수 = ", end='')
print(T.count_leaf(a))
print("트리의 높이 = ", end='')
print(T.calc_height(a))
a = TNode('A', None, None)
b = TNode('B', None, None)
c = TNode('C', None, None)
d = TNode('D', None, None)
e = TNode('E', None, None)
n1 = TNode('/', a, b)
n2 = TNode('*', n1, c)
n3 = TNode('*', n2, d)
n4 = TNode('+', n3, e)
print("In-Order : ", end='')
T.inorder(n4)
print()
print("Pre-Order : ", end='')
T.preorder(n4)
print()
print("Post-Order : ", end='')
T.postorder(n4)
print()
print("Level-Order : ", end='')
T.levelorder(n4)
print()
print("노드의 개수 = ", end='')
print(T.count_node(n4))
print("단말의 개수 = ", end='')
print(T.count_leaf(n4))
print("트리의 높이 = ", end='')
print(T.calc_height(n4))
Pre, In, Post
트리를 읽는 방법은 크게 3개 (사실 4개다)가 있는데 하나씩 파해쳐보도록 하겠다.
Preorder
전위순회이다. 루트노드에서 시작, 좌측노드, 그리고 우측노드 순서로 출력하는 방식이다. VLR이라 부른다
Inorder
중위순회이다. 왼쪽서브트리, 루트, 오른쪽 서브트리 순서로 방문하며 출력한다. LVR이라 부른다
PostOrder
후위순회이다. 오른쪽 왼족서브트리, 오른쪽 서브트리, 루트 순으로 출력한다.
보통 이 3가지 방법중 preorder를 가장 많이 사용하며, 이와 별개로 levelorder도 존재한다.
Morse 부호 Encode / Decode
이러한 트리를 이용해서 모르스 코드를 인코딩 / 디코딩하는 알고리즘을 구현 할 수 있다.
우선 디코딩을 위해서는 결정트리라는 트리를 만들어야 하는데 다음 트리의 생성원리는 다음과 같다.
- .을 좌측노드로 보낸다.
- -를 우측노드로 보낸다.
- 모르스 부호가 끝난자리에 노드를 생성하고 상응하는 대문자 알파벳을 넣는다.
이를 구현하면 다음과 같다.
class TNode:
def __init__(self, data, left, right):
self.data = data
self.left = left
self.right = right
table = [('A', '.-'), ('B', '-...'),
('C', '-.-.'), ('D', '-..'), ('E', '.'),
('F', '..-.'), ('G', '--.'), ('H', '....'),
('I', '..'), ('J', '.---'), ('K', '-.-'),
('L', '.-..'), ('M', '--'), ('N', '-.'),
('O', '---'), ('P', '.--.'), ('Q', '--.-'),
('R', '.-.'), ('S', '...'), ('T', '-'),
('U', '..-'), ('V', '...-'), ('W', '.--'),
('X', '-..-'), ('Y', '-.--'), ('Z', '--..')]
def make_morese_tree():
root = TNode(None, None, None)
for tp in table:
code = tp[1] # save the morse code
node = root
for c in code:
if c == '.':
if node.left is None: # if node is empty
node.left = TNode(None, None, None) # make a empty node
node = node.left # node is moved to left node
elif c == '-':
if node.right is None:
node.right = TNode(None, None, None)
node = node.right
node.data = tp[0] # save data to node
return root- 테이블을 리스트가 아닌 튜플형태로 구현하여도 가능하다,
우선, 코드에다가 해당 알파벳의 코드를 담아둔다.
그 후 코드를 하나씩 확인하며 . 이면 왼쪽, -이면 오른쪽으로 보낸다. 그 후, 만약 노드가 없다면 노드를 만들고 계속 진행한다.
모두 마무리면 해당 위치에 모스부호에 상응하는 데이터값을 저장하고 마무리한다.
이렇게 작성된 결정트리를 통해 우리는 Decoding을 할 수 있다.
코드는 다음과 같다
def decode(root, code):
node = root
for c in code:
if c == '.':
node = node.left
elif c == '-':
node = node.right
return node.data디코딩 과정은 간단하다. 부호를 따라서 좌, 우로 이동하면서 최종 도착한 노드의 data를 가져오는것이다.
encoding의 경우, ascii코드 값을 이용하여 id를 찾고 그 table에서 해당 id 인덱스로 이동하는 방식을 사용한다.
마치며
이처럼 트리를 이용해서 우리는 다양한 표현과 알고리즘을 구현할 수 있다.
다음 글에서는 힙 트리와 힙 정렬, 그리고 BST AVL Red Black등 다양한 트리를 학습하겠다
