ChunMinChang
1/19/2015 - 2:02 PM

Serialize and Deserialize a Binary Tree

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