python-samples/bst.py at master · DulajMadushanka/python-samples · 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
100
101
102
103
104
105
106
107
108
class Node:
    def __init__(self, val):
        self.left = None
        self.right = None
        self.value = val

    def insert(self, val):
        if val < self.value:
            if self.left is None:
                self.left = Node(val)
            else:
                self.left.insert(val)
        elif val > self.value:
            if self.right is None:
                self.right = Node(val)
            else:
                self.right.insert(val)

    def lookup(self, val, parent=None):
        if val < self.value:
            if self.left is None:
                return None, None
            return self.left.lookup(val, self)
        elif val > self.value:
            if self.right is None:
                return None, None
            return self.right.lookup(val, self)
        else:
            return self, parent


    def children_count(self):
        count = 0
        if self.left:
            count += 1
        if self.right:
            count += 1
        return count

    def delete(self, val):
        node, parent = self.lookup(val)
        if self.children_count() == 0:
            if parent:
                if parent.left is node:
                    parent.left = None
                else:
                    parent.right = None
                del node
            else:
                self.value = None

        elif self.children_count() == 1:
            if node.left:
                n = node.left
            else:
                n = node.right
            if parent:
                if parent.left is node:
                    parent.left = n
                else:
                    parent.right = n
                del node
            else:
                self.left = n.left
                self.right = n.right
                self.value = n.value

        else:
            parent = node
            successor = node.right
            while successor.left is not None:
                parent = successor
                successor = successor.left

            node.value = successor.value
            if parent.left == successor:
                parent.left = successor.right
            else:
                parent.right = successor.right

    def pre_order(self):
        print self.value,
        if self.left is not None:
            self.left.pre_order()
        if self.right is not None:
            self.right.pre_order()

    def in_order(self):
        if self.left is not None:
            self.left.in_order()
        print self.value,
        if self.right is not None:
            self.right.in_order()

    def post_order(self):
        if self.left is not None:
            self.left.post_order()
        if self.right is not None:
            self.right.post_order()
        print self.value,

##test
t = Node(10)
t.insert(2)
t.insert(15)
t.insert(5)
t.delete(5)
t.post_order()