Custom Generic Data Structures - Java: How to Program Early Objects - page 909

b) While there are nodes left in the queue, do the following:
Get the next node in the queue.
Print the node's value.
If the reference to the left child of the node is not null:
Insert the left child node in the queue.
If the reference to the right child of the node is not null:
Insert the right child node in the queue.
Write meth od levelOrder to perform a level-order traversal of a binary tree object. Modify
the program of Figs. 21.17 and 21.18 to use this method. [ Note: You'll also need to use the queue-
processing methods of Fig. 21.13 in this program.]
21.25 (Printing Trees) Modify class Tree of Fig. 21.17 to include a recursive outputTree method
to display a binary tree object. The method should output the tree row by row, with the top of the
tree at the left of the screen and the bottom of the tree toward the right. Each row is output verti-
cally. For example, the binary tree illustrated in Fig. 21.20 is output as shown in Fig. 21.21.
The rightmost leaf node appears at the top of the output in the rightmost column and the
root node appears at the left of the output. Each column starts five spaces to the right of the pre-
ceding column. Method outputTree should receive an argument totalSpaces representing the
number of spaces preceding the value to be output. (This variable should start at zero so that the
root node is output at the left of the screen.) The method uses a modified inorder traversal to out-
put the tree—it starts at the rightmost node in the tree and works back to the left. The algorithm is
as follows:

99

97

92

83

72

71

69

49

44

40

32

28

19

18

11

Fig. 21.21 | Sample output of recursive method outputTree .

While the reference to the current node is not null, perform the following:
Recursively call outputTree with the right subtree of the current node and
totalSpaces + 5 .
Use a for statement to count from 1 to totalSpaces and output spaces.
Output the value in the current node.
Set the reference to the current node to refer to the left subtree of the current node.
Increment totalSpaces by 5 .
21.26 (Insert/Delete Anywhere in a Linked List) Our linked-list class allowed insertions and dele-
tions at only the front and the back of the linked list. These capabilities were convenient for us when
we used inheritance or composition to produce a stack class and a queue class with minimal code
simply by reusing the list class. Linked lists are normally more general than those we provided. Mod-
ify the linked-list class we developed in this chapter to handle insertions and deletions anywhere in
the list. Create diagrams comparable to Figs. 21.6 ( insertAtFront ), 21.7 ( insertAtBack ), 21.8