数据结构学习----树类(孩子--兄弟表示)

#include "DCirList.h"
#pragma once
#pragma region
//树类
//测试日期 2010-3-11
#ifndef TREENODE_H
#define TREENODE_H
template<class T>
class TreeNode
{ 
public:
	TreeNode<T>* firstchild;                                     //第一个孩子结点指针
	TreeNode<T>* nextsibling;                                    //下一个兄弟结点指针
	T data;                                                      //数据域
 
	TreeNode(){firstchild=nextsibling=NULL;}                     //构造函数
	TreeNode(T item,TreeNode<T>* pf=NULL,TreeNode<T>* pn=NULL)   //重载构造函数
	{data=item;firstchild=pf;nextsibling=pn;}
};
#endif
#pragma endregion


#pragma region
#ifndef TREE_H
#define TREE_H
template<class T>
class Tree
{
private:
	TreeNode<T>* root;                                            //根结点指针
	TreeNode<T>* current;                                         //当前结点指针
	TreeNode<T>* SearchParent(TreeNode<T>* t,TreeNode<T>* s);     //递归查找父结点
	TreeNode<T>* SearchPrevious(TreeNode<T>* t,TreeNode<T>* s);   //递归查找前驱结点
	TreeNode<T>* Copy(TreeNode<T>* t);                            //拷贝函数
public:
	Tree(){root=current=NULL;}                                    //构造函数 
	~Tree(){ClearTree();}                                         //析构函数 
	void ClearTree(){DeleteSubtree(root);}                        //清空树

	//获取结点指针(8个函数)
	TreeNode<T>* GetRoot()
	{return root;}                                  //返回根结点指针
	TreeNode<T>* GetCurrent()
	{return current;}                               //返回当前结点指针
	TreeNode<T>* GetParent();                       //返回当前结点的父结点的指针
	TreeNode<T>* GetPrevious();                     //返回当前结点的前驱结点的指针
	TreeNode<T>* GetFirstChild()                    //返回当前结点的第一个孩子结点的指针
	{return current==NULL?NULL:current->firstchild;}
	TreeNode<T>* GetLastChild();                    //返回当前结点的最后一个孩子结点的指针
	TreeNode<T>* GetNextSibling()                   //返回当前结点的兄弟结点的指针
	{return current==NULL?NULL:current->nextsibling;}
	TreeNode<T>* GetChild(int i);                   //返回当前结点的第i个孩子结点的指针

 

	//三种遍历(3个函数)
	void PreOrder(TreeNode<T> *t,void(*visit)(T x));   //先根遍历以t为根结点的数据域
	void PosOrder(TreeNode<T> *t,void(*visit)(T x));   //后根遍历以t为根结点的数据域
	void LevelOrder(TreeNode<T> *t,void(*visit)(T x)); //层序遍历以t为根结点的数据域
  
	//设置当前结点,并返回当前结点指针(8个函数)
	TreeNode<T>* SetRoot()
	{return current=root;}                     //把根结点设置为当前结点
	TreeNode<T>* SetCurrent(TreeNode<T> *t)
	{return current=t;}                        //把t所指向的结点设置为当前结点
	TreeNode<T>* SetParent()
	{return current=GetParent();}              //把当前结点的父结点设置为当前结点
	TreeNode<T>* SetPrevious() 
	{return current=GetPrevious();}            //把当前结点的前驱结点设置为当前结点
	TreeNode<T>* SetFirstChild()
	{return current=GetFirstChild();}          //把当前结点的第一个孩子结点设置为当前结点
	TreeNode<T>* SetLastChild()
	{return current=GetLastChild();}           //把当前结点的最后一个孩子结点设置为当前结点
	TreeNode<T>* SetNextSibling()
	{return current=GetNextSibling();}         //把当前结点的兄弟结点设置为当前结点
	TreeNode<T>* SetChild(int i)
	{return current=GetChild(i);}              //把当前结点的第i个孩子结点设置为当前结点


	//插入与删除(6个函数)
	void InsertFirstChild(T x);                //把x插入为当前结点的第一个孩子结点
	void InsertLastChild(T x);                 //把x插入为当前结点的最后一个孩子结点
	void InsertChild(int i,T x);               //把x插入为当前结点的第i个孩子结点
    void InsertSibling(T x);                   //把x插入为当前结点的下一个兄弟结点
	void DeleteSubtree(TreeNode<T>* &t);       //删除以t为根结点的子树
	void DeleteChild(int i);                   //删除当前结点的第i个孩子结点

	//其他操作(2个函数)
	bool IsEmpty(){return root==NULL?true:false;}    //判断是否为空树
	Tree<T>& operator=(Tree<T>& tree);               //运算符重载
};
#endif
#pragma endregion


