Exercises 12-16 use the following tree: see image.
Exercises
12.
a.What is the height of the tree?
b.What noes are on Level 3?
c.Which levels have the maximum number of nodes that they could contain?
d.What is the maximum height of a binary search tree containing these nodes? Draw such a tree.
e.What is the minimum height of a binary search tree containing these nodes? Draw such a tree.
13.
a.Trace the path that would be followed in searching for a node containing 61.
b.Trace the path that would be followed in searching for a node containing 28.
14. Show the order in which the nodes in the tree are processed by
a.an inorder traversal of the tree
b.a postorder traversal of the tree.
c.a preorder traversal of the tree.
15. Show how the tree would look after the deletion of 29, 59, and 47.
16. Show how the (original) tree would look after the insertion of nodes containing 63, 77, 76, 48, 9, and 10 (in that order).
Exercises
2. The elements in a binary tree are to be stored in an array, as described in the chapter: Each element is a nonnegative int value.
a.What value can you use as the dummy value, if the binary tree is not complete?
b.Show the contents of the array, given the following tree.
see image.
5. A binary tree is stored in an array called treeNodes, which is indexed from 0 to 99, as described in the chapter. The tree contains 85 elements. Mark each of the following statements as True of False, and correct any false statements.
a.treeNodes[42] is a leaf node.
b.treeNodes[41] has only one child.
c.The right child of treeNodes[12] is treeNodes[25].
d.The subtree rooted at treeNodes[7] is a full binary tree with four levels.
e.The tree has seven levels that are full, and one additional level that contains some elements.
6. A priority queue containing characters is implemented as a heap stored in an array. The precondition states that this priority queue cannot contain duplicate elements. Currently, the priority queue holds 10 elements, as shown below. What values might be stored in array positions 7-9 so that the properties of a heap are satisfied? see image.
10. A priority queue is implemented as a linked list, sorted from largest to smallest element.
a.How would the definition of PQType change?
b.Write the Enqueue operation using this implementation.
c.Write the Dequeue operation using this implementation.
d.Compare the Enqueue and Dequeue operations to those for the heap implementation, in terms of Big-O notation.
15. A priority queue of strings is implemented using a heap. The heap contains the following elements: see image.
a.What feature of these strings is used to determine their priority in the priority queue?
b.Show how the priority queue is affected by adding the string interviewing.