[SOLVED] COEN 79 - HW5

Description

 

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. 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)
3. 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. // 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_pt
3. Appendix 1: Bag class with binary search tree.