I need some help answering these questions in my Data Structures class. Please H
ID: 3560595 • Letter: I
Question
I need some help answering these questions in my Data Structures class. Please Help!!!
public static boolean has10(IntBTNode root)
// Precondition: root is the root reference of a binary tree (but
// NOT NECESSARILY a search tree).
// Postcondition: The return value indicates whether 10 appears somewhere
// in the tree. NOTE: If the tree is empty, the method returns false.
public static boolean all10(IntBTNode root)
// Precondition: root is the root reference of a binary tree (but
// NOT NECESSARILY a search tree).
// Postcondition: The return value is true if every node in the tree
// contains 10. NOTE: If the tree is empty, the method returns true.
public static int max(BTNode root)
// Precondition: root is the root reference of a nonempty binary SEARCH
// tree.
// Postcondition: The return value is the largest value in the tree.
Explanation / Answer
1)
public static boolean has10(IntBTNode node)
{
if(node == null)
return false;
if(node.data == 10){
return true;
}else{
if(node.left != null)
return has10(node.left);
if(node.right != null)
return has10(node.right);
}
return false;
}
2)
public static boolean all10(IntBTNode node)
{
if(node == null)
return true;
if(node.data == 10){
if(node.left == null)
return true;
else
return all10(node.left);
if(node.right == null)
return true;
else
return all10(node.right);
}
return false;
}
3)
public static int max(BTNode root)
{
BTNode node = root;
while (node.right != null) {
node = node.right;
}
return(node.data);
}
4)
A binary heap is a complete binary tree which satisfies the heap ordering property. The ordering can be one of two types:
1) Min-heap property: the value of each node is greater than or equal to the value of its parent, with the minimum-value element at the root.
2) Max-heap property: the value of each node is less than or equal to the value of its parent, with the maximum-value element at the root.
5)
BSTNode deleteNode(BSTNode root, int data)
1) if root is null
return root
2) if data is less than root.data
root.left <- deleteNode(root.left, data)
3) else if data is greater than root.data
root.right <- deleteNode(root.right, data)
4) else
5) (Tree has two children)
Node temp <- find min value of root.right
6) (Copy the inorder successor's content to this node)
root.data <- temp.data
7) (Delete the inorder successor)
root.right <- deleteNode(root.right, temp.data)
8) return root
6)
An upward reheapification stops :
i) when the new node inserted undergoing an upward reheapification reaches the root
ii) or when the new node's parent has a value greater than or equal to the new node's value.
A downward reheapification stops :
i) when the new node (inserted at root undergoing an downward reheapification) reaches a leaf
ii) it has a value that is greater or equal to all its children.