PLEASE CAN SOMEONE HELP ME WITH THIS!!

In this programming exercise, you are required to realize three different ways of tree traversal.

Use an ADT called BinTree to hold the binary tree and an ADT name BTNode to hold the binary tree nodes, you can make use of the code example binary_tree_node.

Each node in the binary tree must contain ONLY 3 data items.

a char variable to contain a single letter from the English alphabet

a pointer variable to point to a left child node

a pointer variable to point to a right child node

The characters to be input will reside in a file called "infile.txt". All valid input will be single alphabetic characters (digits are ignored), separated by one or more blanks. More than one input value may appear on a single line. Multiple lines of input may be present. Blank lines may appear in the input file. The file will not be entirely empty (i.e. there will be at least a single valid alphabetic character). Also we assume that each alphabetic character will appear at most once in the input file.

For each input character, you are to place it into the binary tree. When properly placed, an in-order traversal of the binary tree will allow the data to be printed in non-decreasing order.

Implement the BinTree and BTNode ADTs and their methods to do the following traversals on your binary tree. During any traversal, your algorithm must print the character content out to the screen and to an output file named "outfile.txt". You should always display a copy of the input along with the resultant output. Below are the traversals to implement.

Post-Order Traversal

Pre-Order Traversal

In-Order Traversal

Include necessary comments

Identify 2 test cases other than the examples given below. At least one test case should have more than 2 lines of input. For each of the 2 test cases, show what input you will use and what your expected outputs would be.

Write the program. Run the project, test your project thoroughly by using your test cases. Check whether the expected outputs are the same as the actual outputs. If they are different, either point out the reason why the expected output is not correct or continue debugging.

Do a screen shot of a sample run result of one of your test cases and paste it here. Copy and paste all your source code here.

Below is a suggestion of what would be an acceptable format of output file. Make sure it is well labeled and very easy to understand without having to look at ANYTHING else.

Tree Traversal Report Input Data: m f s d h o u a e g i n q t x Post-Order: a e d g i h f n q o t x u s m Pre-Order : m f d a e h g i s o n q u t x In-Order : a d e f g h i m n o q s t u x

This is the "binary tree code"

#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

// FILE: bintree.template // IMPLEMENTS: The binary_tree node class (see bintree.h for documentation). #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 << std::setw(4*depth) << ""; // Indent 4*depth spaces. std::cout << node_ptr->data( ) << std::endl; print(node_ptr->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( )); } }