class EmptyNode:
def repr(self):
return '*'
def lookup(self, value): # fail at the bottom
return False
def insert(self, value):
return BinaryNode(self, value, self) # add new node at bottom
class BinaryNode:
def init(self, left, value, right):
self.data, self.left, self.right = value, left, right
def lookup(self, value):
if self.data == value:
return True
elif self.data > value:
return self.left.lookup(value) # look in left
else:
return self.right.lookup(value) # look in right
def insert(self, value):
if self.data > value:
self.left = self.left.insert(value) # grow in left
elif self.data < value:
self.right = self.right.insert(value) # grow in right
return self
def repr(self):
return ('( %s, %s, %s )' %
(repr(self.left), repr(self.data), repr(self.right)))
As usual, BinaryTree can contain objects of any type that support the expected interface
protocol—here, > and < comparisons. This includes class instances with the lt and
gt methods. Let’s experiment with this module’s interfaces. The following code
stuffs five integers into a new tree, and then searches for values 0... 7, as we did earlier
for dictionaries and sets:
C:\...\PP4E\Dstruct\Classics> python
>>> from btree import BinaryTree
>>> x = BinaryTree()
>>> for i in [3, 1, 9, 2, 7]: x.insert(i)
...
>>> for i in range(8): print((i, x.lookup(i)), end=' ')
...
(0, False) (1, True) (2, True) (3, True) (4, False) (5, False) (6, False) (7, True)To watch this tree grow, add a print call statement after each insert. Tree nodes print
themselves as triples, and empty nodes print as *. The result reflects tree nesting:
>>> y = BinaryTree()
>>> y
*
>>> for i in [3, 1, 9, 2, 7]:
... y.insert(i); print(y)
...Binary Search Trees | 1387