Write a function that takes a binary search tree as input and produces a linked list of the entries, with the entries sorted (smallest entries at the front of the list and largest entries at the back). Hint: use in-order traversal. Use the Bst bellow for your test data. THE HEADER AND TEMPLATE FILES ARE PROVIDED BELOW

bintree.h

#ifndef BINTREE_H #define BINTREE_H #include // Provides NULL and size_t

namespace main_savitch_10 {

template class binary_tree_node { public: // TYPEDEF typedef Item value_type; // CONSTRUCTOR binary_tree_node( const Item& init_data = Item( ), binary_tree_node* init_left = NULL, binary_tree_node* init_right = NULL ) { data_field = init_data; left_field = init_left; right_field = init_right; } // MODIFICATION MEMBER FUNCTIONS Item& data( ) { return data_field; } binary_tree_node* left( ) { return left_field; } binary_tree_node* right( ) { return right_field; } void set_data(const Item& new_data) { data_field = new_data; } void set_left(binary_tree_node* new_left) { left_field = new_left; } void set_right(binary_tree_node* new_right) { right_field = new_right; } // CONST MEMBER FUNCTIONS const Item& data( ) const { return data_field; } const binary_tree_node* left( ) const { return left_field; } const binary_tree_node* right( ) const { return right_field; } bool is_leaf( ) const { return (left_field == NULL) && (right_field == NULL); } private: Item data_field; binary_tree_node *left_field; binary_tree_node *right_field; };

// NON-MEMBER FUNCTIONS for the binary_tree_node: template void inorder(Process f, BTNode* node_ptr);

template void preorder(Process f, BTNode* node_ptr);

template void postorder(Process f, BTNode* node_ptr);

template void print(binary_tree_node* node_ptr, SizeType depth);

template void tree_clear(binary_tree_node*& root_ptr);

template binary_tree_node* tree_copy(const binary_tree_node* root_ptr);

template std::size_t tree_size(const binary_tree_node* node_ptr); }

#include "bintree.template" #endif

bintree.template

#include // Provides assert #include // Provides NULL, std::size_t #include // Provides std::setw #include // Provides std::cout

namespace main_savitch_10 { template void inorder(Process f, BTNode* node_ptr) // Library facilities used: cstdlib { if (node_ptr != NULL) { inorder(f, node_ptr->left( )); f( node_ptr->data( ) ); inorder(f, node_ptr->right( )); } }

template void postorder(Process f, BTNode* node_ptr) // Library facilities used: cstdlib { if (node_ptr != NULL) { postorder(f, node_ptr->left( )); postorder(f, node_ptr->right( )); f(node_ptr->data( )); } }

template void preorder(Process f, BTNode* node_ptr) // Library facilities used: cstdlib { if (node_ptr != NULL) { f( node_ptr->data( ) ); preorder(f, node_ptr->left( )); preorder(f, node_ptr->right( )); } }

template void print(binary_tree_node* node_ptr, SizeType depth) // Library facilities used: iomanip, iostream, stdlib { if (node_ptr != NULL) { print(node_ptr->right( ), depth+1); std::cout data( ) left( ), depth+1); } } template void tree_clear(binary_tree_node*& root_ptr) // Library facilities used: cstdlib { binary_tree_node* child; if (root_ptr != NULL) { child = root_ptr->left( ); tree_clear( child ); child = root_ptr->right( ); tree_clear( child ); delete root_ptr; root_ptr = NULL; } }

template binary_tree_node* tree_copy(const binary_tree_node* root_ptr) // Library facilities used: cstdlib { binary_tree_node *l_ptr; binary_tree_node *r_ptr;

if (root_ptr == NULL) return NULL; else { l_ptr = tree_copy( root_ptr->left( ) ); r_ptr = tree_copy( root_ptr->right( ) ); return new binary_tree_node( root_ptr->data( ), l_ptr, r_ptr); } }

template size_t tree_size(const binary_tree_node* node_ptr) // Library facilities used: cstdlib { if (node_ptr == NULL) return 0; else return 1 + tree_size(node_ptr->left( )) + tree_size(node_ptr->right( )); } }

10 15 17 4