Binary Trees - Building Java Programs: A Back to Basics Approach - page 1022

Chapter Summary

A binary tree is a linked structure in which each node
refers to two other nodes. A tree is either empty ( null ) or
a node with references to two other trees, called its subtrees.

the right. Search trees are useful for implementing collec-
tions that can be searched quickly, such as sets and maps.

To add a node to a binary tree, traverse the tree to the left
if the new element is smaller than the current node or to
the right if it is larger. The end of this traversal will reveal
the proper place to add the new node.

The root is the top node of a tree. A leaf node is a node that
has no children. A branch node is a node that has at least
one child. Each node has a level related to the number of
links that are between it and the root of the tree.

To search for a value in a binary tree, traverse the tree
going left if the target value is smaller than the current
node or right if it is larger. Because of the way in which
the tree is ordered, the end of this traversal will either find
the target's node or find a null dead end, in which case
the value is not in the tree.

A tree node object stores a data value and left/right
references to other nodes. An overall tree object stores
a reference to a single tree node as its overall root.

A traversal is an examination of all elements in a binary
tree. Traversals are commonly done in three orders: preorder,
inorder, and postorder. The difference between the orders
relates to when a given node is examined relative to its
left/right subtrees.

The x = change(x) is a pattern in which a recursive
method is passed an object or value in its initial state (called
x here) and returns the new state of x . This technique is
often used in recursive tree methods; the recursive call
accepts a node parameter and later returns the potentially
changed node.

Tree methods are often recursive and are often implemented
with the use of a public/private pair, in which the private
method accepts a reference to a tree node as a parameter.
This technique allows the method to recursively operate
on a given portion of the overall tree.

A tree can be made to store elements of any object type E
rather than just integers. To do this, the tree class must be
made into a generic class, and the generic type parameter
E must be constrained so that it is a class which implements
the Comparable<E> interface.

The elements of a binary search tree are arranged in order,
with smaller elements on the left and larger elements on

Self-Check Problems

Section 17.1: Binary Tree Basics
1. How many roots can a tree have? Does a tree have more branches or leaves?

2. Draw a tree that has twice as many leaves as branches and one that has the same number of leaves as branches.

3. a. How many levels does the given tree have?
b. How many branches does it have, and which nodes are they?
c. How many leaves does it have, and which nodes are they?