(a) Consider a binary min-heap. We have a method that print the keys as encounte

Question

(a) Consider a binary min-heap. We have a method that print the keys as encountered in a preorder traversal. Is the output sorted? Justify your answer. Attempt the same question for inorder and postorder traversal. (b) Propose an efficlent algorithm to find al nodes less than some value X in a binary min- heap. Analyze its complexity. (in Java) a method replaceKey in the MaxHeap class with the following (c) Write signature public void replaceKey(Integer oldKey, Integer newkey) The method will replace the first occurrence of oldKey with the newKey, and restore the Max-Heap property after the change. If the oldKey does not exist in the heap, the method prints an appropriate message and returns without changing the heap. Example: Suppose our binary heap object (bh) has the following keys: 99 64 42 54 32 28 6 19 7 26 4 Then the method call: bh.jeplaceKey (new Integer(54), new Integer(105) should change the keys to: 105 99 42 64 32 28 6 19 726 4 Note: You can assume that the methods perlocateUp and perlocateDown are already implemented in your MaxHeap class

Explanation / Answer

Hi friend, Question is too long.

As per the chegg guide line please post one question in a post.

I have ansered Q1 (Part B).

Please repost other in separate post.

Preorder output is not in sorted order.

PreOrder:

void preorder(Node* root){
   if(root!=NULL){
       printf("%d",root -> data);
       if (root -> left != NULL)
           preorder(root -> left);
       if (root -> right != NULL)
           preorder(root -> right);
       }
   }
}

InOrder:

void inorder(Node* root){
   if(root!=NULL){
       if (root -> left != NULL)
           inorder(root -> left);
       printf("%d",root -> data);
       if (root -> right != NULL)
           inorder(root -> right);
       }
   }
}

PostOrder:

void postorder(Node* root){
   if(root!=NULL){
       if (root -> left != NULL)
           postorder(root -> left);
       if (root -> right != NULL)
           postorder(root -> right);
       }
       printf("%d",root -> data);
   }
}

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.