So I have been asked to write a template class for a binary tree (easy) the hard part is that the nodes have to be written into a file and read in the same exact positions they were in when they were stored. I looked at the array solution with the 2i and 2i+1 concept, but I don't think that works here because the user can add nodes wherever he/she wants to.

I then tried the boost library but I'm getting many errors now. Please help me out. I would prefer to use the boost serialization library. I've tried to have the template class derive from a base class, but that didn't work well.

It is a bit long but I would really like to learn how the boost library serialization works with this. I provided all my files below in the attachments but only copied the binary tree template class to the post. Thank you for your time.

#include <cstdlib>  // Provides NULL and size_t
#include <iostream>
#include <fstream>
#include <list>
#include <boost/archive/tmpdir.hpp>
#include <boost/archive/text_iarchive.hpp>
#include <boost/archive/text_oarchive.hpp>
#include <boost/serialization/base_object.hpp>
#include <boost/serialization/utility.hpp>
#include <boost/serialization/list.hpp>
#include <boost/serialization/assume_abstract.hpp>
using namespace std;
using namespace boost::serialization;

template <class Item>
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 )
    {
               root = 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 = Item( )) { 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); }

        // ORGANIZATION AND PRINT
        void printInOrder(binary_tree_node *node)
        {
            if(node->left() != NULL)
                printInOrder(node->left());
            //display current iteration
            cout << node->data() << endl;

            if(node->right() != NULL)
                printInOrder(node->right());
        }

        void insert_leaf(string animal, bool answer, string question)
        {
            animal = animal.insert(0, "Are you a(n) ");
            animal = animal.append("?!");

            binary_tree_node<string>
                    *question_leaf = new binary_tree_node<string>(question),
                    *animal_leaf = new binary_tree_node<string>(animal),
                    *placeholder = new binary_tree_node<string>(this->data());

            if (answer == true)
            {
                this->set_right(placeholder);
                this->set_left(animal_leaf);
                this->set_data(question_leaf->data());
            }

            if (answer == false)
            {
                this->set_left(placeholder);
                this->set_right(animal_leaf);
                this->set_data(question_leaf->data());
            }
        }

        //BOOSTLIB - SERIALIZATION FUNCTIONS
        void saveTree()
        {
            saveLists(root);
            ofstream ofs;
            ofs.open("animalgame.txt");
            boost::archive::text_oarchive oa(ofs);
            // write class instance to archive
            oa << itemList;
            oa << ptrList;
            // archive and stream closed when destructors are called
            ofs.close();
        }
        void restoreTree()
        {
            // create and open an archive for input
            ifstream ifs;
            ifs.open("animalgame.txt");
            boost::archive::text_iarchive ia(ifs);
            // read class state from archive
            ia >> itemList;
            ia >> ptrList;
            // archive and stream closed when destructors are called
            ifs.close();
        }

    private:
    Item data_field;
        binary_tree_node *root;
    binary_tree_node *left_field;
    binary_tree_node *right_field;
        list<Item> itemList;
        list<binary_tree_node*> ptrList;

        //BOOSTLIB - SERIALIZATION FUNCTIONS
        friend class boost::serialization::access;
        template<class Archive>

        void serialize(Archive & ar, const unsigned int version)
        {
            ar & itemList;
            ar & ptrList;
        }
        void saveLists(binary_tree_node *node)
        {
            if(node->left() != NULL){
                itemList.push_back(node->data());
                ptrList.push_back(node);
                saveLists(node->left());
            }
            if(node->right() != NULL){
                itemList.push_back(node->data());
                ptrList.push_back(node);
                saveLists(node->right());
            }
        }
};

Edited 4 Years Ago by mike_2000_17: Fixed formatting

Attachments
#ifndef BINTREE_H
#define BINTREE_H
#include <cstdlib>  // Provides NULL and size_t
#include <iostream>
#include <fstream>
#include <list>
#include <boost/archive/tmpdir.hpp>
#include <boost/archive/text_iarchive.hpp>
#include <boost/archive/text_oarchive.hpp>
#include <boost/serialization/base_object.hpp>
#include <boost/serialization/utility.hpp>
#include <boost/serialization/list.hpp>
#include <boost/serialization/assume_abstract.hpp>
using namespace std;
using namespace boost::serialization;

