교재 : 파이썬으로 배우는 자료구조 프로그래밍 (유석종, 휴먼싸이언스)
6.1 이진 트리의 정의
1) 트리(tree)
- 루트(root)와 루트의 서브트리(sub-tree)로 구성된 계층형(hierarchical) 자료구조
- 최소 하나 이상의 노드가 있어야 한다.
- 서브 트리는 부모 노드를 제거한 후 남은 부분 트리
- 계통도, 조직도, 폴더의 구조 등 계층적 구조를 갖는 영역에서 활용된다.
2) 이진 트리(binary tree)
- 각 노드가 최소 2개의 자식 노드를 갖도록 제한하는 트리
- ex) 허프만 코딩 트리 (Huffman coding tree)
- 허프만 코딩 : 가변 길이 부호화를 사용하여 텍스트 문서를 압축하는 방법
- 각 문자를 출현 빈도에 따라 나열한다.
- 출현 빈도를 순서대로 트리(tree)의 단말노드(terminal node)의 값으로 지정한다.
- 허프만 코딩 트리를 이용하여 각 문자를 가변 길이 코드로 변환한다.
- 코드
class Node:
def __init__(self, data, sym):
self.data = data
self.sym = sym
self.code_left= {}
self.code_right= {}
self.code_left[sym] = []
self.left = None
self.right = None
class Huffman:
def __init__(self, num, char):
self.node_set = []
self.code = {}
self.root = None
for i in range(len(num)):
node = Node(num[i], char[i])
self.node_set.append(node)
def show_tree(self):
print("[", end = ' ')
for node in self.node_set:
print(node.data, end=' ')
print(']')
def show_code(self):
for sym, hcode in self.root.code_left.items():
if sym:
print(sym, hcode)
for sym, hcode in self.root.code_right.items():
if sym:
print(sym, hcode)
def add_code(self, code, bit):
for sym, lst in code.items():
if sym:
code[sym].insert(0, bit)
def copy_code(self, code1, code2):
for sym, code in code1.items():
code2[sym] = code
def make_tree(self):
while len(self.node_set) > 1:
if len(self.node_set) == 2:
a = self.node_set.pop(0)
b = self.node_set.pop(0)
c = Node(a.data + b.data, None)
c.left = a
c.righ = b
self.copy_code(a.code_left, c.code_left)
self.copy_code(a.code_right, c.code_left)
self.copy_code(b.code_left, c.code_right)
self.copy_code(b.code_right, c.code_right)
self.add_code(c.code_left, '0')
self.add_code(c.code_right, '1')
self.node_set.append(c)
self.root = c
break
min_sum = 1000
pos= 0
for i in range(len(self.node_set)-1):
a= self.node_set[i].data
b = self.node_set[i+1].data
if a + b < min_sum:
min_sum = a+b
pos = i
a = self.node_set.pop(pos)
b = self.node_set.pop(pos)
c= Node(a.data + b.data, None)
self.copy_code(a.code_left, c.code_left)
self.copy_code(a.code_right, c.code_left)
self.copy_code(b.code_left, c.code_left)
self.copy_code(b.code_right, c.code_right)
self.add_code(c.code_left, '0')
self.add_code(c.code_right, '1')
c.left = a
c.right = b
self.node_set.insert(pos, c)
self.show_tree()[IT개론] 데이터 표현과 디지털 논리
내용 출처 : 소프트웨어 세상을 여는 컴퓨터과학 1. 수의 체계와 변환 1) 수의 체계 (1) 진법 : 사용할 수 있는 숫자의 개수와 각 숫자의 위치값을 정의한 수 체계 (2) 진법의 종류 : 10진법, 2진법, 8
0yeonjae2.tistory.com
위 링크에서 관련 내용을 확인하실 수 있습니다.
6.2 이진 트리의 용어
1) 차수와 레벨
- 노드의 차수 (degree of node) : 특정 노드에 연결된 서브 트리의 수
- 트리의 차수 (degree) : 모든 노드의 차수 중 최대값 -> 이진트리에서는 2
- 단말 노드 (leaf/termial) : 자식 노드가 없는 노드 (차수 = 0)
- 레벨 (level) : 단말 노드 방향으로 1씩 단계별로 증가한다.
- 부모 노드(parent)와 자식 노드(child)의 레벨 차이는 1이다.
- 형제 노드 (sibling) : 부모가 동일한 자식 노드
- 조상 노드 (ancester) : 특정 노드에서 루트에 이르는 경로에 존재하는 모든 노드
- 자손 노드(decendant) : 특정 노드의 서브 트리에 존재하는 모든 노드
- 내부 노드 (internal) : 자식이 최소 1개 이상인 노드
- 외부 노드 (external) : 자식이 없는 단말 노드 (terminal)
2) 이진 트리의 높이와 깊이
- 노드의 높이(height) : 해당 노드에서 단말 노드에 이르는 가장 긴 경로(path)에서 간선(edge)의 수
- 노드의 깊이(depth) : 루트에서 해당 노드에 이르는 경로에서 간선의 수
- 트리의 높이(height) == 트리의 깊이(depth) : 단말 노드에 이르는 가장 긴 경로에서 간선의 수
- 트리의 레벨(level) : 루트(레벨0)에서 단말 노드로 내려갈 때마다 1씩 증가한다.
- 트리 노드의 높이와 깊이를 계산하는 코드
class Node:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
class Tree:
def find(self, root, item):
if not root:
return None
if root.data == item:
return root
else:
node1 = self.find(root.left, item)
if node1:
return node1
node2 = self.find(root.right, item)
if node2:
return node2
def height(self, root, item):
if not root:
return
if root.left:
l_height = 1 + self.height(root.left)
else:
l_height = 0
if root.right:
r_height = 1 + self.height(root.right)
else:
r_height = 0
if l_height >= r_height :
return l_height
else:
return r_height
def height_node(self, root, item):
node = self.find(root, item)
if node:
return self.height(node)
else:
return None
def depth(self, root):
if not root:
return 0
if root.left:
l_depth = 1+ self.depth(root.left)
else:
l_depth = 0
if root.right:
r_depth = 1 + self.depth(root.right)
else:
r_depth = 0
if l_depth >= r_depth:
return l_depth
else:
return r_depth
def depth_node(self, root, item):
if not root:
return -1000
if root.data == item:
return 0
if root.left:
l_depth = 1 + self.depth_node(root.left, item)
else:
l_depth = -1000
if root.right:
r_depth = 1 + self.depth_node(root.right, item)
else:
r_depth = -1000
if l_depth >= r_depth:
return l_depth
else:
return r_depth
3) 이진 트리의 특성
- 빈 트리를 허용한다.
- 자식 노드의 좌우 순서를 구별한다.
- 이진 트리에서 레벨 i에 존재할 수 있는 최대 노드 수는 2i이다.
- 이진 트리의 높이(height) : 노드의 최대 레벨
4) 포화 이진 트리 (full binary tree)
- 단말 노드의 수 = 차수가 2인 노드의 수 + 1
5) 완전 이진 트리 (complete binary tree)
- 루트에서 단말 노드 방향으로, 왼쪽에서 오른쪽 방향으로 모든 노드가 순서대로 존재한다.
6.3 이진 트리의 표현
1) 이진 트리의 배열 표현
- 완전 이진 트리의 노드 순서와 배열 인덱스를 일치시켜 저장한다.
- 한쪽 방향으로 치우친 편중 트리(skewed tree)의 경우 최악의 저장 효율을 가진다.
2) 트리의 연결 리스트 표현
- 저장 효율이 트리 형태에 영향을 받지 않는다.
- 노드 링크의 변경만으로 노드의 추가와 삭제가 용이하다.
class Node:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
6.4 이진 트리의 탐색
1) 탐색(search)
- 순회(traversal)라고도 한다.
- 이진 트리에서 각 노드를 순서대로 방문하여 노드 값을 읽는 과정
- 이진 트리의 루프, 왼쪽 서브 트리, 오른쪽 서브 트리를 어떤 순서로 방문하느냐에 따라 구분된다.
- 레벨 탐색을 제외하고 대부분 재귀호출로 구현할 수 있다.
2) 후위 탐색 (postorder)
- 왼쪽 서브 트리, 오른쪽 서브 트리, 루트 순서로 방문한다.
- 후위 수식(postfix)이 출력된다.
def postorder(ptr):
if ptr:
postorder(ptr.left)
postorder(ptr.right)
print(ptr.data, end=' ')
3) 중위 탐색 (inorder)
- 왼쪽 서브 트리, 루트, 오른쪽 서브 트리 순서로 방문한다.
- 중위 수식(infix)이 출력된다.
def inorder(ptr):
if ptr:
inorder(ptr.left)
print(ptr.data, end=' ')
inorder(ptr.right)
4) 전위 탐색 (preorder)
- 루트 노드, 왼쪽 서브트리, 오른쪽 서브트리 순서로 탐색한다.
- 전위 수식(prefix)이 출력된다.
def preorder(ptr):
if ptr:
print(ptr.data, end=' ')
preorder(ptr.left)
preorder(ptr.right)
5) 레벨 탐색 (level-order)
- 같은 레벨에 있는 노드들을 먼저 방문하는 탐색 방법
- 루트 레벨에서 단말 노드 레벨로 한 단계씩 내려가면서, 왼쪽에서 오른쪽 방향으로 노드를 방문한다.
- 재귀 호출을 사용하지 않고 선형 큐를 이용한다.
- 알고리즘
- 이진 트리의 루트 노드를 큐에 넣는다
- 큐에서 노드를 제거하여 출력하고, 이 노드의 왼쪽, 오른쪽 자식 노드 순서대로 큐에 넣는다.
- 2번 과정을 반복하다가 큐가 empty 상태가 되면 종료한다.
- 코드
class Node:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
class Tree:
def __init__(self):
self.queue = []
self.front = -1
self.rear = -1
self.size = 100
def delete(self):
if len(self.queue) > 0:
return self.queue.pop(0)
def add(self, item):
if len(self.queue) < self.size:
self.rear += 1
self.queue.append(item)
else:
print("Queue Full")
def leveloder(self, node):
if not node:
return
self.add(node)
while True:
node = self.delete()
if node:
print(node.data, end = ' ')
if node.left:
self.add(node.left)
if node.right:
self.add(node.right)
else:
break
6) 평가 트리 (evalution tree)
- 이진 트리에 저장된 수식을 탐색하면서 값을 계산하는 트리
- 평가 트리의 내부 노드에는 연산자가 저장되고, 단말 노드에는 피연산자가 저장된다.
- 평가 트리를 탐색하는 도중, 부분 트리에서 정의되는 수식의 계산 값을 저장하기 위해 기존 트리 노드에 value 필드를 추가하여 확장한다.
class Node:
def __init__(self, data):
self.data = data
self.value = None
self.left = None
self.right = None
class Tree:
def eval_tree(self, node):
if node:
self.eval_tree(node.left)
self.eval_tree(node.right)
if node.data == '+':
node.value = node.left.value + node.right.value
elif node.data == '-':
node.value = node.left.value - node.right.value
elif node.data == '*':
node.value = node.left.value * node.right.value
elif node.data == '/':
node.value = node.left.value / node.right.value
else:
node.value= int(node.data)
print(node.value, end= ' ')
'전공과목 정리 > 자료구조' 카테고리의 다른 글
| [자료구조💾] 8장 정렬 (4) | 2024.01.21 |
|---|---|
| [자료구조💾] 7장 최대 힙 (0) | 2024.01.20 |
| [자료구조💾] 5장 연결 리스트 (0) | 2024.01.17 |
| [자료구조💾] 4장 스택과 큐 (0) | 2024.01.16 |
| [자료구조💾] 3장 재귀호출 (2) | 2024.01.10 |