ven the following C++ structure definition struct avl tree node double data; int
ID: 3874064 • Letter: V
Question
ven the following C++ structure definition struct avl tree node double data; int balance; avl tree_ node *left; avl_tree_node right; 1i If you have an AVL search tree of nodes from the above structure, with a root node pointer called root, write the JAVA functions defined below a. void tree_print (avl_tree_node* root node) Precondition: root_node is the root pointer of the AVL tree or NULL if empty. Postcondition: The data from the nodes in the tree have been printed in-order n: root_node is the root pointer of the AVL tree or NULL if empty. Postcondition: All nodes at the root and below have been returned to the Heap b. void tree_clear (avl_tree_node & root_node) Preconditio (i.e. deleted), and root_node has been set to NULLExplanation / Answer
Answer for the given question:
I have written this below code as per given condistions and let me know if you have any quiries.
As per given AVL Node structure printing data in In-Order Format.
Code for print AVL elements in In-Order format.
public void InOrder(avl_tree_node root) {
if (root != null) {
InOrder(root.left);
System.out.printf("%d ", root.data);
InOrder(root.right);
}
}
Code for clear the data from avl tree:
private avl_tree_node deleteNode(avl_tree_node root, double value) {
// STEP 1: PERFORM STANDARD BST DELETE
if (root == null)
return root;
// If the value to be deleted is smaller than the root's value,
// then it lies in left subtree
if ( value < root.value )
root.left = deleteNode(root.left, value);
// If the value to be deleted is greater than the root's value,
// then it lies in right subtree
else if( value > root.value )
root.right = deleteNode(root.right, value);
// if value is same as root's value, then This is the avl_tree_node
// to be deleted
else {
// avl_tree_node with only one child or no child
if( (root.left == null) || (root.right == null) ) {
avl_tree_node temp;
if (root.left != null)
temp = root.left;
else
temp = root.right;
// No child case
if(temp == null) {
temp = root;
root = null;
}
else // One child case
root = temp; // Copy the contents of the non-empty child
temp = null;
}
else {
// node with two children: Get the inorder successor (smallest
// in the right subtree)
Node temp = minValueNode(root.right);
// Copy the inorder successor's data to this node
root.value = temp.value;
// Delete the inorder successor
root.right = deleteNode(root.right, temp.value);
}
}
// If the tree had only one node then return
if (root == null)
return root;
// STEP 2: UPDATE HEIGHT OF THE CURRENT NODE
root.height = Math.max(height(root.left), height(root.right)) + 1;
// STEP 3: GET THE BALANCE FACTOR OF THIS NODE (to check whether
// this node became unbalanced)
int balance = getBalance(root);
// If this node becomes unbalanced, then there are 4 cases
// Left Left Case
if (balance > 1 && getBalance(root.left) >= 0)
return rightRotate(root);
// Left Right Case
if (balance > 1 && getBalance(root.left) < 0) {
root.left = leftRotate(root.left);
return rightRotate(root);
}
// Right Right Case
if (balance < -1 && getBalance(root.right) <= 0)
return leftRotate(root);
// Right Left Case
if (balance < -1 && getBalance(root.right) > 0) {
root.right = rightRotate(root.right);
return leftRotate(root);
}
return root;
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.