Trees - Data Structures and Problem Solving Using Java - page 660

figure 18.11
Uses of binary trees:
(a) an expression tree
and (b) a Huffman
coding tree

+

a * a

- d d

b c b c

(a) (b)

to a 1. Thus b is coded as 100. (See Section 12.1 for a discussion of the con-
struction of the optimal tree, that is, the best code.)

Other uses of the binary tree are in binary search trees (discussed in Chap-
ter 19), which allow logarithmic time insertions and accessing of items, and
priority queues, which support the access and deletion of the minimum in a
collection of items. Several efficient implementations of priority queues use
trees (discussed in Chapters 21-23).
Figure 18.12 gives the skeleton for the BinaryNode class. Lines 49-51 indi-
cate that each node consists of a data item plus two links. The constructor,
shown at lines 18 to 20, initializes all the data members of the BinaryNode class.
Lines 22-33 provide accessors and mutators for each of the data members.

An important use of
binary trees is in
other data struc-
tures, notably the
binary search tree
and the priority
queue.

The duplicate method, declared at line 39, is used to replicate a copy of
the tree rooted at the current node. The routines' size and height , declared
at lines 35 and 37, compute the named properties for the node referenced
by parameter t . We implement these routines in Section 18.3. (Recall that
static methods do not require a controlling object.) We also provide, at
lines 42-47, routines that print out the contents of a tree rooted at the cur-
rent node, using various recursive traversal strategies. We discuss tree tra-
versals in Section 18.4. Why do we pass a parameter for size and height
and make them static but use the current object for the traversals and
duplicate ? There is no particular reason; it is a matter of style, and we
show both styles here. The implementations show that the difference
between them occurs when the required test for an empty tree (given by a
null reference) is performed.
In this section we describe implementation of the BinaryTree class. The
BinaryNode class is implemented separately, instead of as a nested class. The
BinaryTree class skeleton is shown in Figure 18.13. For the most part, the rou-
tines are short because they call BinaryNode methods. Line 44 declares the
only data member—a reference to the root node.

Many of the
BinaryNode rou-
tines are recursive.
The BinaryTree
methods use the
BinaryNode rou-
tines on the root .

The BinaryNode
class is imple-
mented separately
from the BinaryTree
class. The only data
member in the
BinaryTree class is
a reference to the
root node.