template <class Item>
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 )
	{
               root = 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 = Item( )) { 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); }

        // ORGANIZATION AND PRINT
        void printInOrder(binary_tree_node *node)
        {
            if(node->left() != NULL)
                printInOrder(node->left());
            //display current iteration
            cout << node->data() << endl;

            if(node->right() != NULL)
                printInOrder(node->right());
        }

        void insert_leaf(string animal, bool answer, string question)
        {
            animal = animal.insert(0, "Are you a(n) ");
            animal = animal.append("?!");

            binary_tree_node<string>
                    *question_leaf = new binary_tree_node<string>(question),
                    *animal_leaf = new binary_tree_node<string>(animal),
                    *placeholder = new binary_tree_node<string>(this->data());

            if (answer == true)
            {
                this->set_right(placeholder);
                this->set_left(animal_leaf);
                this->set_data(question_leaf->data());
            }

            if (answer == false)
            {
                this->set_left(placeholder);
                this->set_right(animal_leaf);
                this->set_data(question_leaf->data());
            }
        }

        //BOOSTLIB - SERIALIZATION FUNCTIONS
        void saveTree()
        {
            ofstream ofs;
            ofs.open("animalgame.txt");
            boost::archive::text_oarchive oa(ofs);
            // write class instance to archive
            oa << itemList;
            oa << ptrList;
            // archive and stream closed when destructors are called
            ofs.close();
        }
        void restoreTree()
        {
            // create and open an archive for input
            ifstream ifs;
            ifs.open("animalgame.txt");
            boost::archive::text_iarchive ia(ifs);
            // read class state from archive
            ia >> itemList;
            ia >> ptrList;
            // archive and stream closed when destructors are called
            ifs.close();
        }

    private:
	Item data_field;
        binary_tree_node *root;
	binary_tree_node *left_field;
	binary_tree_node *right_field;
        list<Item> itemList;
        list<binary_tree_node*> ptrList;

        //BOOSTLIB - SERIALIZATION FUNCTIONS
        friend class boost::serialization::access;
        template<class Archive>

        void serialize(Archive & ar, const unsigned int version)
        {
            ar & itemList;
            ar & ptrList;
        }
        void saveLists(binary_tree_node *node)
        {
            if(node->left() != NULL){
                itemList.push_back(node->data());
                ptrList.push_back(node);
                saveLists(node->left());
            }
            if(node->right() != NULL){
                itemList.push_back(node->data());
                ptrList.push_back(node);
                saveLists(node->right());
            }
        }
};

#endif
#ifndef _GAME_H
#define	_GAME_H

#include "bintree.h"
#include <stdlib.h>
#include <string>
#include <sstream>
#include <iostream>
using namespace std;

bool inquire(string temp)
{
    string user_input;
    cout << temp << "... \n";
    cin >> user_input;

    if ((user_input == "yes") || (user_input == "Yes") || (user_input == "YES")
       || (user_input == "y") || (user_input == "Y"))
        return true;
    else
        return false;
}

void instruct(){
    cout << "\n This is an animal guessing game.  You can pick any animal "
            "you would like and I will try my best to geuss it correctly... I"
            " will ask you a serious of questions in hopes I can get closer and"
            "closer to the right answer.  Please answer with only a [Y/N] "
            "response? OK, Ready? Let's begin! \n" << endl;
}

void learn(binary_tree_node<string>* leaf_ptr)
{
    //intialize the needed variables for the info to add to the tree
    string animal, question;
    bool answer;

    cout << " I give up, what animal are you? ";
    cin.ignore();
    getline( cin, animal );
    //find out the question to insert into the tree
    cout << "As a " << animal << ", please type a Yes/No question that will"
            " distinguish you from a(n) " << leaf_ptr->data() << "...  ";
    getline( cin, question );
    //confirm the yes/no answer from the user
    cout << "As a " << animal << ", " << question << " ";
    answer = inquire("--Please answer Yes or No ");

    //call the insert_leaf function from bintree.h
    leaf_ptr->insert_leaf(animal, answer, question);
}

