[자료구조] 6,7 주차 노트 (그래프, Heap, 이진 트리, 순회, 우선순위 큐, 이진 탐색 트리)

KOCW에서 제공하는 고려대학교 유용재 교수님의 자료구조 강의를 수강한 후, 정리한 글입니다. 

http://www.kocw.net/home/cview.do?cid=b216fbe96107c9ea

 

주제

• 6. 우선 순위 Queue와 이진 Tree  기초
• 7. 이진 Tree 구현과 데이터 순회

class BiTreeNode:
    def __init__ (self, data):
        self.data = data
        self.left = None
        self.right = None
    
n1 = BiTreeNode(1)
n2 = BiTreeNode(2)
n3 = BiTreeNode(3)
n4 = BiTreeNode(4)
n5 = BiTreeNode(5)
n6= BiTreeNode(6)
n7 = BiTreeNode(7)

n1.left = n2
n1.right = n3
n2.left = n4
n2.right = n5
n5.left = n6
n5.right = n7

def level_order(root_node):
    queue = list()
    queue.append(root_node)
    while True:
        if len(queue) == 0:
            break
        print(queue[0].data)
        if queue[0].left != None:
            queue.append(queue[0].left)
        if queue[0].right != None:
            queue.append(queue[0].right)
        del queue[0]

left_order(n1)

# 실행 결과
1
2
3
4
5
6
7

def pre_order(node):
    print(node.data)
    if node.left != None:
        pre_order(node.left)
    if node.right != None:
        pre_order(node.right)


def in_order(node):
    if node.left != None:
        in_order(node.left)
    print(node.data)
    if node.right != None:
        in_order(node.right)


def post_order(node):
    if node.left != None:
        post_order(node.left)
    if node.right != None:
        post_order(node.right)
    print(node.data)

print("Pre-Order")
pre_order(n1)
print("In-Order")
in_order(n1)
print("Post-Order")
post_order(n1)

#결과
Pre-Order
1
2
4
5
6
7
3
In-Order
4
2
6
5
7
1
3
Post-Order
4
6
7
5
2
3
1