Description

Assignment #6 – Practice for Tree Data Structure,

Each question is 3 pts.

1.

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.