data-structure/tree.py at main · ganggun/data-structure · 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
class t:
    def __init__(self,v):
        self.v= v
        self.left = None
        self.right = None
class bt:
    def __init__(self,root):
        self.root =t(root)

    def insert(self,v):
        def insertr(n,v):
            if not n :#노드 비면 새거 생성
                return t(v)
            if v<n.v :#작으면
                n.left=insertr(n.left,v)
            elif v>n.v :#크면
                n.right=insertr(n.right,v)
            return n# 중복 재거
        self.root =insertr(self.root,v)

    def s(self,v):
        def sr(n,v):
            if not n :return False
            if n.v==v:return True
            elif v<n.v:
                return sr(n.left,v)
            else:
                return sr(n.right, v)
        return sr(self.root,v)

    def d(self,v):
        def dsr(n,v):
            if not n:return n
            if v<n.v:
                n.left=dsr(n.left,v)
            elif v>n.v:
                n.right=dsr(n.right,v) #찾을때까지 제귀
            else:
                if not n.left and not n.right:
                    return None
                elif not n.left:
                    return n.right
                elif not n.right:
                    return n.left
                temp= self.find_min(n.right)
                n.v=temp.v
                n.right=dsr(n.right,temp.v)
            return n
        self.root =dsr(self.root,v)
    def find_min(self,n):
        while n.left:
            n = n.left
        return n


tree=bt(10)
tree.insert(5)
tree.insert(10)
tree.insert(7)
print(tree.s(7))
print(tree.d(7))
print(tree.s(7))
print(tree.s(10))