CMPSC132/node_BST.py at master · wcn4/CMPSC132 · 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
109
110
111
112
113
114
class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

    def __str__(self):
        return ("Node({})".format(self.value))

    __repr__ = __str__


class BinarySearchTree:

    def __init__(self):
        self.root = None

    def insert(self, value): # Simplified version of insert using a helper method
        if self.root is None:
            self.root=Node(value)
        else:
            self._insert(self.root, value)


    def _insert(self, node, value):
        if(value<node.value):
            if(node.left==None):
                node.left = Node(value)
            else:
                self._insert(node.left, value)
        else:      # This will allow repeated values to be placed in the tree. To avoid this, we do: elif(value>node.value):
            if(node.right==None):
                node.right = Node(value)
            else:
                self._insert(node.right, value)


    def __delitem__(self, value):
        self._deleteHelper(None, self.root, value)
        return self.printInorder


    @property
    def printInorder(self):
        self._inorderHelper(self.root)

    def _inorderHelper(self, node):
        if node is not None:
           self._inorderHelper(node.left)
           print(node.value, end=' : ')
           self._inorderHelper(node.right)


    def numChildren(self, node):
        total = 0
        if (node.left):
            total += 1
        if (node.right):
            total += 1
        return total

    def _deleteHelper(self, parent, current, value):
        if current is None:
            return None
        if current.value>value:
            #The node in question is to the left
            self._deleteHelper(current, current.left, value) #[1]
        elif current.value<value:
            #The node in question is to the right
            self._deleteHelper(current, current.right, value) #[2]
        else:
            node_children=self.numChildren(current)
            if node_children==0 or node_children==1:
                if current.left is not None:
                    child = current.left
                else:
                    child = current.right
                #Removing reference to current node
                if (parent is not None) and (parent.left is current):
                   parent.left = child
                elif (parent is not None) and (parent.right is current):
                    parent.right = child
                else:
                    #If root was the node that was being deleted
                    self.root = child
            else:
                temp = current.right
                parent = current
                #Find smallest value on the right subtree
                while temp.left is not None:
                    parent = temp
                    temp = temp.left
                current.value= temp.value #Swap the value
                self._deleteHelper(parent, temp, temp.value) #Delete the node once swap is done


bst_keys = [3, 2, 5, 4, 9, 3.5, 6]
t = BinarySearchTree()
for key in bst_keys:
    t.insert(key)

t.printInorder
print()

print(t.numChildren(t.root))              # Displays 2
print(t.numChildren(t.root.left))         # Displays 0
print(t.numChildren(t.root.right))        # Displays 2
print(t.numChildren(t.root.right.right))  # Displays 1
del t[4]