tree.h

树跟二叉树完整试用版 请选择:(1)建立二叉树:(2)建立二树:(3)帮助:(4)退出:

template<typename T>class Tree;

/*定义树结点类*/
template<typename T>class TreeNode
{
public:

	TreeNode(T value);
    virtual~TreeNode(){};
    T value();
    friend class Tree<T>;

private:

	T m_Value;
    TreeNode<T> * pChild;
    TreeNode<T> *pSibling;

};

template<typename T>TreeNode<T>::TreeNode(T value)
{
	m_Value = value;
    pChild = NULL;
    pSibling = NULL;
}

/*定义树类,用动态左孩子/右孩子表示法来建立树*/
template<typename T>class Tree
{
public:
	
	Tree(){ root=current=NULL; }
	~Tree(){ MakeEmpty(root);}
	int Root();
	int FirstChild();
	int NextSibling();
	void InsertChild(T value);
	void DeleteSubTree(TreeNode<T> *&t);
	void DisplayTree();
	void MakeEmpty(TreeNode<T> *&t);

private:
    
	TreeNode<T> *root, *current;           //定义根结点根当前指针

	TreeNode<T> * GetParent(TreeNode<T> *t,TreeNode<T> *c);
    TreeNode<T> * PrevSibling1(TreeNode<T> *t,TreeNode <T> *current);
	TreeNode<T> * PrevSibling2(TreeNode<T> *t,TreeNode <T> *current);
    int  Current(TreeNode<T> *&t);
	void RootFistTraverse(TreeNode<T> *t);
    void RootLastTraverse(TreeNode<T> *t);
    void WidthTraverse(TreeNode<T> *t);
	void PrintVTree(TreeNode<T> *t);

};

/*清空已t为跟结点的树*/
template<typename T>void Tree<T>::MakeEmpty(TreeNode<T> *&t)
{
	if(t!=NULL)
	{
		MakeEmpty(t->pChild);
		MakeEmpty(t->pSibling);
		delete t;
	}
}

/*确定当前结点*/
template<typename T>int Tree<T>::Current(TreeNode<T> *&t)
{
	if(t == NULL)
	{
		current = NULL;
		return 0;
	}

	else
	{
		current = t;
		return 1;
	}
}

/*定位根结点*/
template<typename T>int Tree<T>::Root()  
{
	if(root == NULL)
	{   
		current = NULL;
		return 0;
	}

	return Current(root);
}

/*查找父母结点*/
template<typename T>TreeNode<T>* Tree<T>::GetParent(TreeNode<T> *t,TreeNode<T> *c) 
{
	if(t == NULL || t->pChild == NULL && t->pSibling == NULL)
		return NULL;

	if(t->pChild == c || t->pSibling == c)
		return root;
    
	TreeNode<T> *p;

	p = GetParent(t->pChild, c);  
	if(p != NULL)
		return p;
	p = GetParent(t->pSibling, c);
	if(p != NULL)
		return p;
}

/*定位于最左孩子*/
template<typename T>int Tree<T>::FirstChild()
{
	if(current == NULL || current->pChild == NULL)
		return 0;
	
	else
	{
		current = current->pChild;
		return Current(current);
	}
}

/*定位于右兄弟*/
template<typename T>int Tree<T>::NextSibling()
{
	if(current == NULL || current->pSibling == NULL)
		return 0;

	else
	{
		current = current->pSibling;
		return Current(current);
	}
}

template<typename T>void Tree<T>::InsertChild(T value)
{
   TreeNode<T> *newNode;

   newNode = new TreeNode<T>(value);
   if(root == NULL)
	   root = current = newNode;
   
   else{
	   if(current->pChild == NULL)
		   current->pChild = newNode;
	   
	   else{
		   TreeNode<T> *p;
		   p = current->pChild;
		   while(p->pSibling != NULL)
			   p = p->pSibling;
		   p->pSibling = newNode;
	   }
   }
   Current(newNode);
}

/*遍历的时候虽然是遍历转换后二叉树，但是结果仍然是树的遍历*/
template<typename T>void Tree<T>::RootFistTraverse(TreeNode<T> *t)
{
	stack<TreeNode<T>*> s;
	TreeNode<T> *p = t;
	s.Push(NULL);
	
	while(p != NULL)
	{
		cout<<p->m_Value<<'\t';
	    
		if(p->pSibling != NULL)
			s.Push(p);
		
		if(p->pChild != NULL)
			p = p->pChild;	
		else
		{	
		 p = s.Pop();
		 if(p != NULL)
		 p = p->pSibling;
		}
	}
}

/*遍历的时候虽然是遍历转换后二叉树，但是结果仍然是树的遍历，
不要看成是二叉树的中序遍历*/
template<typename T>void Tree<T>::RootLastTraverse(TreeNode<T> *t)
{
    stack<TreeNode<T>*> s;
	TreeNode<T> *p = t;
	
	while(p!=NULL || !s.IsEmpty())
	{
		while(p!=NULL)
		{
			s.Push(p);
			p=p->pChild;
		}

		p = s.Pop();
		cout<<p->m_Value<<'\t';
		p = p->pSibling;
	}
}

/*层次遍历树*/
template<typename T>void Tree<T>::WidthTraverse(TreeNode<T> *t)
{
	queue<TreeNode<T> *> Q;
    TreeNode<T> *p = root;
	
	if(p != NULL)
	{
		Q.EnQue(p);
		while(!Q.IsEmpty())	
		{   
			p=Q.DeQue();
			cout<<p->m_Value<<'\t';
			while(p->pSibling != NULL)
			{
				if(p->pChild!=NULL)
					Q.EnQue(p->pChild);
			    p = p->pSibling;
				cout<<p->m_Value<<'\t';
		    }		    
			if(p->pChild != NULL)
				Q.EnQue(p->pChild);
		}
		
	}
}

