An STL like Tree Class

	//move from subtree [b] to under [g]
	px1 = x.find(L"Key4");
	px2 = x.find(L"Key16");
	x.MoveSubTree(px2, px1);
 
	x.SetWalkDownRootPivot();
 
	cout << "After moving tree" << endl;
 
	cout << "Data is: " << x.SubTreeGetData().c_str() << endl;
 
	for (int i=1; i<17; i++) {
		x.SubTreeWalkDown();
		cout << "Data is: " << x.SubTreeGetData().c_str() << endl;
 

#ifndef _TREE_H_
#define _TREE_H_
 
/* 
Copyright - All copyright is owned by Mr Jack Hui
Author : Jack, Hui Ho Yin
Email : jackhui@hotmail.com, jackhui@hongkong.com
Update : 27-Aug-2000, 10-Aug-2002
 
*/
 
#pragma warning(disable : 4786) //debug info - name too long

#include <vector>
#include <map>
#include <string>
#include <iostream>
 
using namespace std;
 
namespace Tiffany {
 
//forward declarations
template <class Key, class T> class TreeNode;
template <class Key, class T> class Tree;
template <class Key, class T> class Tree_iterator;
//

 
template <class Key, class T> class TreeNode
{
	friend class Tree<Key, T>;
 
protected:
 
	T						m_data;		//things stored in treenode
	Key						m_key;		//key to locate myself
	int						m_level;	//rootnode is of level 1

	TreeNode<Key,T>*			m_parent;	//points to node of parent
	vector<TreeNode<Key,T> *>	m_children;	//holds pointers for children

	vector<TreeNode<Key,T> *>::iterator	m_current;	//holds iterator to current child processing

	Tree<Key, T>*	m_LinkedTree;	//whom i'm belonging to

public:
 
    TreeNode(Tree<Key,T>* tr) : m_parent(NULL) {
		m_LinkedTree = tr;
	};
	
	TreeNode(Tree<Key,T>* tr, const Key key, const T x)	{
		m_key = key;
		m_data = x;
		m_LinkedTree = tr;
	};
 
	//Delete all the children of this node including all the down levels
    void DeleteAllChildren()	{
 
		vector<TreeNode<Key,T>*>::iterator		pchild;
		map<Key, TreeNode<Key,T>*>::iterator	itrmap;
 
		for(pchild=m_children.begin();pchild != m_children.end();)
		{
			(*pchild)->DeleteAllChildren();
			itrmap = m_LinkedTree->m_nodemap.find((*pchild)->m_key);
 
			m_LinkedTree->m_nodemap.erase(itrmap);
			delete *pchild;				//delete the TreeNode

			m_children.erase(pchild);
			//after removing the node, iterater is advanced
		}
	};
 
	//It erases a child from a Node without delete the node, and without remove
	//linking from the tree, so it can still be accessed from the tree's find().
	void EraseChild(Tree_iterator<Key, T> &itr)
	{
		vector<TreeNode<Key,T>*>::iterator		pchild;
		map<Key, TreeNode<Key,T>*>::iterator	itrmap;
 
		TreeNode<Key,T> *pNode = itr.m_Node->second;
		itrmap = m_LinkedTree->m_nodemap.find(pNode->m_key);
 
		//erase reference from the child vector
		for(pchild=m_children.begin();pchild != m_children.end(); pchild++)
		{
			if( (*pchild)->m_key == pNode->m_key)
			{
				m_children.erase(pchild);
				break;
			}
		}
	}
 
	//Return a reference to parent node in the tree
    TreeNode<Key,T>& GetParent () const {
		return *m_parent;
	};
 
	//returns a reference to vector to the children
    const vector<TreeNode<Key,T>*>& GetChildren () const
	{
		return  m_children;
	};
    
    long ChildCount () const
    {
		return m_children.size();
	};
 
	//add a child node to this node
    void AddChild (TreeNode<Key,T>* child)
	{
		child->m_parent = this;
		child->m_level = this->m_level + 1;
		m_children.push_back(child);
	};
 
	T GetData(void) const { return m_data; }
};
 

//************ End of Tree Node declaration ***************************//
//

 
//************ Start of Tree declaration ***************************//
//

template <class Key, class T>
class Tree {
 
	friend class TreeNode<Key, T>;
 
protected:
 
	//provide a name of the TreeNode to direct access to it
	map<Key, TreeNode<Key,T>*>		m_nodemap;		//a map for fast accessing TreeNode

    TreeNode<Key,T>*				m_pTreeroot;	//a pointer to root node

	TreeNode<Key,T>*				m_WalkPivot;	//Sub-tree root for walking

	TreeNode<Key,T>*				m_WalkCurrent;	//point to current node of walking

	TreeNode<Key,T>*				m_WalkParent;	//point to parent node of current node

public:
 
	typedef Tree_iterator<Key, T> iterator;
 
	typedef const iterator const_iterator;
 
	iterator begin() {
		iterator _tmp;
		_tmp.m_Node = m_nodemap.begin();
 
		return _tmp;
	}
 
	iterator end() {
		iterator _tmp;
		_tmp.m_Node = m_nodemap.end();
 
		return _tmp;
	}
 
	const_iterator begin() const {
		iterator _tmp;
		_tmp.m_Node = m_nodemap.begin();
 
		return _tmp;
	}
 
	const_iterator end() const {
		const_iterator _tmp;
		_tmp.m_Node = m_nodemap.end();
 
		return _tmp;
	}
 
	iterator find(const Key& key) {
		iterator _tmp;
		_tmp.m_Node = m_nodemap.find(key);
 
		return _tmp;
	}
 
	const_iterator find(const Key& key) const {
		const_iterator _tmp;
		_tmp.m_Node = m_nodemap.find(key);
 
		return _tmp;
	}
 
	Tree () : m_pTreeroot(NULL) {
		//instantiate an empty tree
	}
 
	Tree (const Key nm, const T x) {
		//instantiate a tree with the root node

		TreeNode<Key,T>* pNode;
 
		pNode = new TreeNode<Key,T>(this, nm, x);
		m_nodemap.insert(map<Key, TreeNode<Key,T>*>::value_type(nm, pNode));
		m_pTreeroot = pNode;
		pNode->m_level = 1;
	}
 
	~Tree()	{
		if (m_pTreeroot) {
			m_pTreeroot->DeleteAllChildren();
			delete m_pTreeroot;
		}
	}
 
	//returns tree root node, or NULL for empty tree
	TreeNode<Key,T>& GetRoot () const {
		return *m_pTreeroot;
	}
    
	iterator AddChild (iterator& parent, const Key nm, const T x) {
		TreeNode<Key,T>* pNew;
 
		pNew = new TreeNode<Key,T>(this, nm, x);
		parent.m_Node->second->AddChild(pNew);
 
		pair<map<Key, TreeNode<Key,T>*>::iterator, bool> pt = m_nodemap.insert(map<Key, TreeNode<Key,T>*>::value_type(nm, pNew));
 
		iterator _tmp;
		_tmp.m_Node = pt.first;
		return _tmp;
	}
 
    iterator AddChild (const Key nm, const T x) {
		TreeNode<Key,T>* pNew;
 
		pNew = new TreeNode<Key,T>(this, nm, x);
 
		m_pTreeroot->AddChild(pNew);
 
		pair<map<Key, TreeNode<Key,T>*>::iterator, bool> pt = m_nodemap.insert(map<Key, TreeNode<Key,T>*>::value_type(nm, pNew));
 
		iterator _tmp;
		_tmp.m_Node = pt.first;
		return _tmp;
	}
 
	void DeleteAllChildren(iterator & itr) {
		itr.m_Node->second->DeleteAllChildren();
	}
 
	size_t size(void) { return m_nodemap.size(); }
 
	//Set the sub-tree walking root and traverse to the first node
	void SetPostOrderSubTreePivot(iterator& it) {
 
		m_WalkPivot = it.m_Node->second;
		m_WalkCurrent = m_WalkPivot;
		m_WalkCurrent->m_current = m_WalkCurrent->m_children.begin();
 
		while (m_WalkCurrent->m_children.size() != 0) {
			m_WalkCurrent->m_current = m_WalkCurrent->m_children.begin();
			m_WalkCurrent = *(m_WalkCurrent->m_children.begin());
		}
		if (m_WalkCurrent != m_WalkPivot) {
			m_WalkParent = m_WalkCurrent->m_parent;
		}
		else {
			m_WalkParent = m_WalkCurrent;	//for the case no child in pivot
		}
	}
 
	//Set the sub-tree walking root and traverse to the first node
	void SetPostOrderRootPivot() {
 
		m_WalkPivot = m_pTreeroot;
		m_WalkCurrent = m_WalkPivot;
		m_WalkCurrent->m_current = m_WalkCurrent->m_children.begin();
 
		while (m_WalkCurrent->m_children.size() != 0) {
			m_WalkCurrent->m_current = m_WalkCurrent->m_children.begin();
			m_WalkCurrent = *(m_WalkCurrent->m_children.begin());
		}
		if (m_WalkCurrent != m_WalkPivot) {
			m_WalkParent = m_WalkCurrent->m_parent;
		}
		else {
			m_WalkParent = m_WalkCurrent;	//for the case no child in pivot
		}
	}
 
	//It sets root to be the pivot in Walk Down, first node is the first child
	void SetWalkDownSubTreePivot(iterator& itr) {
 
		m_WalkPivot = itr.m_Node->second;
		m_WalkCurrent = m_WalkPivot;
		m_WalkCurrent->m_current = m_WalkCurrent->m_children.begin();
	}
 

	//It sets root to be the pivot in Walk Down, first node is the first child
	void SetWalkDownRootPivot() {
 
		m_WalkPivot = m_pTreeroot;
		m_WalkCurrent = m_WalkPivot;
		m_WalkCurrent->m_current = m_WalkCurrent->m_children.begin();
	}
 
	//it advances m_WalkCurrent in post-order, and returns true if a move is made
	//else it returns false

	bool SubTreePostOrderWalk() {
 
		if (m_WalkCurrent == m_WalkPivot)
			return false;
 
		//if not the parent's last child, advance one node in paraent's child
		//if the advanced child contains sub node, go in depth to the leftmost one
		if (++m_WalkParent->m_current != m_WalkParent->m_children.end()) {
			m_WalkCurrent = *(m_WalkParent->m_current);
			while (m_WalkCurrent->m_children.size() != 0) {
				//go down
				m_WalkCurrent->m_current = m_WalkCurrent->m_children.begin();
				m_WalkParent = m_WalkCurrent;
				m_WalkCurrent = *(m_WalkCurrent->m_current);
			}
		}
		else {
			//if it's the last child of parent, we go up
			m_WalkCurrent = m_WalkParent;
			m_WalkParent = m_WalkCurrent->m_parent;
		}
		m_WalkParent = m_WalkCurrent->m_parent;
 
		return true;
	}
 
	//It advance the tree in top-down style with parent first
	bool SubTreeWalkDown() {
 
		//if it has children, we go down to children
		if (m_WalkCurrent->m_current != m_WalkCurrent->m_children.end()) {
			m_WalkCurrent = *(m_WalkCurrent->m_current);
			m_WalkParent = m_WalkCurrent->m_parent;
			m_WalkParent->m_current++;	//advance to next child for next iteration
			m_WalkCurrent->m_current = m_WalkCurrent->m_children.begin();	//initialize to first child
		}
		else {
			//if it's the last child of parent, we go up to the level
			//which we still need processing by recurively call ourself

			if (m_WalkCurrent == m_WalkPivot)
				return false;		//no more child
			m_WalkCurrent = m_WalkCurrent->m_parent;
			m_WalkParent = m_WalkCurrent->m_parent;
			SubTreeWalkDown();
 
		}
		return true;
	}
 
	void DelSubTree() {
	}
 
	//It moves a tree from source to destination. After moving a tree, tree walking will be invalid.
	//However iterator will still be valid. Users has to Set the new root pivot again.
	void MoveSubTree(iterator& dest_parent, iterator& src)
	{
 
		TreeNode<Key,T>* pSrcNode;
		TreeNode<Key,T>* pDestNode;
		TreeNode<Key,T>* pSrcNodeParent;
 
		pSrcNode = src.m_Node->second;
		pSrcNodeParent = pSrcNode->m_parent;
 
		//remove reference from original parent
		pSrcNodeParent->EraseChild(src);
 
		//add the src sub tree to destination parent node
		pDestNode = dest_parent.m_Node->second;
		pDestNode->AddChild(pSrcNode);
 
		iterator itr;
		itr = find(pSrcNode->m_key);
 
		//setting up correct level
		SetWalkDownSubTreePivot(itr);
		while (SubTreeWalkDown())
		{
			m_WalkCurrent->m_level = m_WalkCurrent->m_parent->m_level + 1;
		}
 
	}
 
	//It gets the current data while the tree is walking
	T SubTreeGetData(void) { return m_WalkCurrent->m_data; }
 
	//It gets the current node level while the tree is walking
	T SubTreeGetLevel(void) { return m_WalkCurrent->m_level; }
 
}; //class Tree

//************ End of Tree declaration ***************************//
//

//Actually, the interator is just a copy of the iterator to a std::map hold in
//the tree to provide simple navigation ability.
template <class Key, class T>
class Tree_iterator
{
	typedef map<Key, TreeNode<Key,T>*>::iterator _map_it;
 
	public:
		_map_it		m_Node;			//a (key, TreeNode *) iterator

		T operator*() const { return (m_Node->second)->GetData(); } 
		
		Tree_iterator& operator++()	{ 
			m_Node++;
			return *this; 
		}
 
		Tree_iterator operator++(int) {
			Tree_iterator __tmp = *this;
			m_Node++;
			return __tmp;
		}
    
		Tree_iterator& operator--() { 
			m_Node--;
			return *this; 
		}
 
		bool operator==(const Tree_iterator& _y) const {
			return m_Node == _y.m_Node;
		}
 
		bool operator!=(const Tree_iterator& _y) const {
			return m_Node != _y.m_Node;
		}
 
};	//class Tree_iterator

}; //namespace Tiffany

#endif //_TREE_H_