The program of Figs. 21.15 and 21.16 illustrated three recursive methods of traversing a binary tree—inorder, preorder and postorder traversals. This exercise presents the level-order traversal of a binary tree, in which the node values are printed level by level, starting at the root-node level. The nodes on each level are printed from left to right. The level-order traversal is not a recursive algorithm. It uses a queue object to control the output of the nodes. The algorithm is shown in Fig. 21.22. Write method levelOrder to perform a level-order traversal of a binary tree object. Modify the program of Figs. 21.15 and 21.16 to use this method.

Fig. 21.22

Fig. 21.15

Fig. 21.16

Transcribed Image Text:

I 2 3 4 5 6 7 8 9 10 II Insert the root node in the queue. 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.