void ask_and_move(binary_tree_node<string>*& current_ptr)
{
    //retrieve the initial boolean value of the question at hand
    bool answer = inquire(current_ptr->data());
    binary_tree_node<string> *route = current_ptr;
    //error checkto see if it is a leaf or not and which question to ask next
    if (current_ptr->is_leaf() == true)
    {
        if (answer == false)
            learn(current_ptr);
        else
            cout << "\n\n Yay!! I win! \n\n" << endl;
    } else {
        
        if (answer == true){
            route = current_ptr->left();
            ask_and_move(route);
        }
        if(answer == false){
            route = current_ptr->right();
            ask_and_move(route);
        }
    }
}

void play(binary_tree_node<string>*& current_ptr)
{
    if (inquire("Think of an animal and enter 'Y' to start") == true)
        ask_and_move(current_ptr);
}

binary_tree_node<string> *buildTree()
{
    //initiliaze the main nodes to build a foundation
    binary_tree_node<string> 
       *root = new binary_tree_node<string>("Are you a mammal?"),
       *left_node = new binary_tree_node<string>("Are you bigger than a cat?"),
       *right_node = new binary_tree_node<string>("Can you breath underwater?");

    //set the left and right leafs of the root node
    root->set_left(left_node);
    root->set_right(right_node);

    //configure the leafs of root's left node
    binary_tree_node<string> 
          *left_animalA = new binary_tree_node<string>("Elephant?"),
          *left_animalB = new binary_tree_node<string>("Rat?");

    left_node->set_left(left_animalA);
    left_node->set_right(left_animalB);

    //configure the leafs of root's right node
    binary_tree_node<string> 
          *right_animalA = new binary_tree_node<string>("Fish?"),
          *right_animalB = new binary_tree_node<string>("Bird?");

    right_node->set_left(right_animalA);
    right_node->set_right(right_animalB);

    return root;
}

#endif
#include "game.h"
#include "bintree.h"

int main() {

    cout << "Hello Animal World" << endl;

    //defining the root of the tree
    binary_tree_node<string> *root;
    bool input;

    //display instruction to human
    instruct();

    input = inquire("Would you like to load the previous game? (Y/N)...");

    //load file if user chooses to
    if (input == true)
        root = buildTree();
    //set up the questions
    if (input == false)
        root->restoreTree();

    //root->printInOrder(root);

    // main game loop
    do {
        play(root);     //play the game -- travel the tree
    } while (inquire("Shall we play again, my friend? [Yes, No]  "));

    cout << "It was nice of you to play with me, Farewell" << endl;
    return(EXIT_SUCCESS);
}

heres a couple of build errors:

build/Debug/GNU-Linux-x86/main.o: In function `boost::serialization::void_upcast(boost::serialization::extended_type_info const&, boost::serialization::extended_type_info const&, void*)':
/usr/local/include/boost/serialization/void_cast.hpp:66: undefined reference to `boost::serialization::void_upcast(boost::serialization::extended_type_info const&, boost::serialization::extended_type_info const&, void const*)'
build/Debug/GNU-Linux-x86/main.o: In function `text_iarchive':
/usr/local/include/boost/archive/text_iarchive.hpp:129: undefined reference to `boost::archive::text_iarchive_impl<boost::archive::text_iarchive>::text_iarchive_impl(std::basic_istream<char, std::char_traits<char> >&, unsigned int)'
/usr/local/include/boost/archive/text_iarchive.hpp:129: undefined reference to `boost::archive::detail::shared_ptr_helper::shared_ptr_helper()'
build/Debug/GNU-Linux-x86/main.o: In function `~text_iarchive':
/usr/local/include/boost/archive/text_iarchive.hpp:131: undefined reference to `boost::archive::detail::shared_ptr_helper::~shared_ptr_helper()'
/usr/local/include/boost/archive/text_iarchive.hpp:131: undefined reference to `boost::archive::detail::shared_ptr_helper::~shared_ptr_helper()'
build/Debug/GNU-Linux-x86/main.o: In function `~text_iarchive_impl':
/usr/local/include/boost/archive/text_iarchive.hpp:80: undefined reference to `boost::archive::basic_text_iprimitive<std::basic_istream<char, std::char_traits<char> > >::~basic_text_iprimitive()'

This article has been dead for over six months. Start a new discussion instead.