Previous Section
 < Free Open Study > 
Next Section


Exercises

    1. What does the level of a binary search tree mean in relation to its searching efficiency?

    2. What is the maximum number of levels that a binary search tree with 100 nodes can have?

    3. What is the minimum number of levels that a binary search tree with 100 nodes can have?

  1. Which of these formulas gives the maximum total number of nodes in a tree that has N levels? (Remember that the root is Level 0.)

    1. N2 - 1

    2. 2N

    3. 2N - 1

    4. 2N+1

  2. Which of these formulas gives the maximum number of nodes in the Nth level of a binary tree?

    1. N2

    2. 2N

    3. 2N+1

    4. 2N - 1

  3. How many ancestors does a node in the Nth level of a binary search tree have?

    1. How many different binary trees can be made from three nodes that contain the key values 1, 2, and 3?

    2. How many different binary search trees can be made from three nodes that contain the key values 1, 2, and 3?

  4. Draw all possible binary trees that have four leaves where all nonleaf nodes have two children.

  5. The TreeType class used a queue as an auxiliary storage structure for iterating through the elements in the tree. Discuss the relative merits of using a dynamically allocated array-based queue versus a dynamically allocated linked queue.

Answer the questions in Exercises 8-10 independently, using the following tree.

Click To expand
    1. What are the ancestors of node P?

    2. What are the descendants of node K?

    3. What is the maximum possible number of nodes in the tree at the level of node W?

    4. What is the maximum possible number of nodes in the tree at the level of node N?

    5. Insert node O. How many nodes would be in the tree if it were completely full down to and including the level of node O?

  1. Show what the tree would look like after each of the following changes. (Use the original tree to answer each part.)

    1. Add node C.

    2. Add node Z.

    3. Add node X.

    4. Delete node M.

    5. Delete node Q.

    6. Delete node R.

  2. Show the order in which the nodes in the tree are processed by

    1. an inorder traversal of the tree.

    2. a postorder traversal of the tree.

    3. a preorder traversal of the tree.

  3. Draw the binary search tree whose elements are inserted in the following order:

    50 72 96 94 107 26 12 11 9 2 10 25 51 16 17 95

Exercises 12-16 use the following tree.

