Java Reference
In-Depth Information
C
A
F
B
E
H
G
D
I
Figure6.18
A sample tree for Exercise 6.16.
6.19 Draw the general tree represented by the following sequential representation
for general trees illustrated by Example 6.8:
XPC)Q)RV)M))))
6.20 (a) Write a function to decode the sequential representation for binary trees
illustrated by Example 6.5. The input should be the sequential repre-
sentation and the output should be a pointer to the root of the resulting
binary tree.
(b) Write a function to decode the sequential representation for full binary
trees illustrated by Example 6.6. The input should be the sequential
representation and the output should be a pointer to the root of the re-
sulting binary tree.
(c) Write a function to decode the sequential representation for general
trees illustrated by Example 6.8. The input should be the sequential
representation and the output should be a pointer to the root of the re-
sulting general tree.
6.21 Devise a sequential representation for Huffman coding trees suitable for use
as part of a file compression utility (see Project 5.7).
6.8
Projects
6.1 Write classes that implement the general tree class declarations of Figure 6.2
using the dynamic “left-child/right-sibling” representation described in Sec-
tion 6.3.4.
6.2 Write classes that implement the general tree class declarations of Figure 6.2
using the linked general tree implementation with child pointer arrays of Fig-
ure 6.12. Your implementation should support only fixed-size nodes that
do not change their number of children once they are created. Then, re-
implement these classes with the linked list of children representation of