#pragma region
template<class T>
TreeNode<T>* Tree<T>::SearchParent(TreeNode<T> *t, TreeNode<T> *s)
{
	if(t==NULL||s==NULL||s==root) return NULL;
	TreeNode<T>* p=t->firstchild; 
	for(;p!=NULL;p=p->nextsibling)
	{
		if(p==s) return t;
		SearchParent(p,s);  
	} 
	return NULL;
}
template<class T>
TreeNode<T>* Tree<T>::SearchPrevious(TreeNode<T> *t, TreeNode<T> *s)
{
    if(t==NULL||s==NULL||s==root) return NULL;
	if(t->firstchild==s||t->nextsibling==s) return t;
	TreeNode<T> *p=NULL;
	if((p=SearchPrevious(t->firstchild,s))!=NULL) return p;
	if((p=SearchPrevious(t->nextsibling,s))!=NULL) return p;
}
template<class T>
TreeNode<T>* Tree<T>::Copy(TreeNode<T> *t)
{
	if(t==NULL) return NULL;
	TreeNode<T>* p=new TreeNode<T>();
	p->data=t->data;
	p->firstchild=Copy(t->firstchild);
	p->nextsibling=Copy(t->nextsibling);
	return p;
}
template<class T>
TreeNode<T>* Tree<T>::GetParent()
{
    return SearchParent(root,current);
}
template<class T>
TreeNode<T>* Tree<T>::GetPrevious()
{
	return SearchPrevious(root,current);
}
template<class T>
TreeNode<T>* Tree<T>::GetLastChild()
{
	if(current==NULL) return NULL;
	TreeNode<T>* p=current->firstchild;
	for(;p->nextsibling!=NULL;p=p->nextsibling);
	return p;
}
template<class T>
TreeNode<T>* Tree<T>::GetChild(int i)
{
	if(current==NULL||i<0) return NULL;
	TreeNode<T>* p=current->firstchild; 
	for(int k=0;p!=NULL&&k<i;k++) 
		p=p->nextsibling;  
	return p;
}
template<class T>
void Tree<T>::PreOrder(TreeNode<T> *t, void (*visit)(T))
{
	if(t==NULL) return;
	visit(t->data);
	if(t->firstchild!=NULL)  PreOrder(t->firstchild,visit);
	if(t->nextsibling!=NULL) PreOrder(t->nextsibling,visit);
}
template<class T>
void Tree<T>::PosOrder(TreeNode<T> *t, void (*visit)(T))
{
	if(t==NULL) return;
	if(t->firstchild!=NULL)  PosOrder(t->firstchild,visit);
	visit(t->data);
	if(t->nextsibling!=NULL) PosOrder(t->nextsibling,visit);
}
template<class T>
void Tree<T>::LevelOrder(TreeNode<T> *t, void (*visit)(T))
{
    if(t==NULL) return;
    DCirList<TreeNode<T>*> list;
	TreeNode<T>* p1,*p2;
	list.PushBack(t);
	while(!list.IsEmpty())
	{
		p1=list.PopFront();
		visit(p1->data);
		p2=p1->firstchild;
		while(p2!=NULL)
		{
			list.PushBack(p2);
			p2=p2->nextsibling;
		}
	}
}
template<class T>
void Tree<T>::InsertFirstChild(T x)
{
   TreeNode<T>* newnode=new TreeNode<T>(x);
   if(root==NULL){current=root=newnode; return;} 
   if(current==NULL)return;
   if(current->firstchild!=NULL)
   {
	   TreeNode<T>* p=GetFirstChild();
	   current->firstchild=newnode;
	   newnode->nextsibling=p;
   }
   else
	   current->firstchild=newnode;
}
template<class T>
void Tree<T>::InsertLastChild(T x)
{ 
	TreeNode<T>* newnode=new TreeNode<T>(x);
	if(root==NULL){current=root=newnode; return;} 
	if(current==NULL)return;
	if(current->firstchild!=NULL)
	{
		TreeNode<T>* p=GetLastChild();
		p->nextsibling=newnode;
	}
	else
		current->firstchild=newnode;
}
template<class T>
void Tree<T>::InsertChild(int i, T x)
{  
	TreeNode<T>* newnode=new TreeNode<T>(x);
	if(root==NULL){current=root=newnode; return;} 
	if(current==NULL||i<0)return;
	TreeNode<T>* p=current->firstchild;
	if(p!=NULL)
	{ 
	   if(i==0)
	   {
           newnode->nextsibling=p;
		   current->firstchild=newnode; 
	   }
	   else
	   {
		   p=GetChild(i-1);
		   newnode->nextsibling=p->nextsibling;
		   p->nextsibling=newnode;
	   }
	}
	else
		current->firstchild=newnode;
}
template<class T>
void Tree<T>::InsertSibling(T x)
{
    if(current==NULL||current==root)return;
    TreeNode<T>* newnode=new TreeNode<T>(x);
	newnode->nextsibling=current->nextsibling;
	current->nextsibling=newnode;
}
template<class T>
void Tree<T>::DeleteSubtree(TreeNode<T>* &t)
{
	if(t==NULL) return;
	TreeNode<T> *r,*p1,*p2;
	p1=t->firstchild;  
	while(p1!=NULL)
	{
		p2=p1->nextsibling;
		DeleteSubtree(p1);
		p1=p2;
	}
	r=SearchPrevious(root,t);
	if(r!=NULL)
	{
		if(r->firstchild==t)
			r->firstchild=t->nextsibling;
		if(r->nextsibling==t)
			r->nextsibling=t->nextsibling;
	}
	delete t;
	t=NULL;
}
template<class T>
void Tree<T>::DeleteChild(int i)
{
	TreeNode<T>* p=GetChild(i);
	DeleteSubtree(p);
}
 
template<class T>
Tree<T>& Tree<T>::operator =(Tree<T> &tree)
{
	if(tree.root==NULL) return *this;
	current=root=Copy(tree.root);
	return *this;
}
#pragma endregion