Java Reference
In-Depth Information
Theorem5.2
The number of empty subtrees in a non-empty binary tree is one
more than the number of nodes in the tree.
Proof1
: Take an arbitrary binary tree T and replace every empty subtree with a
leaf node. Call the new tree T
0
. All nodes originally in T will be internal nodes in
T
0
(because even the leaf nodes of T have children in T
0
). T
0
is a full binary tree,
because every internal node of T now must have two children in T
0
, and each leaf
node in T must have two children in T
0
(the leaves just added). The Full Binary Tree
Theorem tells us that the number of leaves in a full binary tree is one more than the
number of internal nodes. Thus, the number of new leaves that were added to create
T
0
is one more than the number of nodes in T. Each leaf node in T
0
corresponds to
an empty subtree in T. Thus, the number of empty subtrees in T is one more than
the number of nodes in T.
2
Proof2
: By definition, every node in binary tree T has two children, for a total of
2n children in a tree of n nodes. Every node except the root node has one parent,
for a total of n 1 nodes with parents. In other words, there are n 1 non-empty
children. Because the total number of children is 2n, the remaining n + 1 children
must be empty.
2
5.1.2 A Binary Tree Node ADT
Just as a linked list is comprised of a collection of link objects, a tree is comprised
of a collection of node objects. Figure 5.5 shows an ADT for binary tree nodes,
called
BinNode
. This class will be used by some of the binary tree structures
presented later. Class
BinNode
is a generic with parameter
E
, which is the type
for the data record stored in the node. Member functions are provided that set or
return the element value, set or return a reference to the left child, set or return a
reference to the right child, or indicate whether the node is a leaf.
5.2
Binary Tree Traversals
Often we wish to process a binary tree by “visiting” each of its nodes, each time
performing a specific action such as printing the contents of the node. Any process
for visiting all of the nodes in some order is called a traversal. Any traversal that
lists every node in the tree exactly once is called an enumeration of the tree's
nodes. Some applications do not require that the nodes be visited in any particular
order as long as each node is visited precisely once. For other applications, nodes
must be visited in an order that preserves some relationship. For example, we might
wish to make sure that we visit any given node before we visit its children. This is
called a preorder traversal.
