1 算数表达式求值

三种遍历方式

①先序遍历次序（前缀式）：+ * 3 - 6 2 / 8 2

②中序遍历方式（中缀式）：3 * 6 - 2 + 8 / 2

③后序遍历方式（后缀式）：3 6 2 - * 8 2 / +

由表达式的三种标识方法，可得到如下结论：

①操作数之间的相对次序不变

②运算符的相对次序不同

③中缀式丢失了括号信息，致使运算的次序不确定

④前缀式的运算规则是：连续出现的两个操作数和在它们之前且紧靠它们的运算符构成一个最小表达式。

⑤后缀式的运算规则是：运算符在式中出现的顺序恰为表达式的运算顺序；每个运算符和在它之前出现且紧靠它的两个操作数构成一个最小表达式。

实现代码：

//BinaryExpTree.h
#pragma once
#include "BTnode.h"
#include <windows.h>
class BinaryExpTree
{
public:
	BinaryExpTree():m_root(NULL){}
	~BinaryExpTree();
	void Create(char ch1[],char ch2[],int);
	int Evaluate();
private:
	BTnode<char>* m_root;
	void _DestroyBT(BTnode<char>* &);
	int _Evaluate(BTnode<char>* &);
	int _Operate(const int&, const char&, const int&);
	void _Create(BTnode<char>* &,char ch1[],char ch2[],int,int,int&);
};

//BinaryExpTree.cpp
#include "BinaryExpTree.h"

BinaryExpTree::~BinaryExpTree()
{
	_DestroyBT(m_root);
}

void BinaryExpTree::Create(char ch1[],char ch2[],int n)
{
	int i = 0;
	_Create(m_root,ch1,ch2,0,n-1,i);
}

void BinaryExpTree::_DestroyBT(BTnode<char>* &p)
{
	if (p)
	{
		_DestroyBT(p->Lchild);
		_DestroyBT(p->Rchild);
		delete p;
	}
}

int BinaryExpTree::Evaluate()
{
	return _Evaluate(m_root);
}

int BinaryExpTree::_Evaluate(BTnode<char>* &T)
{
	if (T)
	{
		if (!T->Lchild && !T->Rchild)
		{
			return T->data - '0';
		}
		return _Operate(_Evaluate(T->Lchild),T->data,_Evaluate(T->Rchild));
	}
}

int BinaryExpTree::_Operate(const int&a, const char& theta, const int&b)
{
	int c;
	switch(theta)
	{
	case '+' : c = a + b; break;
	case '-' : c = a - b; break;
	case '*' : c = a * b; break;
	case '/' : c = a / b; break;
	}
	return c;
}

void BinaryExpTree::_Create(BTnode<char>* &T,char ch1[],char ch2[],int low,int high,int& k)
{
	int i;
	if (low > high)
	{
		T = NULL;
	}
	else
	{
		T = new BTnode<char>;
		T->data = ch1[k];
		for (i = low; i <= high && ch2[i]!= ch1[k]; i++);
		k++;
		_Create(T->Lchild,ch1,ch2,low,i-1,k);
		_Create(T->Rchild,ch1,ch2,i+1,high,k);
	}
}

//main.cpp
#include <iostream>
#include <fstream>
#include "BinaryExpTree.h"
using namespace std;

void main(int argc, char* argv[])
{
	BinaryExpTree bt;
	char pch[256],ich[256];
	cout<<"请按二叉表达式树的前缀表示输入字符串："<<endl;
	cin>>pch;
	cout<<"请按二叉表达式树的中缀表示输入字符串："<<endl;
	cin>>ich;
	int i = 0;
	while (pch[i])
	{
		i++;
	}
	bt.Create(pch,ich,i);
	cout<<"表达式按后缀求值的结果为："<<bt.Evaluate()<<endl;
	system("pause");
}

2 等价问题

静态树表节点的双亲表示法如下：

struct PTnode
{
	char data;
	int parent;
};

//MEset.h
#pragma once
#include "PTnode.h"
class MEset
{
public:
	MEset(int n):m_len(0),m_size(n){m_nodes = new PTnode[n];}
	~MEset(){delete [] m_nodes;}
	bool Create(char[],const int&);
	void Display();
	int LocateElem(const char&);
	int FindRoot(const int&);
	void Merge(const int&, const int&);
	void EffMerge(const int&, const int&);
private:
	int m_len;
	int m_size;
	PTnode* m_nodes;
};

//MEset.cpp
#include "MEset.h"
#include "iostream"
bool MEset::Create(char ch[],const int& n)
{
	if (n > m_size)
	{
		return false;
	}
	int i = 0;
	while (i < n)
	{
		m_nodes[i].data = ch[i];
		m_nodes[i].parent = -1;
		i++;
	}
	m_len = n;
	return true;
}

int MEset::LocateElem(const char& e)
{
	for (int i = 0; i < m_len; i++)
	{
		if (m_nodes[i].data == e)
		{
			return i;
		}
	}
	return -1;
}

int MEset::FindRoot(const int& i)
{
	int k;
	for (k = i; m_nodes[k].parent >= 0; k = m_nodes[k].parent);
	return k;
}

void MEset::Merge(const int& i, const int& j)
{
	m_nodes[i].parent = j;
}

//子树的根结点的parent域存储子树中所含数据元素个数的负值，在合并时
//令成员少的子树的根结点之parent域指向成员多的子树的跟
void MEset::EffMerge(const int& i, const int& j)
{
	if (m_nodes[i].parent > m_nodes[j].parent)
	{
		m_nodes[j].parent += m_nodes[i].parent;
		m_nodes[i].parent = j;
	}
	else
	{
		m_nodes[i].parent += m_nodes[j].parent;
		m_nodes[j].parent = i;
	}
}

void MEset::Display()
{
	std::cout<<"位置   "<<"data   "<<"parent   "<<std::endl;
	for (int i = 0; i < m_len; i++)
	{
		std::cout<<"  "<<i<<"    "<<m_nodes[i].data
			<<"    "<<m_nodes[i].parent<<std::endl;
	}
}

//main.cpp
#include <iostream>
#include <fstream>
#include "MEset.h"
using namespace std;

void main(int argc, char* argv[])
{
	ifstream cin("input.txt");
	int n,m,i,j,k=1,r1,r2;
	char c,d,ch[256];
	cout<<"请输入集合中元素的个数："<<endl;
	cin>>n;
	MEset a(n);
	cout<<"请输入"<<n<<"个数据元素至集合a："<<endl;
	for (int i = 0; i < n; i++)
	{
		cin>>ch[i];
	}
	cout<<endl;
	a.Create(ch,n);
	a.Display();
	cout<<endl;
	cout<<"请输入等价关系的序偶对个数："<<endl;
	cin>>m;
	cout<<endl;

	while (k <= m)
	{
		cout<<"请输入一个等价关系:"<<endl;
		cin>>c>>d;
		i = a.LocateElem(c);
		j = a.LocateElem(d);
		if (i < 0 || j < 0)
		{
			cout<<"输入有误，请重输！"<<endl;
		}
		else
		{
			r1 = a.FindRoot(i);
			r2 = a.FindRoot(j);
			if (r1 != r2)
			{
				cout<<c<<"和"<<d<<"不是同属于一个等价类"<<endl;
				a.EffMerge(r1,r2);
			}
			else
			{
				cout<<c<<"和"<<d<<"是同一个等价类"<<endl;
			}
			k++;
		}
	}

	cout<<endl;
	a.Display();
	cout<<endl;
	system("pause");
}

输出：