tree_test.cpp

一个包装好的树型模板类,可以实例化树型数据结构.

// Tree_test.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"

#include "Tree.h"





typedef Tree <char> TreeCls;
TreeCls g_tree;


// Reading a DFS encoded tree from a file

// Here is the algorith, ... the file contains the number of children 
// of each node as nodes are encountered in a DFS order
//
// createa new current node, push it on stack, and then
// untill stack (of nodes) is empty
//		Read a number
//		Create that many nodes 
//		add them to parent in order
//		push them on the stack in reverse 
//		set current as their parent
//		push them on stack
//
//////////////////////////////////////////

void read_states_tree()
{
	std::ifstream fp ("dfs_tree.txt");
	if ( ! fp ) {
		std::cout << "file dfs_tree.txt not found\n";
		return; }


	// the stack that will keep track of the DFS ordering while reading from the file
	// (DFS ordering dfetermiens whose parent is who)
	typedef std::stack <TreeCls::Node*> NodesStack;
	NodesStack stack;

	// now create the root node which is always there .. this is also the current node
	char id = 'a';
	TreeCls::Node* root = new TreeCls::Node (id++); 
	stack.push ( root );

	while ( ! stack.empty() ) 
	{
		TreeCls::Node* current = stack.top();
		stack.pop();

		// read the number of children information from file for the current node
		int n = 0;
		fp >> n;
		
		// crete as many new nodes and add them in order to parent 
		for (int i = 0; i<n; i++) {
			TreeCls::Node* node = new TreeCls::Node ( char (id + i) ) ;
			current -> add_child (node); }

		// and now push them in reverse on stack
		for (int i = n - 1; i>= 0; i--) {
			TreeCls::Node* node = current -> child (i); 
			stack.push (node); }
		
		
		id += n;
	}

	std::cout <<"\n\n\n"; 

	// and assign the root node to the tree
	g_tree.set_root (root);
}




int _tmain(int argc, _TCHAR* argv[])
{
	read_states_tree ();

	TreeCls::iterator_dfs it	 = g_tree.begin();
	TreeCls::iterator_dfs it_end = g_tree.end();
	
	while ( it != it_end ) 
	{
		char& c = *it;
		std::cout << c << "\n";
		++it; 
	}


	return 0;
}