Binary trees are a data structure that impose an order on inserted nodes: items less than a node are stored in its left subtree, and items greater than a node are inserted in the right. At the bottom, the subtrees are empty. Because of this structure, binary trees naturally support quick, recursive traversals -- at least ideally, every time you follow a link to a subtree, you divide the search space in half.
Binary trees are named for the implied branch-like structure of their
subtree links. Typically, their nodes are implemented as a triple of
Beyond that, there is fairly wide latitude in the tree
implementation. Here we’ll use a class-based approach:
BinaryTree is a header object, which initializes and manages the actual tree.
EmptyNode is the empty object, shared at all empty subtrees (at the bottom).
BinaryNode objects are nonempty tree nodes with a value and two subtrees.
Rather than coding distinct search functions, binary trees are
constructed with “smart” objects (class instances) that
know how to handle insert/lookup and printing requests and pass them
to subtree objects. In fact, this is another example of the OOP
composition relationship in action: tree nodes embed other tree nodes
and pass search requests off to the embedded subtrees. A single empty
class instance is shared by all empty subtrees in a binary tree, and
inserts replace an
EmptyNode with a
BinaryNode at the bottom (see Example ...