technical-recipes.com

Tag: Recursion

  • 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:

    https://www.technical-recipes.com/2012/using-boostpro-to-install-boost-library-packages/
    https://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:

  • A Simple Binary Tree Implementation in C++

    A very basic binary tree implementation in C++ that defines a binary tree node, adds new nodes and prints the tree.

    #include <stdio.h>

class Node
{
public:
	Node( int v )
	{
		data = v;
		left = 0;
		right = 0;
	}

	int data;
	Node* left;
	Node* right;
};

void Add( Node** root, Node* n )
{
	if ( !*root  )
	{
		*root = n;
		return;
	}

	if ( (*root)->data < n->data )
	{
		Add( &(*root)->right, n );
	}
	else
	{
		Add( &(*root)->left, n );
	}
}

void Print( Node* node )
{
	if ( !node )  return;	
	Print( node->left );
	printf( "value = %i\n", node->data );
	Print( node->right );
}

int main()
{
	Node* root = 0;

	Add( &root, new Node( 1 ) );
	Add( &root, new Node( 2 ) );
	Add( &root, new Node( -1 ) );
	Add( &root, new Node( 12 ) );

	Print( root );
	return 0;
}

    Output:

  • A Recursive Algorithm to Find all Paths Between Two Given Nodes in C++ and C#

    Problem Outline

    This I tackled previously when working on the design and implementation of routing optimization algorithms for telecommunications networks. Given that a wide area network with nodes and interconnecting links can be modelled as a graph with vertices and edges, the problem is to find all path combinations (more…)