forest.h

将森林转化为相应二叉树的算法

#include<queue>
template<class T>class Tree;
template<class T>
class TreeNode
{
friend class Tree<T>;
private:
	T m_value;
	TreeNode<T> *pChild;
	TreeNode<T> *pSibling;

public:
	TreeNode(const T&);
	~TreeNode(){};
	bool isLeaf();
	T Value(){return m_value;};
	TreeNode<T>* LeftMostChild();
	TreeNode<T>* RightSibling();
	void setValue(T&);
	void setChild(TreeNode<T>* pointer);
	void setSibling(TreeNode<T>* pointer);
	void InsertFirst(TreeNode<T>* node);
	void InsertNext(TreeNode<T>* node);
};
template<class T>
TreeNode<T>::TreeNode(const T& value)
{
m_value=value;
pChild=pSibling=NULL;
}
template<class T>
bool TreeNode<T>::isLeaf()
{
if(NULL==pChild)return true;
else return false;
}
template<class T>
TreeNode<T>* TreeNode<T>::LeftMostChild()
{
return pChild;
}
template<class T>
TreeNode<T>* TreeNode<T>::RightSibling()
{
return pSibling;
}
template<class T>
void TreeNode<T>::setChild(TreeNode<T>* pointer)
{
pChild=pointer;
}
template<class T>
void TreeNode<T>::setSibling(TreeNode<T>* pointer)
{
pSibling=pointer;
}

//tree
template<class T>
class Tree
{
private:
	TreeNode<T>* root;
	TreeNode<T>* getParent(TreeNode<T>* root,TreeNode<T>* current);
	void DestroyNodes(TreeNode<T>* root);
public:
	Tree(TreeNode<T>* rt);
	~Tree(){};
	TreeNode<T>* getRoot();
	void CreateRoot(const T& rootValue);
	bool isEmpty();
	TreeNode<T>* Parent(TreeNode<T>* current);
	TreeNode<T>* PrevSibling(TreeNode<T>* current);
	void DeleteSubTree(TreeNode<T>* subroot);
};
template<class T>
Tree<T>::Tree(TreeNode<T>* rt)
{
	root=rt;
}
/*template<class T>
Tree<T>::~Tree()
{
	while(root)
		DeleteSubTree(root);
}*/
template<class T>
TreeNode<T>* Tree<T>::getRoot()
{
return root;
}
template<class T>
void Tree<T>::CreateRoot(const T& rootValue)
{
	if(!root)
		root=new TreeNode<T>(rootValue);
}
template<class T>
bool Tree<T>::isEmpty()
{
	if(root)
		return false;
	return true;
}
template <class T>
TreeNode<T>* Tree<T>::PrevSibling(TreeNode<T>* current)
{
	using std::queue;
	queue<TreeNode<T>*> aQueue;
	TreeNode<T>* pointer=root;
	TreeNode<T>* prev=NULL;
	if(current==NULL||pointer==NULL||current==pointer)
		return NULL;
	while(pointer)
	{
		if(pointer==current)
			return prev;
		aQueue.push(pointer);
		prev=pointer;
		pointer=pointer->pSibling;
	}
	while(!aQueue.empty())
	{
		prev=NULL;
		pointer=aQueue.front();
		aQueue.pop();
		pointer=pointer->LeftMostChild();
		while(pointer)
		{
			if (pointer==current)
				return prev;
			aQueue.push(pointer);
			prev=pointer;
			pointer=pointer->pSibling;
		}
	}
	return NULL;
}
template<class T>
TreeNode<T>* Tree<T>::getParent(TreeNode<T>* root,TreeNode<T>* current)
{
	if (root==current)return NULL;
	TreeNode<T>* temp;
	if(root==NULL)
		return NULL;
	if (root->LeftMostChild()==current)
		return root;
	if ((temp=getParent(root->LeftMostChild(),current))!=NULL)
		return temp;
	else return getParent(root->RightSibling(),current);
}
template<class T>
TreeNode<T>* Tree<T>::Parent(TreeNode<T>* current)
{
	TreeNode<T>* pointer=current;
	if(NULL!=pointer)
	{
		TreeNode<T>* leftmostChild=NULL;
		while((leftmostChild=PrevSibling(pointer))!=NULL)
			pointer=leftmostChild;
		leftmostChild=pointer;
		pointer=root;
		if(leftmostChild==root)
			return NULL;
		else return getParent(pointer,leftmostChild);
	}

}
template<class T>
void Tree<T>::DestroyNodes(TreeNode<T>* root)
{
	if(root)
	{
	DestroyNodes(root->LeftMostChild());
	DestroyNodes(root->RightSibling());
	delete root;
	}
}
template<class T>
void Tree<T>::DeleteSubTree(TreeNode<T>* subroot)
{
	TreeNode<T>* pointer=PrevSibling(subroot);
	if(NULL==pointer)
	{
		pointer=Parent(subroot);
		if(pointer)
		{
			pointer->pChild=subroot->RightSibling();
			subroot->pSibling=NULL;
		}
		else
		{
			root=subroot->RightSibling();
			subroot->pSibling=NULL;
		}
	}
	else
	{
		pointer->pSibling=subroot->RightSibling();
		subroot->pSibling=NULL;
	}
	DestroyNodes(subroot);
}