/*查找当前结点前一个邻居结点的第一种方法*/
template<typename T>TreeNode<T> * Tree<T>::PrevSibling1(TreeNode<T> *t,TreeNode<T> *current)
{
	queue<TreeNode<T> *> Q;
    TreeNode<T> *p = root,*prev = NULL;
	
    if((t == NULL) || (current == p) || (current == NULL)) //当前结点是根结点或者是最左孩子时，没有邻居结点
		return NULL;

	if(p != NULL)
	{
		Q.EnQue(p);
		while(!Q.IsEmpty())	
		{   
            prev=NULL;
			p=Q.DeQue();
			while(p->pSibling != NULL)
			{
				if(p->pChild!=NULL)
					Q.EnQue(p->pChild);
			    prev = p;
				p = p->pSibling;
				if(p == current)
					return prev;
		    }		    
			if(p->pChild != NULL)
				Q.EnQue(p->pChild);
		}	
	}
}

/*查找当前结点前一个邻居结点的第二种方法*/
template<typename T>TreeNode<T>* Tree<T>::PrevSibling2(TreeNode<T> *t,TreeNode <T> *current)
{
	TreeNode<T> *p = root, *Prev = NULL ;
	queue<TreeNode<T> *> Q;

	if((t == NULL) || (current == p) || (current == NULL))
		return NULL;

	while(p != NULL)
	{
		if(p == current)
           return Prev;
		Q.EnQue(p);
		Prev = p;
		p = p->pSibling;
	}

	while(!Q.IsEmpty())
	{
		Prev = NULL;
		p = Q.DeQue();
		p = p->pChild;
		while(p != NULL)
		{
			if(p == current)
				return Prev;
			Q.EnQue(p);
			Prev = p;
			p = p->pSibling;
		}//end while
	}//end while
}

/*删除以current为根结点的子树*/
template<typename T>void Tree<T>::DeleteSubTree(TreeNode<T> *&t)
{
	TreeNode<T> *p = PrevSibling1(root,t);
	
	if(p == NULL)
	{
		p = GetParent(root,t);
			if(p!=NULL)
			{
				p->pChild = t->pSibling;
				t->pSibling = NULL;
			}
			else
			{
				root= t->pChild;
				t->pChild = NULL;
			}
	}
	else{
		p->pSibling = t->pSibling;
		t->pSibling = NULL;
	}
	MakeEmpty(t);
}

/*用图形显示树*/
template<typename T>void Tree<T>::PrintVTree(TreeNode<T> *t){
	
	int screenWidth=64;
	int dataWidth=2;
	
	queue<TreeNode<T> *> Q;
	queue<Level> QI;
	
	TreeNode<T> *p;
	Level s,s1,s2;
	
	double offset,level=-1,i;
	Q.EnQue(t);
	s.xIndent=screenWidth/dataWidth;
	s.yLevel=0;
	QI.EnQue(s);
	
	while(!Q.IsEmpty()&&!QI.IsEmpty())
	{
		s2=s;
		p=Q.DeQue();
		s=QI.DeQue();
		
		if(s.yLevel!=level)
		{
		    cout<<"\n\n第"<<s.yLevel<<"层";
			level=s.yLevel;
			for(i=0;i<s.xIndent-1;i++) cout<<" ";
		}
		else	
			for(i=0;i<s.xIndent-s2.xIndent;i++) cout<<" ";
		       cout<<p->m_Value;
		
		if(p->pChild!=NULL)
		{
			Q.EnQue(p->pChild);
			s1.yLevel=s.yLevel+1;
			offset=screenWidth/pow(dataWidth,s1.yLevel+1);
			s1.xIndent=s.xIndent-offset;
			QI.EnQue(s1);
		}
		
		if(p->pSibling!=NULL)
		 { 
		 
			 Q.EnQue(p->pSibling);
			 s1.yLevel=s.yLevel+1;
			 offset=screenWidth/pow(dataWidth,s1.yLevel+1);
			 s1.xIndent=s.xIndent+offset;
			 QI.EnQue(s1);
		}
	}
}

template<typename T>void Tree<T>::DisplayTree()
{
	cout<<"打印树:"<<endl;
	PrintVTree(root);
	cout<<endl<<endl;
	
	cout<<"按先根遍历树显示的结点次序为:"<<endl<<endl;
	RootFistTraverse(root);
	cout<<endl<<endl;

	cout<<"按后根遍历树显示的结点次序为:"<<endl<<endl;
	RootLastTraverse(root);
	cout<<endl;

    cout<<"按层次遍历树显示的结点次序为:"<<endl<<endl;
	WidthTraverse(root);
	cout<<endl;

	Root();
	FirstChild();
	NextSibling();
    NextSibling();
	cout<<"显示当前结点的前一个邻居结点:"<<endl<<endl;
	cout<<"当前结点是:"<<current->m_Value<<endl<<endl;
	TreeNode<T> *p;
	p = PrevSibling1(root,current);
	cout<<"前一个邻居结点是:"<<endl;
	cout<<p->m_Value<<endl;

	cout<<"删除当前结点为根结点的子树:"<<endl<<endl;
	Root();
	FirstChild();
	NextSibling();
	cout<<"要删除以这个结点为根的子树的结点是:"<<endl;
	cout<<current->m_Value<<endl;
	DeleteSubTree(current);
	PrintVTree(root);
	cout<<endl<<endl;
}