C++ Binary Tree traversal program

comment your code so I understand what is happening. I am having trouble with this class and will upvote clear answer. Thanks

Get familiar with the tree structure and tree traversal. Through this programming exercise, you can further understand and implement different ways of tree traversal.

Description of requirements:

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

Use an abstract data type called BinTree to hold the binary tree and an abstract data type named 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 characters, 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 character). Also we assume that each 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 abstract data types 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

Find 4 test cases and test them and show they work correctly.

Do a screen shot of a sample run result of your test cases

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

HERE IS THE code example binary_tree_node to reference and help build the program

// FILE: bintree.h (part of the namespace main_savitch_10) // PROVIDES: A template class for a node in a binary tree and functions for // manipulating binary trees. The template parameter is the type of data in // each node. // // TYPEDEF for the binary_tree_node template class: // Each node of the tree contains a piece of data and pointers to its // children. The type of the data (binary_tree_node::value_type) is // the Item type from the template parameter. The type may be any of the C++ // built-in types (int, char, etc.), or a class with a default constructor, // and an assignment operator. // // CONSTRUCTOR for the binary_tree_node class: // binary_tree_node( // const item& init_data = Item( ), // binary_tree_node* init_left = NULL, // binary_tree_node* init_right = NULL // ) // Postcondition: The new node has its data equal to init_data, // and it's child pointers equal to init_left and init_right. // // MEMBER FUNCTIONS for the binary_tree_node class: // const item& data( ) const <----- const version // and // Item& data( ) <----- non-const version // Postcondition: The return value is a reference to the data from // this binary_tree_node. // // const binary_tree_node* left( ) const <----- const version // and // binary_tree_node* left( ) <----- non-const version // and // const binary_tree_node* right( ) const <----- const version // and // binary_tree_node* right( ) <----- non-const version // Postcondition: The return value is a pointer to the left or right child // (which will be NULL if there is no child). // // void set_data(const Item& new_data) // Postcondition: The binary_tree_node now contains the specified new data. // // void set_left(binary_tree_node* new_link) // and // void set_right(binary_tree_node* new_link) // Postcondition: The binary_tree_node now contains the specified new link // to a child. // // bool is_leaf( ) // Postcondition: The return value is true if the node is a leaf; // otherwise the return value is false. // // NON-MEMBER FUNCTIONS to maniplulate binary tree nodes: // tempate // void inorder(Process f, BTNode* node_ptr) // Precondition: node_ptr is a pointer to a node in a binary tree (or // node_ptr may be NULL to indicate the empty tree). // Postcondition: If node_ptr is non-NULL, then the function f has been // applied to the contents of *node_ptr and all of its descendants, using // an in-order traversal. // Note: BTNode may be a binary_tree_node or a const binary tree node. // Process is the type of a function f that may be called with a single // Item argument (using the Item type from the node). // // tempate // void postorder(Process f, BTNode* node_ptr) // Same as the in-order function, except with a post-order traversal. // // tempate // void preorder(Process f, BTNode* node_ptr) // Same as the in-order function, except with a pre-order traversal. // // template // void print(const binary_tree_node* node_ptr, SizeType depth) // Precondition: node_ptr is a pointer to a node in a binary tree (or // node_ptr may be NULL to indicate the empty tree). If the pointer is // not NULL, then depth is the depth of the node pointed to by node_ptr. // Postcondition: If node_ptr is non-NULL, then the contents of *node_ptr // and all its descendants have been written to cout with the << operator, // using a backward in-order traversal. Each node is indented four times // its depth. // // template // void tree_clear(binary_tree_node*& root_ptr) // Precondition: root_ptr is the root pointer of a binary tree (which may // be NULL for the empty tree). // Postcondition: All nodes at the root or below have been returned to the // heap, and root_ptr has been set to NULL. // // template // binary_tree_node* tree_copy(const binary_tree_node* root_ptr) // Precondition: root_ptr is the root pointer of a binary tree (which may // be NULL for the empty tree). // Postcondition: A copy of the binary tree has been made, and the return // value is a pointer to the root of this copy. // // template // size_t tree_size(const binary_tree_node* node_ptr) // Precondition: node_ptr is a pointer to a node in a binary tree (or // node_ptr may be NULL to indicate the empty tree). // Postcondition: The return value is the number of nodes in the tree.

#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 tree_clear(binary_tree_node*& root_ptr);

template binary_tree_node* tree_copy(const binary_tree_node* root_ptr);

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); } } }

#endif