[Python 자료구조 #트리2] 모르스 코드 결정트리

* 이진트리의 응용 : 모르스 코드 결정트리

• 모르스 부호는 도트(점)와 대시(선)의 조합으로 구성된 메시지 전달용 부호로 1830년대에 미국의 사뮤엘 모르스(Samuel Morse)에 의해 고안되었다.
• 결정트리는 여러 단계의 복잡한 조건을 갖는 문제에 대해 조건과 그에 따른 해결방법을 트리 형태로 나타낸 것을 말한다.
• 결정트리를 이용하면 알파벳을 찾는데 걸리는 시간은 O(log_2 n)이다.

모르스 코드 표

 

출처 : 파이썬으로 쉽게 풀어쓴 자료구조

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', '--..') ]
        
class TNode:
    def __init__(self, data, left, right):
        self.data = data
        self.left = left
        self.right = right


def make_morse_tree():
    root = TNode(None, None, None)
    for tp in table:				# table에 있는 요소 하나 하나씩 넣음.
        code = tp[1]				# 모르스 코드 table 한 요소의 모르스 코드를 넣음

        node = root
        for c in code: 				 # 맨 마지막 문자 이전까지 -> 이동
            if c == ".": 			 # 점(.): 결정트리에서 왼쪽으로 이동
                if node.left == None:		  # 비었으면 빈 노드 만들기
                    node.left = TNode(None, None, None)
                node = node.left 		 # 그쪽으로 이동
            elif c == "-":  			# 오른쪽으로 이동
                if node.right == None:		  # 비었으면 빈 노드 만들기
                    node.right = TNode(None, None, None)
                node = node.right  		# 그쪽으로 이동

        node.data = tp[0] 			 # 코드의 알파벳을 해당 노드에 넣음.
    return root


def decode(root, code):				 # 모르스 코드에 대한 문자를 찾는 함수
    node = root
    for c in code:
        if c == ".":
            node = node.left
        elif c == "-":
            node = node.right
    return node.data


def encode(ch):     # 문자에 대한 코드를 찾아 반환하는 함수
    idx = ord(ch) - ord("A")    # 예로 C의 코드를 찾는다고하면 C(67)-A(65)=2
    return table[idx][1]        # C의 코드는 table[2][1]에 해당한다.

morseCodeTree = make_morse_tree()
str = input("입력 문장 : ")		# 알파벳 대문자만 입력가능. 그 외 오류
mlist = []
for ch in str:
    code = encode(ch)
    mlist.append(code)
print("Morse Code: ", mlist)
print("Decoding  : ", end="")
for code in mlist:
    ch = decode(morseCodeTree, code)
    print(ch, end="")
print()
--------------------------------------------------
입력 문장 : GAMEOVER
Morse Code:  ['--.', '.-', '--', '.', '---', '...-', '.', '.-.']
Decoding  : GAMEOVER