1. Please complete the following implementation:
template < class Item >
2.
binary_tree_node <Item>* tree_copy (const binary_tree_node <Item>* root_ptr)
• Using the previous implementation, complete the following function for the bag class given in Appendix 1:
1.
template < class Item >
2.
void bag <Item>::operator = (const bag<Item>& source)
3.
// Header file used: bintree.h
2. For the bag class defined in Appendix 1, please complete the following function:
1. template < class Item >
2. void bag<Item>::insert(const Item& entry)
3. // Postcondition: A new copy of entry has been inserted into the bag.
4. // Header file used: bintree.h
3. Write a function to perform left-right rotation on the following AVL tree. The figure shows the steps. (Note: Please implement the function in two steps: (1) left rotation, (2) right rotation.)
parent
1. template < class Item >
2. binary_tree_node <Item>* left_right_rotation (binary_tree_node <Item>*& parent) 3. {
4. binary_tree_node <Item>* temp;
4. Add the following numbers to an AVL tree. Please draw the final tree. 2, 4, 6, 8, 10, 12, 20, 18, 16, 14
5. The following functions are available:
Also assume the following functions are available:
• binary_tree_node<Item>* left_rotation (binary_tree_node<Item>*& parent)
• binary_tree_node<Item>* right_rotation (binary_tree_node<Item>*& parent)
• binary_tree_node<Item>* left_right_rotation (binary_tree_node<Item>*& parent)
• binary_tree_node<Item>* right_left_rotation (binary_tree_node<Item>*& parent)
Complete the following function, which balances a tree rooted at temp.
1. template < class Item >
2. binary_tree_node<Item>* balance(binary_tree_node <Item>*& temp)
6. Please implement the following function (recursively).
1. template < class Item >
2. void flip(binary_tree_node < Item > * root_ptr)
3. // Precondition: root_ptr is the root pointer of a non-empty binary tree. 4. // Postcondition: The tree is now the mirror image of its original value.
Example:
// 1 1
// / \ / \
// 2 3 3 2
// / \ / \
// 4 5 5 4
1. template < class Item >
2. void flip (binary_tree_node <Item>* root_ptr)
Appendix 1: Bag class with binary search tree.
