Created
January 19, 2015 14:02
-
-
Save ChunMinChang/0a43bc8e9ac5e32c3071 to your computer and use it in GitHub Desktop.
Serialize and Deserialize a Binary Tree
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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; | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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); | |
}; |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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; | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# 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 |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
30 10 50 # # # 20 45 # # 35 # # |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment