How to recursively print STL-based trees

There are plenty of resources on how we may recursively search and print the contents of binary trees. This example shows how to (recursively) make use of the Boost serialization libraries and streams in order to print the contents of a tree-like data structure.

For more help on getting set up with the Boost libraries in Visual Studio environments, see these following links:

http://www.technical-recipes.com/2012/using-boostpro-to-install-boost-library-packages/
http://www.technical-recipes.com/2011/how-to-install-the-boost-libraries-in-visual-studio/

This following ‘Node’ class stores a std::string text value. In place of things like linked lists or binary trees, the Node class uses a std::vector of Node objects:

#include <boost/archive/text_oarchive.hpp>
#include <boost/archive/text_iarchive.hpp>
#include <boost/serialization/vector.hpp>
#include <fstream>
#include <vector>
#include <iomanip>
#include <iostream>

class Node
{
private:    
    friend std::ostream& operator<<(std::ostream &os, const Node &n);       
	std::string txt;	
	std::vector<Node> v;

public:
    Node(){};
    Node(std::string txt) : txt(txt) {}  
	void Print( std::ostream & os, const Node &tk, int level ) const;
	void Add( Node tk )
	{ v.push_back( tk ); }
};

typedef std::vector<Node>::const_iterator tk_cit;

void Node::Print(std::ostream& os, 
	             const Node &tk,
				 int level ) const
{
	if (level == 1)
	{
		os << tk.txt << '\n';
	}

	for ( tk_cit it = tk.v.begin();
		  it != tk.v.end();
		  it++ )
	{
		Node t = *it;
		os << std::setw(level*4) << t.txt << std::endl;
		Print( os, t, level + 1 );
	}
}

std::ostream & operator<<(std::ostream &os, const Node &tk)
{
  tk.Print( os, tk, 1 );
  return os;
}

To use the class, simply create Node instances, initialising their text values in the constructor, use the ‘Add‘ function to add child nodes. Output the entire tree details to a stream. Example usage shown here, whereby:

node “A” has child nodes “B”, “C”, “D” and “E”;
node “C” has child nodes “A”, “B” and “F”;
node “G” has child nodes “A” and “C”:

#include "Node.h"

int main()
{
 	Node n1( "A" );
	Node n2( "B" );
	Node n3( "C" );
	Node n4( "D" );
	Node n5( "E" );
	Node n6( "F" );
	Node n7( "G" );

	n1.Add( n2 );
	n1.Add( n3 );
	n1.Add( n4 );
	n1.Add( n5 );

	n3.Add( n1 );
	n3.Add( n2 );
	n3.Add( n6 );

	n7.Add( n1 );
	n7.Add( n3 );

	std::cout << n7 << std::endl;

	return 0;
}

Giving the following console output when we output the parent node “G” and its child nodes, and further sub-child nodes as necessary:

Leave a Reply