Serialize and Deserialize a Binary Tree
30 10 50 # # # 20 45 # # 35 # #
# define the C compiler to use
CC = g++
# define any compile-time flags
CFLAGS = -ggdb
# define the compile command by compiler and flags
CC_OPTIONS = $(CC) $(CFLAGS)
# define the C source files
SRCS = binary_tree.cpp main.cpp
# define the C object files
#
# This uses Suffix Replacement within a macro:
# $(name:string1=string2)
# For each word in 'name' replace 'string1' with 'string2'
# Below we are replacing the suffix .c of all words in the macro SRCS
# with the .o suffix
#
OBJS = $(SRCS:.cpp=.o)
# define the executable file
MAIN = BT
#
# The following part of the makefile is generic; it can be used to
# build any executable just by changing the definitions above and by
# deleting dependencies appended to the file from 'make depend'
#
all:$(MAIN)
@echo The $(MAIN) has been compiled!
$(MAIN):$(OBJS)
$(CC_OPTIONS) -o $@ $(OBJS)
# this is a suffix replacement rule for building .o's from .c's
# it uses automatic variables
# $<: the name of the prerequisite of the rule(a .c/cpp file)
# and $@: the name of the target of the rule (a .o file)
# (see the gnu make manual section about automatic variables)
#.c.o:
.cpp.o:
$(CC) $(CFLAGS) -c $< -o $@
clean:
$(RM) $(OBJS) $(MAIN)
# Original makefile
# ------------------------
#main:main.o binary_tree.o
# g++ -ggdb -o main main.o binary_tree.o
#main.o:main.cpp binary_tree.h
# g++ -ggdb -c main.cpp
#binary_tree.o:binary_tree.cpp
# g++ -ggdb -c binary_tree.cpp
#clean:
# rm main.o binary_tree.o main
#include "binary_tree.h"
#include <iostream>
#define TREEFILE "test.tree"
int main(){
std::ifstream in (TREEFILE);
BinaryTree bt;
bt.Deserialize(in);
std::ofstream out (TREEFILE);
bt.Serialize(out);
return 0;
}
#include <fstream>
class BinaryTree
{
private:
struct node
{
node* left;
node* right;
int data;
//constructor
node(int const &d):left(0), right(0), data(d){}
};
node* root;
void Preorder(node *n);
void PreorderWriteBinaryTree(node* n, std::ofstream &fout);
void PreorderReadBinaryTree(node** n, std::ifstream &fin);
bool ReadNext(std::ifstream &fin, int* data, bool* isEndNode);
public:
void Serialize(std::ofstream &fout);
void Deserialize(std::ifstream &fin);
};
#include "binary_tree.h"
#include <iostream> // std::cout
#include <iomanip> // std::setw
#include <string> // std::string
#include <sstream> // std::istringstream
bool
BinaryTree::ReadNext(std::ifstream& fin, int* data, bool* isNumber)
{
if(!fin.is_open() || !fin.good()){
return false;
}
std::string str;
fin >> str; // Read one int/char split by whitespace
std::istringstream input(str); // Use to transfer str to int
*isNumber = (input >> *data); // *data will be 0 if input is not integer
return !fin.eof();
}
void
BinaryTree::PreorderWriteBinaryTree(node* n, std::ofstream &fout)
{
// Remember to add a whitespace used to split the data.
// It's the native split-marker of file reading
if(!n){
fout << "# ";
return;
}
fout << n->data << " ";
PreorderWriteBinaryTree(n->left, fout);
PreorderWriteBinaryTree(n->right, fout);
}
void
BinaryTree::PreorderReadBinaryTree(node** n, std::ifstream &fin)
{
bool isNumber;
int data;
if(!ReadNext(fin, &data, &isNumber) || !isNumber){
return;
}
*n = new node(data);
PreorderReadBinaryTree(&((*n)->left), fin);
PreorderReadBinaryTree(&((*n)->right), fin);
}
void
BinaryTree::Preorder(node* n)
{
if(!n){
return;
}
std::cout << std::setw(4) << n->data;
Preorder(n->left);
Preorder(n->right);
}
void
BinaryTree::Serialize(std::ofstream &fout)
{
// Print the tree first
if(root){
std::cout << "tree: ";
Preorder(root);
std::cout << std::endl;
}else{
std::cout << "empty tree!" << std::endl;
}
if(!fout.is_open()){
std::cout << "file can't be open!" << std::endl;
}
PreorderWriteBinaryTree(root, fout);
if(fout.is_open()){
fout.close();
std::cout << "file has been closed" << std::endl;
}
}
void
BinaryTree::Deserialize(std::ifstream &fin)
{
if(!fin.is_open()){
std::cout << "file can't be open!" << std::endl;
}
PreorderReadBinaryTree(&root, fin);
if(fin.is_open()){
fin.close();
std::cout << "file has been closed" << std::endl;
}
}