Binary Search Trees
Binary trees are a data structure that impose an order on inserted nodes: items less than a node are stored in the 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 values: (LeftSubtree, NodeValue,
RightSubtree). Beyond that, there is fairly wide latitude in
the tree implementation. Here we’ll use a class-based approach:
BinaryTreeis a header object, which initializes and manages the actual tree.EmptyNodeis the empty object, shared at all empty subtrees (at the bottom).BinaryNodeobjects are nonempty tree nodes with a value and two subtrees.
Instead of 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 object-oriented
programming (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 ...