tree.h

包括树的构造

#include <iostream>
#include <vector>
#include <string>
#include "stack.h"
#include "LinkedQueue.h"
#include "BinaryTreeNode.h"
using namespace std;
int PRI(char sign)//优先级的计算
{
	if (sign=='*'||sign=='/'||sign=='%')return 2;
	if(sign=='+'||sign=='-')return 1;
	return 0;
}
template<class T>
class BinaryTree
{
public:
	BinaryTree(){root=0;}
	void InputBinaryTree();
	void Show_BinaryTree();
	void MakeTree(BinaryTreeNode<T>*left,BinaryTreeNode<T>*mid,BinaryTreeNode<T>*right);
	void TreeCount();
	void ShowFloor();
	void DeleteTree();
protected:
private:
	void DeleteNode(BinaryTreeNode<T>*p);
	void ShowNode(BinaryTreeNode<T>*p,LinkedQueue<BinaryTreeNode<T>*>&myqueue);
	T Count(BinaryTreeNode<T>*p);
	void Print_BNode(BinaryTreeNode<T> *p, int c, vector<bool>& isend,bool RorL);
	BinaryTreeNode<T> *root;
};
template<class T>
void BinaryTree<T>::DeleteTree()
{
	cout<<"销毁所建的树:"<<endl<<endl;
	Stack<BinaryTreeNode<T>*> node_stack;
	DeleteNode(root);
}
template<class T>
void BinaryTree<T>::DeleteNode(BinaryTreeNode<T>*p)
{
	if (!p)
	{
		return;
	}
	if (!p->LeftChild&&!p->RightChild)
	{
		cout<<"删除节点";
		if (p->sign>=37&&p->sign<=47)
		{
			cout<<p->sign;
		}
		else cout<<p->data;
		cout<<"!"<<endl;
		delete p;
		return;
	}
	DeleteNode(p->LeftChild);
	p->LeftChild=0;
	DeleteNode(p->RightChild);
	p->RightChild=0;
	DeleteNode(p);
	p=0;
}
//***********************************
template<class T>
void BinaryTree<T>::MakeTree(BinaryTreeNode<T>*left,BinaryTreeNode<T>*mid,BinaryTreeNode<T>*right)
{
	mid->LeftChild=left;
	mid->RightChild=right;
	left=right=0;
}
template<class T>
void BinaryTree<T>::InputBinaryTree()
{
	cout<<"请输入您要计算的表达式:"<<endl;
	string str;
	cin>>str;
	Stack<BinaryTreeNode<T>*>num_stack;
	Stack<BinaryTreeNode<T>*>sign_stack;
	int len=str.length();
	for (int i=0;i<len;)
	{
		if (str[i]=='+'&&(i==0||str[i-1]=='('))
		{
			i++;
		}
		else if (str[i]>47&&str[i]<58||str[i]=='-'&&(i==0||str[i-1]=='('))
		{
			T num;
			string one_num;
			while (str[i]>47&&str[i]<58||str[i]=='-'&&(i==0||str[i-1]=='(')||str[i]=='.')
			{
				one_num.append(&str[i],1);
				i++;
			}
			if(one_num=="-")
			{
				str.insert(i-1,"0",1);
				i--;
				len=str.length();
				continue;
			}
			num=atof(&one_num[0]);
			BinaryTreeNode<T>*r=new BinaryTreeNode<T>(num);
			num_stack.Add(r);
		}
		else if (sign_stack.IsEmpty()||str[i]=='(')
		{
			BinaryTreeNode<T>*r=new BinaryTreeNode<T>(str[i],true);
			sign_stack.Add(r);
			i++;
		}
		else
		{
			if (str[i]==')')
			{
				BinaryTreeNode<T>* l,*r,*m,*mid;
				while (sign_stack.Top()->sign!='(')
				{
					num_stack.Delete(r);
					num_stack.Delete(l);
					sign_stack.Delete(m);
					MakeTree(l,m,r);
					num_stack.Add(m);
				}
				sign_stack.Delete(mid);
				i++;
			}
			else
			{
				int now=PRI(str[i]),s_top=PRI(sign_stack.Top()->sign);
				if (now==s_top||now<s_top)
				{
					BinaryTreeNode<T>* l,*r,*m,*mid;
					while((now==s_top||now<s_top))
					{
						
						num_stack.Delete(r);
						num_stack.Delete(l);
						sign_stack.Delete(m);
						MakeTree(l,m,r);
						num_stack.Add(m);
						if(sign_stack.IsEmpty())break;
						now=PRI(str[i]),s_top=PRI(sign_stack.Top()->sign);
					}
					mid=new BinaryTreeNode<T>(str[i],true);
					sign_stack.Add(mid);
					i++;
				}
				else if (now>s_top)
				{
					BinaryTreeNode<T>*r=new BinaryTreeNode<T>(str[i],true);
					sign_stack.Add(r);
					i++;
				}
			}	
		}
	}
	while (!sign_stack.IsEmpty())
	{
		BinaryTreeNode<T>* l,*r,*m,*mid;
		num_stack.Delete(r);
		num_stack.Delete(l);
		sign_stack.Delete(m);
		MakeTree(l,m,r);
		num_stack.Add(m);
	}
	if (!num_stack.IsEmpty())
	{
		num_stack.Delete(root);
	}
}
//**************************************
template<class T>
void BinaryTree<T>::Show_BinaryTree()

