class Node:
def __init__(self, item, left=None, right=None): # 노드 생성자
self.item = item
self.left = left
self.right = right
class BinaryTree:
def __init__(self): # 트리 생성자
self.root = None
def preorder(self, n): # 전위순회
if n != None:
print(str(n.item),' ', end='')
if n.left:
self.preorder(n.left)
if n.right:
self.preorder(n.right)
def inorder(self, n): # 중위순회
if n != None:
if n.left:
self.inorder(n.left)
print(str(n.item),' ', end='')
if n.right:
self.inorder(n.right)
def postorder(self, n): # 후위순회
if n != None:
if n.left:
self.postorder(n.left)
if n.right:
self.postorder(n.right)
print(str(n.item),' ', end='')
def levelorder(self, root): # 레벨순회
q = []
q.append(root)
while len(q) != 0:
t = q.pop(0)
print(str(t.item), ' ', end='')
if t.left != None:
q.append(t.left)
if t.right != None:
q.append(t.right)
def height(self, root): # 트리 높이 계산
if root == None:
return 0
return max(self.height(root.left), self.height(root.right)) + 1
def size(self, root): # 트리 노드 수 계산
if root is None:
return 0
else:
return 1 + self.size(root.left) + self.size(root.right)
def copy_tree(self, n): # 트리 복제
if n == None:
return None
else:
left = self.copy_tree(n.left)
right = self.copy_tree(n.right)
return self.Node(n.item, left, right)
def is_equal(self, n, m): # 두 트리의 동일성 검사
if n == None or m == None:
return n == m
if n.item != m.item:
return False
return( self.is_equal(n.left, m.left) and
self.is_equal(n.right, m.right) )
#from binary_tree import BinaryTree, Node
if __name__ == '__main__':
t = BinaryTree() # 이진트리 객체 t 생성
n1 = Node(100) # 8개의 노드 생성
n2 = Node(200)
n3 = Node(300)
n4 = Node(400)
n5 = Node(500)
n6 = Node(600)
n7 = Node(700)
n8 = Node(800)
n1.left = n2 # n1의 왼쪽 자식-> n2
n1.right = n3 # n1의 오른쪽 자식-> n3
n2.left = n4 # n2의 왼쪽 자식-> n4
n2.right = n5 # n2의 오른쪽 자식-> n5
n3.left = n6 # n3의 왼쪽 자식-> n6
n3.right = n7 # n3의 오른쪽 자식-> n7
n4.left = n8 # n4의 왼쪽 자식-> n8
t.root = n1 # t의 루트노드를 n1으로
print('트리 높이 =', t.height(t.root))
print('전위순회:\t', end='')
t.preorder(t.root)
print('\n중위순회:\t', end='')
t.inorder(t.root)
print('\n후위순회:\t', end='')
t.postorder(t.root)
print('\n레벨순회:\t', end='')
t.levelorder(t.root)
class BHeap:
def __init__(self, a): # 생성자
self.a = a # a[0] 사용 안함
self.N = len(a) - 1 # 힙의 항목 수
def create_heap(self): # 초기 힙 만들기
for i in range(self.N//2, 0, -1):
self.downheap(i)
def insert(self, key_value): # 삽입 연산
self.N += 1
self.a.append(key_value) # 새로운 키(항목)를 맨 끝에 저장
self.upheap(self.N) # 위로 올라가며 힙속성 회복시키기 위해
def delete_min(self): # 최솟값 삭제
if self.N == 0: # underflow 경우
print('힙이 비어 있음')
return None
minimum = self.a[1] # a[1]의 최솟값을 minimum에 저장하여 리턴
self.a[1], self.a[-1] = self.a[-1], self.a[1] # 힙의 마지막 항목과 교환
del self.a[-1] # 힙의 마지막 항목 삭제
self.N -= 1
self.downheap(1) # 힙속성을 회복시키기 위해
return minimum
def downheap(self, i): # 힙 내려가며 힙속성 회복
while 2*i <= self.N: # i의 왼쪽자식이 힙에 있으면
k = 2*i # k는 왼쪽자식의 인덱스
if k < self.N and self.a[k][0] > self.a[k+1][0]: #왼쪽과 오른쪽자식의 승자를 결정하여 k가 승자의 인덱스가됨
k += 1
if self.a[i][0] < self.a[k][0]:
break # 현재 노드가 자식 승자보다 작으면, 루프를 중단하고
self.a[i], self.a[k] = self.a[k], self.a[i] # 현재 노드가 자식 승자보다 크면 현재 노드와 자식 승자와 교환
i = k # 자식 승자가 현재 노드가 되어 다시 반복하기 위해
def upheap(self, j): # 힙 올라가며 힙속성 회복
while j > 1 and self.a[j//2][0] > self.a[j][0]: # 현재노드가 루트가 아니고 동시에 부모가 크면
self.a[j], self.a[j//2] = self.a[j//2], self.a[j] # 부모와 현재 노드 교환
j = j//2 # 부모가 현재 노드가 되어 다시 반복하기 위해
def print_heap(self): # 힙 출력
for i in range(1, self.N+1):
print('[%2d' % self.a[i][0], self.a[i][1], ']', end='')
print('\n힙 크기 = ', self.N)
#from binary_heap import BHeap
if __name__ == '__main__':
a = [None] * 1
a.append([90, 'watermelon'])
a.append([80, 'pear'])
a.append([70, 'melon'])
a.append([50, 'lime'])
a.append([60, 'mango'])
a.append([20, 'cherry'])
a.append([30, 'grape'])
a.append([35, 'orange'])
a.append([10, 'apricot'])
a.append([15, 'banana'])
a.append([45, 'lemon'])
a.append([40, 'kiwi'])
b = BHeap(a)
print('힙 만들기 전:')
b.print_heap()
b.create_heap() # 힙 만들기
print('최소힙:')
b.print_heap()
print('최솟값 삭제 후')
print(b.delete_min())
b.print_heap()
b.insert([5,'apple'])
print('5 삽입 후')
b.print_heap()