koreatech_-/BSTMap.py at master · EunHoLee02/koreatech_- · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
from BinSrchTree import *

def inorder(n):
    if n is not None:
        inorder(n.left)
        print(n.key, end=' ')  # node의 key만 중위순회로 출력
        inorder(n.right)

def preorder(n):
    if n is not None:
        print(n.key, end=' ')
        preorder(n.left)
        preorder(n.right)

def postorder(n):
    if n is not None:
        postorder(n.left)
        postorder(n.right)
        print(n.key, end=' ')

# 코드 9.11: 이진탐색트리를 이용한 맵 클래스
class BSTMap():
    def __init__(self):
        self.root = None

    def isEmpty(self):
        return self.root == None

    def findMax(self):
        return search_max_bst(self.root)

    def findMin(self):
        return search_min_bst(self.root)

    def search(self, key):
        return search_bst(self.root, key)
        # return search_bst_iter(self.root, key)

    def searchValue(self, key):
        return search_value_bst(self.root, key)

    def insert(self, key, value=None):
        n = BSTNode(key, value)
        if self.isEmpty():
            self.root = n
        else:
            insert_bst(self.root, n)

    def delete(self, key):
        self.root = delete_bst(self.root, key)

    def display(self, msg='BSTMap :', order=1):
        print(msg, end='')
        if order == 1:  # inorder
            inorder(self.root)
        elif order == 2:  # preorder
            preorder(self.root)
        elif order == 3:  # postorder
            postorder(self.root)
        print()


# =========================================================
#   - 이 파일이 직접 실행될 때에는 다음 문장들을 실행함.
#   - 다른 파일에서 모듈로 불려지는 경우는 실행되지 않음.
# =========================================================
# 코드 9.12: 이진탐색트리를 이용한 맵 테스트 프로그램
if __name__ == "__main__":
    data = [35, 18, 7, 26, 12, 3, 68, 22, 30, 99]
    value = ["삼오", "일팔", "영칠", "이육", "일이", "영삼", "육팔", "이이", "삼영", "구구"]

    map = BSTMap()
    map.display("[삽입 전] : ")
    for i in range(len(data)):
        map.insert(data[i], value[i])
        map.display("[삽입 %2d] : " % data[i])

    print('[최대 키] : ', map.findMax().key)
    print('[최소 키] : ', map.findMin().key)
    print('[탐색 26] : ', '성공' if map.search(26) != None else '실패')
    print('[탐색 25] : ', '성공' if map.search(25) != None else '실패')
    print('[탐색 일팔]:', '성공' if map.searchValue("일팔") != None else '실패')
    print('[탐색 일칠]:', '성공' if map.searchValue("일칠") != None else '실패')

    # 노드 삭제 테스트
    map.delete(3)
    map.display("[삭제  3] : ")
    map.delete(68)
    map.display("[삭제 68] : ")
    map.delete(18)
    map.display("[삭제 18] : ")
    map.delete(35)
    map.display("[삭제 35] : ")

    # 트리 순회 방식 테스트
    print("\n트리 순회 방식별 출력:")
    map.display("[중위 순회] : ", order=1)  # inorder
    map.display("[전위 순회] : ", order=2)  # preorder
    map.display("[후위 순회] : ", order=3)  # postorder