GeneralTree to BinaryTree

main.cpp

/*
  Input File Command Manual

  1. insert  
	This Command Call insert Function.
	If  is Root,  will insert to Root Node.

  2. Gen2Bin
	This Command make General Tree Binary Tree.

  3. clearBinary
	This Command Clear data(link data : R_child, L_child) of Binary Tree.
	You Must call This command, When You insert Node after calling Gen2Bin command.

  4. inorder
	This Command is In-order Traversal.

  5. preorder
	This Command is Pre-order Traversal.

  6. postorder
	This Command is Post-order Traversal.

  7. end
	End of input File.

  #- all Commands are case-sensitive  -#
*/


//---------------------------------------------------------------------------

#pragma hdrstop
#include "GeneralTree.h"
#include 
#include 
#include 
//---------------------------------------------------------------------------

using namespace std;
#pragma argsused
int _tmain(int argc, _TCHAR* argv[])
{
	string command;
	cout << "Enter Input File name : ";
	cin >> command;
	fstream i_file(command.c_str(), ios_base::in);
	cout << "Enter Output File name : ";
	cin >> command;
	fstream o_file(command.c_str(), ios_base::out);

	GeneralTree* tree = new GeneralTree(o_file);

	while(!i_file.eof()){
	i_file >> command ;
	if (strcmp(command.c_str(),"insert")==0) {
		string p;
		char a;
		i_file >>p >> a;
		if(strcmp(p.c_str(),"Root")==0)
		{
			tree->Insert(NULL,a);
		} else {
			tree->Insert(p[0],a);
		}
	} else if (strcmp(command.c_str(),"Gen2Bin")==0) {
			tree->General2Binary(tree->getRoot());
		   }
	else if (strcmp(command.c_str(),"clearBinary")==0) {
			tree->ClearBinary(tree->getRoot());
		 }

	 else if (strcmp(command.c_str(),"inorder")==0) {
			 tree->inOrder(tree->getRoot());
			 o_file << "\n";

	 }
	  else if (strcmp(command.c_str(),"preorder")==0) {
			tree->preOrder(tree->getRoot());
			 o_file << "\n";
	 }
	  else if (strcmp(command.c_str(),"postorder")==0) {
			tree->postOrder(tree->getRoot());
			o_file << "\n";
	 }
	 else if (strcmp(command.c_str(),"end")==0) {
				cout <<"[Finished]\n";
				tree->~GeneralTree();
				i_file.close();
				o_file.close();
				return 0;
	 }
	 else {
				cout <<"Unknown Command Error!! : "<< command<<"\n";
				tree->~GeneralTree();
				i_file.close();
				o_file.close();
				return 1;
			}
	}
 }
//---------------------------------------------------------------------------

Node.h

#include 

#ifndef NODE_H
#define NODE_H
template 
class Node
{
public:

	Node(Ty d)
	{
		data=d;
		//children.reserve(10);
	}
	inline void setRight(Node* node){ R_child = node;}
	inline void setLeft(Node* node) { L_child = node;}

	inline Node* getRight(){return R_child;}
	inline Node* getLeft() {return L_child;}

	inline Ty getData()const { return data; }
	std::vector* > children;
private:
	Node *R_child;
	Node *L_child;
	Ty data;
};

#endif

GeneralTree.h

#ifndef GENERALTREE_H
#define GENERALTREE_h
#include 
#include 

#include 

#include "Node.h"
using namespace std;


template 
class GeneralTree
{
public:
	GeneralTree(ostream o_stream)
	{
		root = new Node(NULL);
		NullNode = new Node(NULL);
		os = o_stream;
	}

	~GeneralTree()
	{
		delete root;
		delete NullNode;
	}

	Node* findNode(Node* node,Ty data);
	bool Insert(Ty Dop,Ty data);
	Node* makeNode(Ty data);
	void General2Binary(Node* CurrentNode);
	void inOrder(Node *node);
	void preOrder(Node *node);
	void postOrder(Node *node);
	void showData(Node *node);
	void ClearBinary( Node *node);

	inline Node* getRoot() const {return root; }



private:
	Node* root;
	Node* NullNode;
	ostream os;

};

template 
void GeneralTree::General2Binary(Node* CurrentNode)
{
	typedef vector< Node* >::iterator Child_t;
	if(!(CurrentNode->children.empty()))
	{
		for(Child_t it= CurrentNode->children.begin();it != CurrentNode->children.end()-1 ; it++)
		{
			if(it == CurrentNode->children.begin())
			{
				CurrentNode->setLeft(*it);
				(*it)->setRight(*(it+1));
				General2Binary(*it);
			} else {
				(*it)->setRight(*(it+1));
				General2Binary(*it);
			}
		}
	}
}

/*
 * Dop : Data of Parent
 *       if Dop is NULL , data Will be Inserted to Root.
 *       if Dop could not find, data Will Not be inserted.
 *       if Dop was Found , data will be Inserted to Child of Dop.
 * data : A data to insert
 */
template 
bool GeneralTree::Insert(Ty Dop, Ty data)
{
	if(root->getData() == NULL)
	{
		root = makeNode(data);
		return true;
	} else {
		Node* parent;
		parent = findNode(root,Dop);
		if(parent == NullNode)
		{
			std::cerr << " 원하는 부모의 값이 없습니다. \n";
			return false;
		} else {
			parent->children.push_back(makeNode(data));
			return true;
		}
	}

}

template 
Node* GeneralTree::findNode(Node* node,Ty data)
{
	typedef vector< Node* >::iterator Child_t;
	Node* temp;
	if(node->getData() == data)
		return node;
	else {
		Node* Parent=node;
		Child_t begin = Parent->children.begin();
		for(Child_t it = begin; it != Parent->children.end(); it++)
		{
			temp = findNode((*it),data);
			if(temp != NullNode )
				return temp;
		}
		return NullNode;
	}

}
template 
Node* GeneralTree::makeNode(Ty data)
{
	Node* new_node = new Node(data);
	new_node->setLeft(NullNode);
	new_node->setRight(NullNode);
	return new_node;
}

template 
void GeneralTree::showData(Node *node)
{
	os << node->getData() <<" ";
}


template 
void GeneralTree::preOrder(Node * node)
{
	if(node == NullNode ) return ;
	if(node == root) os << "PreOrder : ";

	showData(node);
	preOrder(node->getLeft());
	preOrder(node->getRight());
}

template 
void GeneralTree::inOrder(Node * node)
{
	if(node == NullNode ) return ;
	if(node == root) os << "InOrder : ";

	inOrder(node->getLeft());
	showData(node);
	inOrder(node->getRight());
}

template 
void GeneralTree::postOrder(Node * node)
{
	if(node == NullNode ) return ;
	if(node == root) os << "PostOrder : ";

	postOrder(node->getLeft());
	postOrder(node->getRight());
	showData(node);
}

template 
void GeneralTree::ClearBinary(Node *node)
{
	if(node == NullNode ) return ;
	ClearBinary(node->getLeft());
	ClearBinary(node->getRight());
	node->setLeft(NullNode);
	node->setRight(NullNode);
}

#endif