5.cpp

实验描述：树的前序遍历和中序遍历结果可以确定一棵树。 输入树的前序遍历结果和中序遍历结果建立起这棵树并给出后序遍历结果。

#include <iostream>
#include <string>
using namespace std;

typedef char ElemtType;
struct node       //二叉树结点类定义
{
	ElemtType Data;
	struct node* Leftchild;
	struct node* Rightchild;
};

class BTree
{
private:
	node* Boot;
	PostorderTraversal(node* T)//递归输出后序遍历结果
	{
		if (T!=NULL)
		{
			PostorderTraversal(T->Leftchild);
			PostorderTraversal(T->Rightchild);
			cout<<T->Data;
		}
	}
public:
	void FreeChilds(node* ptr){    //递归删除树的左右子树
		if (ptr!=NULL)
		{
			FreeChilds(ptr->Leftchild);
			FreeChilds(ptr->Rightchild);
			delete ptr;
		}
	}
	void FreeItself()   //删除所有子树结点，即删除整棵树
	{
		FreeChilds(Boot);
	}
	node* getBoot(){return Boot;}  //获得结点
	BTree(){Boot = NULL;}  
	BTree(node* root){Boot = root;}//构造空树
	~BTree();	
	PostorderTraversal(void)      //后序遍历输出结果
	{
		PostorderTraversal(Boot);
		cout<<endl;
	}
};
node* RestoreBTreeNodes(char* preorder, char* inorder, int size)  //存储树的结点，建立树
{
	if (size ==0)
	{
		return NULL;//树为空
	}
	node *newNode = new node;
	newNode->Data = preorder[0];
	newNode->Leftchild = NULL;
	newNode->Rightchild = NULL;
	
	char* rpos;
	
	for (rpos=inorder;rpos<inorder+size;rpos++)//在中序遍历结果中搜索等于前序遍历结果第一个结点的位子
	{
		if (*rpos ==*preorder)
		{
			break;
		}
	}
	int i = rpos - inorder;//从在inorder找到的根结点处将结果分成两部分，左子树和右子树 
	newNode->Leftchild = RestoreBTreeNodes(preorder+1,inorder,i);//递归调用
	newNode->Rightchild = RestoreBTreeNodes(preorder+1+i, rpos+1, size-1-i);
	return newNode;	//返回根结点
}

BTree* RestoreBTree(char* preoder, char* inorder, int size)  //树结点的建立
{

	BTree   *root = new BTree(RestoreBTreeNodes(preoder,inorder,size));
	

	return root;	
}

int CheckValidInputs(char* a, char* b, int size)  //对输入的前序和中序遍历结果检验是否信息相同，这是形成树的前提
{
	int* c= new int[size];
	memset( c, 0, sizeof(int)*size );//将数组c大小为size 的地方 ，用0填充，如果结果数组c全为1则说明信息相同，反之只要有一个为0 则不相同
	int i,j,k;
	
	for (i=0;i<size;i++)
	{
		for (j=0;j<size;j++)
		{
			if (a[i]==b[j]&&!c[j])
			{
				c[j]=1;
				break;
			}
		}
	}
	for (k=0;k<size;k++)
	{
		if (c[k]==0)
		{
			return 0;
		}
	}
	return 1;
}
int main(int argc, char* argv[])
{
	int size;
	char* preorder;
	char* inorder;
	string strPreorder;
	string strInorder;
	if (argc == 2)
	{
		cout<<"Wrong Arguments!"<<endl;
		cout<<"USAGE: preorder inorder"<<endl;
		return -1;
	}
	else if (argc ==3)
	{
		preorder = argv[1];
		inorder = argv[2];
		for (size = 0;preorder[size]!='\0';size++)//求size
			;

	}
	else if (argc == 1)
	{
		
		
	
		cout<<"Input the preorder:";
		cin>>strPreorder;
		preorder =(char*) strPreorder.c_str();
		cout<<"Input the inorder :";
		cin>>strInorder;
		inorder = (char*)strInorder.c_str();
		size = strInorder.length();	
	
	}

	
	//Check  the valid inputs
	if (!CheckValidInputs(preorder,inorder,size))
	{
		cout<<"Invalid input!"<<endl;
	}

	BTree* btree = RestoreBTree(preorder,inorder,size);
	btree->PostorderTraversal();//后序遍历输出结果

	btree->FreeItself();//删除树

	return 1;
}