-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathbintreeno.py
157 lines (137 loc) · 4.85 KB
/
bintreeno.py
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
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
#!/usr/bin/python
# note from polycopter: can't recall where I found this code originally
# I added "contains()" and "delete()" and removed 'object' inheritance
class Node():
def __init__(self, key, parent = None):
self.key = key
self.parent = parent
self.left = None
self.right = None
self.keycount = 1 # this is nonstandard, eh? I think so
class BinaryTree():
def __init__(self, key):
self.root = Node(key)
def add(self, key):
nd = self.root
while nd is not None:
saved_place = nd
if nd.key > key:
nd = nd.left
elif nd.key == key:
nd.keycount += 1 # nonstandard?
return
else:
nd = nd.right
if saved_place.key > key:
saved_place.left = Node(key, saved_place)
else:
saved_place.right = Node(key, saved_place)
def traverse(self, nd, func):
if nd.left is not None:
self.traverse(nd.left, func)
for i in range(nd.keycount):
func(nd.key)
if nd.right is not None:
self.traverse(nd.right, func)
def printTree(self):
self.traverse(self.root, print)
def traverseDbg(self, nd, func):
if nd.left is not None:
self.traverseDbg(nd.left, func)
for i in range(nd.keycount):
if nd.parent is not None:
func(nd.key, nd.parent.key)
else:
func(nd.key, 'None')
if nd.right is not None:
self.traverseDbg(nd.right, func)
def debugPrint(self):
self.traverseDbg(self.root, print)
def contains(self, key):
nd = self.root
while nd is not None:
if nd.key > key:
nd = nd.left
elif nd.key == key:
return True
else:
nd = nd.right
return False
def smallestKey(self, nd):
if nd is not None:
if nd.left is not None:
return self.smallestKey(nd.left)
else:
return nd.key
else:
# TO DO: should raise exception here
return None
def delete(self, key):
nd = self.root
side = '?'
while nd is not None:
if nd.key > key:
side = 'L'
nd = nd.left
elif nd.key == key:
nd.keycount -= 1 # keycount always starts at 1, in Node() ctor
if nd.keycount == 0:
# handle 3 cases to delete node nd
if nd.left is None:
if nd.right is None:
# case 1: no children, just delete this node
if side == 'L':
nd.parent.left = None
elif side == 'R':
nd.parent.right = None
else:
# case 2a: connect right child to parent
# & connect parent to right child
if side == 'L':
nd.parent.left = nd.right
elif side == 'R':
nd.parent.right = nd.right
nd.right.parent = nd.parent
elif nd.right is None:
# case 2b: connect left child to parent
# & connect parent to left child
if side == 'L':
nd.parent.left = nd.left
elif side == 'R':
nd.parent.right = nd.left
nd.left.parent = nd.parent
else:
# case 3:
swapkey = self.smallestKey(nd.right)
# 'catch' exception
if swapkey is None:
print('ERROR: smallestKey() failed')
return
self.delete(swapkey)
nd.key = swapkey
# all done if we get here
return
else:
side = 'R'
nd = nd.right
if __name__ == '__main__':
testTree = BinaryTree('p')
for c in 'olycopter': testTree.add(c)
testTree.printTree()
testTree.debugPrint()
piTree = BinaryTree(3)
for d in [1,4,1,5,9]: piTree.add(d)
piTree.printTree()
piTree.debugPrint()
print(testTree.contains('p'), testTree.contains('x'))
print(piTree.contains(1), piTree.contains(8))
testTree.delete('y')
testTree.printTree()
testTree.debugPrint()
testTree.add('x')
testTree.debugPrint()
testTree.delete('t')
testTree.debugPrint()
piTree.delete(9)
piTree.printTree()
piTree.debugPrint()