Previous Section
 < Free Open Study > 
Next Section


Chapter 8

    1. The level of a binary search tree determines the maximum number of comparisons that are required to find an element in the tree.

    2. 100

    3. 7

  1. (c) is the correct answer.

  1. Click To expand
  2. The queue holds the values in the tree so that the user can access them one at a time. A linked structure would require an extra pointer for each value in the tree. If an array-based queue of just the right size could be dynamically allocated, it would be much more efficient. The implementation presented here makes the queue a part of the private data of the tree object, and the number of nodes (data values) is not known at the time of instantiation.

    1. Q, K, and M

    2. B, D, J. M. P, and N

    3. 8

    4. 16

    5. 63

  3. Click To expand
    1. BDJKMNPQRTWY

    2. BJDNPMKRWYTQ

    3. QKDBJMPNTRYW

  4. Click To expand
  1. Click To expand
  2. Click To expand
    1. False

    2. False

    3. True

    4. False

  3. No; an inorder traversal would leave the elements in a sorted order, so that when you went to rebuild the tree, you would have a stalk instead of a tree.

    1. Elements inserted in random order:

      Linked list: O(N)

      Binary search tree: O(log2N)

    2. Elements inserted in order:

      Linked list: O(N)

      Binary search tree: O(N)

    1. Click To expand
    1. void Ancestors(ItemType value); // Prototype
      // Pre:  A node whose info member is value is in the tree.
      // Post: The ancestors of the node whose info member is
      //     value have been printed.
      
    2. template<class ItemType>
      void TreeType<ItemType>::Ancestors(ItemType value)
      {
        TreeNode<NodeType>* location;
      
        while (location->info != value)
        {
          std::cout << location->info << end1;
          if (location->info < value)
              location = location->right;
            else
              location = location->left;
          }
        }
      
  1. template<class ItemType>
    void PrintAncestors(TreeNode<NodeType>* tree, ItemType value) const;
    // Prototype
    template<class ItemType>
    void TreeType<ItemType>::Ancestors(ItemType value) const
    // Calls recursive function PrintAncestors to print the ancestors.
    {
      PrintAncestors(root, value);
    }
    
    template<class ItemType>
    void PrintAncestors(TreeNode<NodeType>* tree, ItemType value) const
    {
      if (tree->info != value)
      {
        std::cout << tree->info << end1;
        if (tree->info < value)
          PrintAncestors(tree->right, value);
        else
          PrintAncestors(tree->left, value);
      }
    }
    
  1. int LeafCount () ;   // Prototype
    // post: function value = number of leaf nodes in the tree.
    template<class ItemType>
    int Count(TreeNode<ItemType>* tree);     // Prototype
    
    template<class ItemType>
    int TreeType<ItemType>::LeafCount()
    // Calls recursive function Count to count the number
    //  of leaf nodes.
    {
      return Count(root);
    }
    
    template<class ItemType>
    int Count(TreeNode<ItemType>* tree)
    {
      if (tree == NULL)
        return 0;
      else if (tree->left == NULL) && (tree->right == NULL)
        return 1;
      else
        return Count(tree->left) + Count(tree->right);
    }
    
  2. int SingleParentCount();   // Prototype
    // Post: Number of nodes with only one child is returned.
    template<class ItemType>
    int SingleCount(TreeNode<ItemType>* tree);      // Prototype
    
    template<class ItemType>
    int TreeType<ItemType>::SingleParentCount()
    // Calls recursive function SingleCount to count the number of nodes
    // with only one child.
    {
      return SingleCount(root);
    }
    
    template<class ItemType>
    int SingleCount(TreeNode<ItemType>* tree)
    {
      if (tree == NULL)
        return 0;
      else if (tree->left == NULL && tree->right != NULL)
        return 1 + Count(tree->right);
      else if (tree->right == NULL && tree->left != NULL)
        return 1 + Count(tree->left);
      else
        return Count(tree->left) + Count(tree->right);
    }
    
  3. template<class ItemType>
    int Count(TreeType<ItemType> tree, ItemType value)
    // Pre:  tree has been initialized.
    // Post: Function value = the number of nodes in tree that contain
    //       values that are greater than value.
    {
      ItemType item;
      bool finished = false; 
      int number = 0;    // Sum of number of items < value
    
      if (tree.IsEmpty())
        return 0;
      else
      {
        tree.ResetTree(IN_ORDER);
        // By using an inorder traversal, the process can stop when
        // a larger value is returned.
        while (!finished)
        {
          tree.GetNextItem(item, finished, IN_ORDER);
          if (item < value)
            number++;
          else
            finished = true;
        }
        return number;
      }
    }
    
  1. template<class ItemType>
    void MakeTree(TreeType<ItemType>& tree, int info[], int length)
    // Creates a binary tree from a sorted array.
    {
      tree.MakeEmpty();
      AddElements(tree, info, 0, length-1);
    }
    
    template<class ItemType>
    void AddElements(TreeType<ItemType>& tree, ItemType info[],
       int fromIndex, int toIndex)
    {
      int midIndex;
    
      if (fromIndex <= toIndex)
      {
         midIndex = (fromIndex + toIndex) / 2;
         tree.InsertItem(info[midIndex]);
         AddElements(tree, info, fromIndex, midIndex - 1);
         // Complete the left subtree.
         AddElements(tree, info, midIndex+1, toIndex);
         // Complete the right subtree.
      }
    }
    
  1. Either the value in node 5 or the value in node 6.

  2. Inorder

  3. Preorder

    1. b, d, and e b.

    2. d, and e

    3. d

    1. Any negative number can be used as a dummy value.

    2. Assume that the dummy value is -1.0.

      Click To expand
  1. Click To expand
  2. Click To expand
    1. True. Its smallest child index would be 85, but the tree contains only 85 elements.

    2. False. treeNodes [41] has two children: treeNodes [83] and treeNodes [84].

    3. False. The left child of treeNodes [12] is treeNodes [25].

    4. True.

    5. False. The tree contains six full levels (containing 63 elements), with 22 additional elements on the seventh level.



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