expressionbinarytree.cpp

表达式二叉树的实现。输入任意一个前序中序或后序表达式

     
#include<conio.h>
#include<stdlib.h>
#include<stdio.h>
#include<string.h>
#include <stack>
#include <queue>
#include <iostream>
using namespace std;

class BinaryTree;

class BinaryTreeNode  
{
friend class BinaryTree;
private:
	char  element;					               			
public:
	BinaryTreeNode*  left; 						
	BinaryTreeNode*  right; 				

public:
	BinaryTreeNode();
	BinaryTreeNode(const char& ele);				
	BinaryTreeNode(const char& ele,BinaryTreeNode* l, BinaryTreeNode* r);
	char  value() const;														
};

BinaryTreeNode::BinaryTreeNode()
{
	left=right=NULL;
}


BinaryTreeNode::BinaryTreeNode(const char& ele)	
{
	element=ele;
	left=right=NULL;
}


BinaryTreeNode::BinaryTreeNode(const char& ele,BinaryTreeNode* l, BinaryTreeNode* r)
{
	element=ele;
	left=l;
	right=r;
}


char BinaryTreeNode::value() const
{
	return element; 
}	

enum Tags{Left,Right};

class StackElement
{
public:
	BinaryTreeNode* pointer;
	Tags tag;
};	

class BinaryTree  
{

public:
	BinaryTreeNode*  root;      						
public:
	BinaryTree(){root=NULL;};							
	virtual ~BinaryTree(){};											
	void PreOrder(BinaryTreeNode* root);
	void InOrder(BinaryTreeNode* root);
	void PostOrder(BinaryTreeNode*root);
	bool buildfromprefix (BinaryTreeNode*&p, char str[]);
	bool buildfrominfix  (BinaryTreeNode*&p, char str[]);
	bool buildfrompostfix(BinaryTreeNode*&p, char str[]);
	void print(BinaryTreeNode*p,int i);
	int height(BinaryTreeNode*p)
	{
		if(!p) return 0;
		int h1=height(p->left);
		int h2=height(p->right);
		if(h1>h2) return h1;
		else return h2;
	}

};

void BinaryTree::PreOrder(BinaryTreeNode* root)				
{
	if(root!=NULL)
	{
		cout<<root->value();			
		PreOrder(root->left);		
		PreOrder(root->right);		
	}
};


void BinaryTree::PostOrder(BinaryTreeNode* root)				
{
	if(root!=NULL)
	{
		PostOrder(root->left);		
		PostOrder (root->right);		
		cout<<root->value();		
	}
}

int precede(char c,char ch)
{
  	switch (c)
	{
	case '#':
	case '(':	return 0;
	case '*':
	case '/':					
	case '+':
	case '-':	if (!(ch!='*' && ch!='/')) return 0;
				return 1;
	default :	return 1;
	}
}

bool isoperator(char a)
{

	if(a=='+')
		return 1;
	else if(a=='-')
		return 1;
	else if(a=='*')
		return 1;
	else if(a=='/')
		return 1;
	else if(a=='(')
		return 1;
	else if(a==')')
		return 1;
	else if(a=='#')
		return 1;
	else
		return 0;
}

bool BinaryTree::buildfromprefix(BinaryTreeNode*&p, char str[])
{
	char nextelem;
	static int time=0;
	p=new BinaryTreeNode;
	if(!p) return false;
	nextelem=str[time];
	time++;
	if(isoperator(nextelem))
	{
		p->element=nextelem;
		return buildfromprefix(p->left,str)&&buildfromprefix(p->right,str);
	}
	else
	{
		p->element=nextelem;
		p->left=NULL;
		p->right=NULL;
	}
}


