#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <algorithm>
#include <stdexcept>
Brings all the named entities from std namespace into current declarative region
using namespace std;
This is the node structure we use to store the values
and form the binary tree. For the simplicity, we use
int data type to store the node data.
struct node {
int val;
struct node *left;
struct node *right;
};
It prints the vector contents for debug purpose.
void printVector(vector<node *> list)
{
for (vector<node *>::const_iterator i = list.begin(); i != list.end(); ++i)
{
if (NULL != *i)
cout << "[" << (*i)->val << "] -> ";
else
cout << "[EMPTY] -> ";
}
cout << "NULL" << endl;
}
The input vector has all the nodes of a certain level (or depth)
in the given tree, stored from left to right. This function is
capable of printing either in the same order as the vector is created
or in reverse order.
void printLevels(vector<node *>& level, int count, int forward)
{
if (1 == forward) { // Print vector as it is
for(vector<node *>::iterator it = level.begin(); it != level.end(); ++it) {
if (*it)
cout << (*it)->val << " ";
else
cout << "- "; // Empty Node
}
} else { // Print vector in reverse order
for(vector<node *>::reverse_iterator it = level.rbegin(); it != level.rend(); ++it) {
if (*it)
cout << (*it)->val << " ";
else
cout << "- "; // Empty Node
}
}
cout << endl;
}
The main function to trave level by level.
void traverse(node *binaryTree, bool ziczac)
{
string zz = ziczac? "True":"False";
cout << "ZicZac: [" << zz << "]" << endl;
int count = 1; // Initial count for the ROOT node (Level 1)
int countNext = 0; // Node count in the Next Level
int forward = 1; // Decides how to print the list
vector<node *> nodeList; // Store nodes level-by-level
node *tmp = NULL; // Store the node pointer temporarily
// Push the ROOT
nodeList.push_back(binaryTree);
while (0 != count) {
// Print the nodes from the current level
printLevels(nodeList, count, forward);
// Iterate the nodes from current level and get the nodes from
// the next level
countNext = 0;
for (int i=0; i<count;){
tmp = nodeList.front();
// Remove the node which is getting processed
nodeList.erase(nodeList.begin());
// Node is NULL. Don't count the NULL nodes
if (NULL == tmp) {
nodeList.push_back(NULL);
nodeList.push_back(NULL);
} else {
i++;
// Check the left child node
if (tmp->left) {
countNext++;
// Push it to the list
nodeList.push_back(tmp->left);
} else {
nodeList.push_back(NULL);
}
// Check the right child node
if (tmp->right) {
countNext++;
// Push it to the list
nodeList.push_back(tmp->right);
} else {
nodeList.push_back(NULL);
}
}
}
// update the current with the level count from the next level
count = countNext;
if (true == ziczac) {
// Toggle the way the level is getting printed
forward = (forward ^ 0x1) & 0x1;
}
}
}
Read the file with the following format,('|' is the delimitor)
1
2|3
4|5| |7
8|9|0|1| | |2|3
and create the binary tree
node *createBinaryTreeFromFile(string filename)
{
node *binaryTree = NULL;
vector<node *> nodeList;
vector<node *> childNodeList;
vector<string> stringList;
string line;
try {
// Open the given file
ifstream inFile (filename);
while ( getline (inFile, line) )
{
// First Line => ROOT node
if (NULL == binaryTree) {
binaryTree = new node;
binaryTree->val = stoi(line);
binaryTree->right = NULL;
binaryTree->left = NULL;
nodeList.push_back(binaryTree);
} else {
stringList.clear();
string::size_type prev_pos = 0, pos = 0;
// Split the line with '|' delimitor
while( (pos = line.find('|', pos)) != string::npos )
{
std::string substring( line.substr(prev_pos, pos-prev_pos) );
stringList.push_back(substring);
prev_pos = ++pos;
}
string substring( line.substr(prev_pos, pos-prev_pos) ); // Last word
stringList.push_back(substring);
// Create the binary tree here (level by level)
vector<string>::iterator itStringList = stringList.begin();
while (!nodeList.empty()) {
if (itStringList >= stringList.end())
break;
if (NULL == *(nodeList.begin())) {
itStringList = itStringList + 2;
} else {
// Left Node
try{
int val = stoi(*itStringList);
node *tmp = new node;
tmp->val = val;
tmp->left = NULL;
tmp->right = NULL;
(*(nodeList.begin()))->left = tmp;
itStringList++;
nodeList.push_back(tmp);
} catch (const invalid_argument& ia) {
cerr << "Invalid argument: " << ia.what() << '\n';
nodeList.push_back(NULL);
itStringList++;
}
// Right Node
try{
int val = stoi(*itStringList);
node *tmp = new node;
tmp->val = val;
tmp->left = NULL;
tmp->right = NULL;
(*(nodeList.begin()))->right = tmp;
itStringList++;
nodeList.push_back(tmp);
} catch (const invalid_argument& ia) {
cerr << "Invalid argument: " << ia.what() << '\n';
nodeList.push_back(NULL);
itStringList++;
}
}
// Remove the node which is getting processed
nodeList.erase(nodeList.begin());
}
}
}
inFile.close();
} catch (ifstream::failure e) {
cerr << e.what() << endl;
}
// Print the tree
traverse(binaryTree, false);
return binaryTree;
}
Everything starts from here,
int main(int argc, char** argv)
{
node *binaryTree = createBinaryTreeFromFile(argv[1]);
traverse(binaryTree, true);
return 0;
}