Click To expand
    1. What is the height of the tree?

    2. What nodes are on Level 3?

    3. Which levels have the maximum number of nodes that they could contain?

    4. What is the maximum height of a binary search tree containing these nodes? Draw such a tree.

    5. What is the minimum height of a binary search tree containing these nodes? Draw such a tree.

    1. Trace the path that would be followed in searching for a node containing 61.

    2. Trace the path that would be followed in searching for a node containing 28.

  1. Show the order in which the nodes in the tree are processed by

    1. an inorder traversal of the tree.

    2. a postorder traversal of the tree.

    3. a preorder traversal of the tree.

  2. Show how the tree would look after the deletion of 29, 59, and 47.

  3. Show how the (original) tree would look after the insertion of nodes containing 63, 77, 76, 48, 9, and 10 (in that order).

  4. True or false?

    1. Invoking the delete function in this chapter might create a tree with more levels than the original tree had.

    2. A preorder traversal processes the nodes in a tree in the exact reverse order that a postorder traversal processes them.

    3. An inorder traversal always processes the elements of a tree in the same order, regardless of the order in which the elements were inserted.

    4. A preorder traversal always processes the elements of a tree in the same order, regardless of the order in which the elements were inserted.

  5. If you wanted to traverse a tree, writing all the elements to a file, and later (the next time you ran the program) rebuild the tree by reading and inserting, would an inorder traversal be appropriate? Why or why not?

    1. One hundred integer elements are chosen at random and inserted into a sorted linked list and a binary search tree. Describe the efficiency of searching for an element in each structure, in terms of Big-O notation.

    2. One hundred integer elements are inserted in order, from smallest to largest, into a sorted linked list and a binary search tree. Describe the efficiency of searching for an element in each structure, in terms of Big-O notation.

  6. The key of each node in a binary search tree is a short character string.

    1. Show how such a tree would look after the following words were inserted (in the order indicated):

      • monkey canary donkey deer zebra yak walrus vulture penguin quail

    2. Show how the tree would look if the same words were inserted in this order:

      • quail walrus donkey deer monkey vulture yak penguin zebra canary

    3. Show how the tree would look if the same words were inserted in this order:

      • zebra yak walrus vulture quail penguin monkey donkey deer canary

  7. Write a function called PtrToSuccessor that finds a node with the smallest key value in a tree, unlinks it from the tree, and returns a pointer to the unlinked node.

  8. Modify the DeleteNode function so that it uses the immediate successor (rather than the predecessor) of the value to be deleted in the case of deleting a node with two children. You should call the function PtrToSuccessor that you wrote in Exercise 21.

  9. Use the Three-Question Method to verify the recursive function Insert.

  10. Use the Three-Question Method to verify the recursive function Delete.

  11. Write IsFull and IsEmpty for the iterative version of class TreeType.

  12. Add a TreeType member function Ancestors that prints the ancestors of a given node whose info member contains value. Do not print value.

    1. Write the declaration.

    2. Write the iterative implementation.

  13. Write a recursive version of the function Ancestors described in Exercise 26.

  14. Write a recursive version of Ancestors (see Exercise 27) that prints out the ancestors in reverse order (first the parent, then the grandparent, and so on).

  15. Add a Boolean member function IsBST to the class TreeType that determines whether a binary tree is a binary search tree.

    1. Write the declaration of the function IsBST. Include adequate comments.

    2. Write a recursive implementation of this function.

  16. Extend the Binary Search Tree ADT to include the member function LeafCount that returns the number of leaf nodes in the tree.

  17. Extend the Binary Search Tree ADT to include the member function SingleParentCount that returns the number of nodes in the tree that have only one child.

  18. Write a client function that returns a count of the nodes that contain a value less than the parameter value.

  19. Extend the Binary Search Tree ADT to include a Boolean function SimilarTrees that receives pointers to two binary trees and determines whether the shapes of the trees are the same. (The nodes do not have to contain the same values, but each node must have the same number of children.)

    1. Write the declaration of the function SimilarTrees as a TreeType member function. Include adequate comments.

    2. Write the body of the function SimilarTrees.

  20. The TreeType member function MirrorImage creates and returns a mirror image of the tree.

    1. Write the declaration of the function MirrorImage. Include adequate comments.

    2. Write the body of the function MirrorImage.

    3. Can the binary tree returned from this function be used for binary searching? If so, how?

  21. Write a client function MakeTree that creates a binary search tree from the elements in a sorted list of integers. You cannot traverse the list inserting the elements in order, as that would produce a tree that has N levels. You must create a tree with at most log2N + 1 levels.

  22. Write a client Boolean function MatchingItems that determines whether a binary search tree and a sequential list contain the same values.

Examine the following binary search tree and answer the questions in Exercises 37-40. The numbers on the nodes are labels so that we can talk about the nodes; they are not key values within the nodes.

Click To expand
  1. If an item is to be inserted whose key value is less than the key value in node 1 but greater than the key value in node 5, where would it be inserted?

  2. If node 1 is to be deleted, the value in which node could be used to replace it?

  3. 4 2 7 5 1 6 8 3 is a traversal of the tree in which order?

  4. 1 2 4 5 7 3 6 8 is a traversal of the tree in which order?

  5. In Chapter 6, we discussed how to store a linked list in an array of nodes using index values as "pointers" and managing our list of free nodes. We can use these same techniques to store the nodes of a binary search tree in an array, rather than using dynamic storage allocation. Free space is linked through the left member.

    1. Show how the array would look after these elements had been inserted in this order:

      Q L W F M R N S

      Be sure to fill in all the spaces. If you do not know the contents of a space, use "?".

      Click To expand
    2. Show the contents of the array after "B" has been inserted and "R" has been deleted.

      Click To expand
    1. Which of the following trees are complete?

    2. Which of the following trees are full?

    Click To expand
  6. 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.

    1. What value can you use as the dummy value, if the binary tree is not complete?

    2. Show the contents of the array, given the tree illustrated below.

    Click To expand
  7. The elements in a complete binary tree are to be stored in an array, as described in the chapter. Each element is a nonnegative int value. Show the contents of the array, given the tree illustrated below.

    Click To expand
  8. Given the array pictured below, draw the binary tree that can be created from its elements. The elements are arranged in the array as discussed in the chapter.

    Click To expand
  9. 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 or False, and correct any false statements.

    1. treeNodes[42] is a leaf node.

    2. treeNodes[41] has only one child.

    3. The right child of treeNodes[12] is treeNodes [25].

    4. The subtree rooted at treeNodes[7] is a full binary tree with four levels.

    5. The tree has seven levels that are full, and one additional level that contains some elements.

  10. Implement the Binary Search Tree ADT as a template class.



Previous Section
 < Free Open Study > 
Next Section
Converted from CHM to HTML with chm2web Pro 2.85 (unicode)