bool BinaryTree::buildfrominfix(BinaryTreeNode*&p, char str[])
{
	stack<BinaryTreeNode*> CH;
	stack<char> OP;
	OP.push('#');
	char * data=str;
	char ch=*data;
	while(ch != '\0')
	{
		if(!isoperator(ch))
		{
			p=new BinaryTreeNode(ch);
			CH.push(p); 
		}
		else
		{
			switch(ch)
			{
			case '(':
				OP.push(ch);
				break;
			case ')':
				{
					char c=OP.top();OP.pop();
					while(c!='(')
					{
						p=new BinaryTreeNode(c);
						if(!CH.empty())
						{
							p->right=CH.top();
							CH.pop();
						}
						else
							p->right=NULL;
						if(!CH.empty())
						{
							p->left=CH.top();
							CH.pop();
						}
						else
							p->left=NULL;
						CH.push(p);
						c=OP.top();
						OP.pop();
					}
					break;
				}
			default:
				{
					char c;
					c=OP.top();
					if( precede( c, ch))
					{
						p=new BinaryTreeNode(c);
						if(!CH.empty())
						{
							p->right=CH.top();
							CH.pop();
						}
						else
							p->right=NULL;
						if(!CH.empty())
						{
							p->left=CH.top();
							CH.pop();
						}
						else
							p->left=NULL;
						CH.push(p);
						OP.pop();
						OP.push( ch);
					}

					else{
						OP.push( ch);
					}
				}
			}
		}
		if(ch!='\0')
		{
			data++;
			ch=* data;
		}
	}

	
	char c;
	while( ( c=OP.top()) != '#')
	{
		p=new BinaryTreeNode(c);
		if(!CH.empty())
		{
			p->right=CH.top();
			CH.pop();
		}
		else
			p->right=NULL;
		if(!CH.empty())
		{
			p->left=CH.top();
			CH.pop();
		}
		else
			p->left=NULL;
		CH.push(p);
		OP.pop();

	}
	root = CH.top();
	return true;
}

bool BinaryTree::buildfrompostfix(BinaryTreeNode*&p, char str[])
{
	char nextelem;   
	static int time=0;  
	p=new BinaryTreeNode;
	if(!p) return false;
	nextelem=str[time];
	time++;
	if(isoperator(nextelem))
	{
		p->element=nextelem;
		return buildfrompostfix(p->right,str)&&buildfrompostfix(p->left,str);
	}
	else
	{
		p->element=nextelem;
		p->right=NULL;
		p->left=NULL;
	}
}

void BinaryTree::print(BinaryTreeNode *p,int i)
{
	if(p->left) print(p->left,i+1);
	for(int j=0;j<i;j++)
		cout<<"   ";
	cout<<p->element<<endl;
	if(p->right) print(p->right,i+1);

}

void BinaryTree::InOrder(BinaryTreeNode* p)
{
	if(p)
	{
		if(!isoperator(p->element))
			cout<<p->element;
		else
		{
			if(isoperator(p->left->element)&&!precede(p->left->element,p->element) )
			{
				cout<<'(';
				InOrder(p->left);
				cout<<')';
			}
			else
				InOrder(p->left);
			cout<<p->element;
			if(isoperator(p->right->element)&& !precede(p->right->element,p->element) )
			{
				cout<<'(';
				InOrder(p->right);
				cout<<')';
			}
			else 
				InOrder(p->right);
		}
	}
}


void main()
{
	char ch;
	char str[256];
	BinaryTree Mytree;
	system("cls");
	cout<<"Input expression is:"<<endl
		<<"1)Prefix"<<endl
		<<"2)Infix"<<endl
		<<"3)Postfix"<<endl;
	ch=getch();
	if(ch=='1')
	{
		cout<<"Enter Prefix Expression:"<<endl;
		gets(str);
		Mytree.buildfromprefix(Mytree.root,str);
	}
	if(ch=='2')
	{
		cout<<"Enter Infix Expression:"<<endl;
		cin.getline(str,50);
		Mytree.buildfrominfix(Mytree.root,str);
	}
	if(ch=='3')
	{
		cout<<"Enter Postfix Expression:"<<endl;
		gets(str);
		strrev(str);
		Mytree.buildfrompostfix(Mytree.root,str);
	}
	cout<<endl;
	Mytree.print(Mytree.root,0);
	cout<<"最左边为根结点"<<endl;
	cout<<endl;
	cout<<"which expression to print:"<<endl
		<<"1)Prefix"<<endl
		<<"2)Infix"<<endl
		<<"3)Postfix"<<endl;
	ch=getch();
	switch(ch)
	{
	case '1':
		Mytree.PreOrder(Mytree.root);
		cout<<endl;
		break;
	case '2':
		Mytree.InOrder(Mytree.root);
		cout<<endl;
		break;
	case '3':
		Mytree.PostOrder(Mytree.root);
		cout<<endl;
		break;
	}
}