{
       vector<bool> bIsEnd;
       bIsEnd.push_back(0);
	   cout<<"您所输入的树是：\n";
       cout<<"Root:";
	   if (!root->LeftChild&&!root->RightChild)
	   {
		   cout<<root->data<<endl;
	   }
	   else 
	   {
		   cout<<root->sign<<endl;
		   
		   Print_BNode(root->LeftChild,1,bIsEnd,false);
		   bIsEnd[0]=1;
		   Print_BNode(root->RightChild,1,bIsEnd,true);
		   cout<<endl;
	   }
}
template<class T>
void BinaryTree<T>::Print_BNode(BinaryTreeNode<T> *p, int c, vector<bool>& isend,bool RorL)

{
	if (!p)
	{
		return;
	}
       for(int j=0;j<c;j++)
       {//─└├│
		   if(isend[j]==0)
			   if(j!=c-1)cout<<"│";
			   else cout<<"├";
			   else if(j!=c-1)cout<<"  ";	   
			   else cout<<"└";
			   if(j!=c-1)cout<<"  ";				   
			   else cout<<"─";
       }
       if (!p->LeftChild&&!p->RightChild)
       {
		   cout<<" "<<p->data;
       }
       else
		   cout<<" "<<p->sign;
	   if (RorL)
	   {
		   cout<<"R";
	   }
	   else cout<<"L";
       cout<<endl;   
       for(int i=0;i<2;i++)
       {
		   if(isend.size()==c)isend.push_back(0);		   
		   else isend[c]=0;		   
		   if(i==1)			   
		   {			  
			   if(isend.size()==c)isend.push_back(1);			   
			   else isend[c]=1;
		   }	   
		   if (i==0)
		   {
			   Print_BNode(p->LeftChild,c+1,isend,false);
		   }
		   else Print_BNode(p->RightChild,c+1,isend,true);
       }
}
template<class T>
void BinaryTree<T>::TreeCount()
{
	T result=Count(root);
	cout<<"运算结果为：\n"<<result<<endl;
}
template<class T>
T BinaryTree<T>::Count(BinaryTreeNode<T>*p)
{
	if (!p->LeftChild&&!p->RightChild)
	{
		return p->data;
	}
	T result,l=Count(p->LeftChild),r=Count(p->RightChild);
	if (p->sign=='+')
	{
		return l+r;
	}
	else if (p->sign=='-')
	{
		return l-r;
	}
	else if (p->sign=='*')
	{
		return l*r;
	}
	else if (p->sign=='/')
	{
		if(r==0) throw BadInput();
		return l/r;
	}
	else if (p->sign=='%')
	{
		return l%r;
	}
	else 
	{
		cout<<"不支持"<<p->sign<<"运算"<<endl;
		exit(1);
	}
}
template<class T>
void BinaryTree<T>::ShowFloor()
{
	LinkedQueue<BinaryTreeNode<T>*>myqueue;
	int floor=1;
	cout<<"遍历这棵二叉树：\n";
	ShowNode(root,myqueue);
	cout<<endl;
}
template <class T>
void BinaryTree<T>::ShowNode(BinaryTreeNode<T>*p,LinkedQueue<BinaryTreeNode<T>*>&myqueue)
{
	if(p)
	{
		if (!p->LeftChild&&!p->RightChild)
		{
			cout<<" "<<p->data;
		}
		else
			cout<<" "<<p->sign;
		myqueue.Add(p->LeftChild).Add(p->RightChild);
	}
	if (myqueue.IsEmpty())
	{
		return;
	}
	BinaryTreeNode<T>*mid;
	myqueue.Delete(mid);
	ShowNode(mid,myqueue);
}