( *, 3, * )
( ( *, 1, * ), 3, * )
( ( *, 1, * ), 3, ( *, 9, * ) )
( ( *, 1, ( *, 2, * ) ), 3, ( *, 9, * ) )
( ( *, 1, ( *, 2, * ) ), 3, ( ( *, 7, * ), 9, * ) )At the end of this chapter, we’ll see another way to visualize such trees in a GUI named
PyTree (you’re invited to flip ahead now if you prefer). Node values in this tree object
can be any comparable Python object—for instance, here is a tree of strings:
>>> z = BinaryTree()
>>> for c in 'badce': z.insert(c)
...
>>> z
( ( *, 'a', * ), 'b', ( ( *, 'c', * ), 'd', ( *, 'e', * ) ) )>>> z = BinaryTree()
>>> for c in 'abcde': z.insert(c)
...
>>> z
( *, 'a', ( *, 'b', ( *, 'c', ( *, 'd', ( *, 'e', * ) ) ) ) )>>> z = BinaryTree()
>>> for c in 'edcba': z.insert(c)
...
>>> z
( ( ( ( ( *, 'a', * ), 'b', * ), 'c', * ), 'd', * ), 'e', * )Notice the last tests here: if items inserted into a binary tree are already ordered, you
wind up with a linear structure and lose the search-space partitioning magic of binary
trees (the tree grows in right or left branches only). This is a worst-case scenario, and
binary trees generally do a good job of dividing values in practice. But if you are inter-
ested in pursuing this topic further, see a data structures text for tree-balancing tech-
niques that automatically keep the tree as dense as possible but are beyond our scope
here.
Trees with Both Keys and Values
Also note that to keep the code simple, these trees store a value only and lookups return
a true or false result. In practice, you sometimes may want to store both a key and an
associated value (or even more) at each tree node. Example 18-15 shows what such a
tree object looks like, for any prospective lumberjacks in the audience.
Example 18-15. PP4E\Dstruct\Classics\btreevals.py
"a binary search tree with values for stored keys"
class KeyedBinaryTree:
def init(self): self.tree = EmptyNode()
def repr(self): return repr(self.tree)
def lookup(self, key): return self.tree.lookup(key)
def insert(self, key, val): self.tree = self.tree.insert(key, val)
1388 | Chapter 18: Data Structures