Java Reference
In-Depth Information
The program obtains a Huffman coding tree based on
counts
(line 14). The tree con-
sists of linked nodes. The
Node
class is defined in lines 102-118. Each node consists of
properties
element
(storing character),
weight
(storing weight of the subtree under this
node),
left
(linking to the left subtree),
right
(linking to the right subtree), and
code
(storing the Huffman code for the character). The
Tree
class (lines 76-119) contains the
root property. From the root, you can access all the nodes in the tree. The
Tree
class imple-
ments
Comparable
. The trees are comparable based on their weights. The compare order
is purposely reversed (lines 93-100) so that the smallest-weight tree is removed first from
the heap of trees.
The
getHuffmanTree
method returns a Huffman coding tree. Initially, the single-node
trees are created and added to the heap (lines 50-54). In each iteration of the
while
loop (lines
56-60), two smallest-weight trees are removed from the heap and are combined to form a big
tree, and then the new tree is added to the heap. This process continues until the heap contains
just one tree, which is our final Huffman tree for the text.
The
assignCode
method assigns the code for each node in the tree (lines 34-45). The
getCode
method gets the code for each character in the leaf node (lines 26-31). The element
codes[i]
contains the code for character
(char)i
, where
i
is from
0
to
255
. Note that
codes[i]
is
null
if
(char)i
is not in the text.
Node
class
Tree
class
getHuffmanTree
assignCode
getCode
25.18
✓
✓
Every internal node in a Huffman tree has two children. Is it true?
Check
25.19
What is a greedy algorithm? Give an example.
Point
25.20
If the
Heap
class in line 50 in Listing 25.10 is replaced by
java.util.PriorityQueue
, will the program still work?
K
EY
T
ERMS
binary search tree
930
Huffman coding 954
inorder traversal 933
postorder traversal 933
preorder traversal
binary tree 930
breadth-first traversal
934
depth-first traversal
934
934
greedy algorithm
956
tree traversal
933
C
HAPTER
S
UMMARY
1.
A
binary search tree
(BST) is a hierarchical data structure. You learned how to define
and implement a BST class, how to insert and delete elements into/from a BST, and
how to traverse a BST using
inorder
,
postorder
,
preorder
, depth-first, and breadth-first
searches.
2.
An iterator is an object that provides a uniform way of traversing the elements in a con-
tainer, such as a set, a list, or a
binary tree
. You learned how to define and implement
iterator classes for traversing the elements in a binary tree.
3.
Huffman coding
is a scheme for compressing data by using fewer bits to encode char-
acters that occur more frequently. The codes for characters are constructed based on the
occurrence of characters in the text using a binary tree, called the
Huffman coding tree
.
Q
UIZ
Search WWH ::
Custom Search