1.cpp

已知二叉树的先序、中序遍历的结果

#include<iostream.h>
#include<string.h>
#define OK               1;
#define TRUE             1;
#define FALSE            0;
#define maxsize 100
typedef int Status;
struct Node             //节点结构体
{
	char data;
	Node* left;
	Node* right;
};
struct BTree           //二叉树结构体
{
	Node* root;
};
typedef struct         //栈结构体
{
     Node* Elem[maxsize];
     int top;
}Stack;
BTree *btree;
char pre[100];         //存储前序遍历结果
char in[100];          //存储中续遍历结果
char *Getleft(char *str,char a);        
char *Getright(char *str,char a);
char path[100];        //存储根节点到某节点的路径
int pathnum(0);        //路径长度

//通过前序和中序遍历结果构造二叉树的函数：
int InPreOrder(char *in,Node *node)
{
	int find(0);

	//在中序遍历结果中寻找前序遍历结果的第一个节点，即根节点：

	for(unsigned int i=0;i<strlen(pre);i++)        
	{
		for(unsigned int j=0;j<strlen(in);j++)
			if(pre[i]==in[j])
				find=1;
		if(find)
			break;
		find=0;
	}
	node->data=pre[i];                                //建立根节点
	node->left=new Node;
	node->right=new Node;

	//递归,在根节点的左边右边分别作同样的工作

	if(Getleft(in,pre[i]))                            
	    InPreOrder(Getleft(in,pre[i]),node->left);
	else
		node->left=NULL;                               //叶结点
	if(Getright(in,pre[i]))
		InPreOrder(Getright(in,pre[i]),node->right);
	else
		node->right=NULL;                              //叶结点
	return 1;
}

//取得字符串str以a为分界的左边的字符串
char *Getleft(char *str,char a)
{
	char *temp;
	for(unsigned int i=0;i<strlen(str);i++)
	{
		if(str[i]==a)
			break;
	}
	if(i==0)
		return NULL;
	temp=new char[i];
	for(unsigned int j=0;j<i;j++)
		temp[j]=str[j];
	temp[i]='\0';
	return temp;
}

//取得字符串str以a为分界的右边的字符串
char *Getright(char *str,char a)
{
	char *temp;
	for(unsigned int i=0;i<strlen(str);i++)
		if(str[i]==a)
			break;
	if(i>=strlen(str)-1)
		return NULL;
	i++;
	temp=new char[strlen(str)-i];
	temp[strlen(str)-i]='\0';
	for(int j=0;i<strlen(str);j++)
	{
		temp[j]=str[i];
		i++;
	}
	return temp;
}

//栈的基本操作实现函数
Status InitStack(Stack &S)     //构造一个空栈
{
	S.top=0;
	return OK;
}
Status StackEmpty(Stack &S)    //若栈S为空栈则返回TURE,否则返回FALSE
{
	if(S.top==0) return TRUE;
	return FALSE;
}
Status Push(Stack &S,Node* e)  //插入元素e为新的栈顶元素
{
	S.Elem[S.top]=e;
	S.top++;
	return OK;
}
Node* Pop(Stack &S)            //若栈不空则删除S的栈顶元素,用e返回其值
{
	Node* e;
	if(S.top==0) e=NULL;
	else {e=S.Elem[S.top-1];
	S.top--;}
	return e;
}
Node* GetTop(Stack &S)          //若栈不空则返回S的栈顶元素,否则返回NULL
{
	if(S.top==0) return NULL;
	return S.Elem[S.top-1];
}

//后序遍历函数
void PostOrder(Node *root)
{
	Stack s;
	InitStack(s);
	Node* p=root;
	Node* q;
	do{
		Push(s,p);               //当前节点入栈
		if(p->right!=NULL&&p->left==NULL)
		{
			p=p->right;
		}                        //如果没有左节点只有右节点，右节点成为当前节点
		else if(p->left!=NULL)    
		{
			p=p->left;
		}                        //如果有左节点，左节点成为当前节点
		else if(p->left==NULL&&p->right==NULL)
		{                        //如果发现叶节点
			q=Pop(s);
			cout<<q->data;
			if(!StackEmpty(s))
			{
				p=GetTop(s);
				while(p->right==q||p->right==NULL)
				{
					q=Pop(s);
					cout<<q->data;
					if(!StackEmpty(s))
						p=GetTop(s);
					else break;
				}
				p=p->right;
			}
			else break;
		}
	}while(!StackEmpty(s));        //循环完成遍历结束
	cout<<endl;
}
 
//求根节点到a节点的路径，存在path数组中
int Print(Node* T,char a)
{
	if(!T)
		return 0;
	Node* temp=T;
	if(temp->data==a)
		{
			path[pathnum]=temp->data;
			pathnum++;
			return 1;
		}
	else if(temp->left||temp->right) 
		if(Print(temp->left,a)||Print(temp->right,a))   //递归
		{
			path[pathnum]=temp->data;
			pathnum++;
			return 1;
		}
		else 
			return 0; 
	else
		return 0;
}

//主函数负责输入输出，控制程序流程
void main()
{
	int iferror(0);                        //判断输入是否有误，或有重复字符
	char a;
	char ifcontinue='a';
	btree=new BTree;
	btree->root=new Node;
	cout<<"请输入前序遍历结果："<<endl;
	while(1)                               //输入不能重复
	{
		iferror=0;
		cin>>pre;
		for(unsigned int i=0;i<strlen(pre);i++)
			for(unsigned int j=0;j<i;j++)
				if(pre[i]==pre[j])
					iferror=1;
		if(iferror)
			cout<<"输入有重复，请重新输入！"<<endl;
		else
			break;
	}
	cout<<"请输入中序遍历结果："<<endl;
	while(1)                                //中序遍历要与前序遍历匹配
	{
		iferror=0;
		cin>>in;
		for(unsigned int i=0;i<strlen(in);i++)
			for(unsigned int j=0;j<i;j++)
				if(in[i]==in[j])
					iferror=1;
		if(iferror)
		{
			cout<<"输入有重复，请重新输入！"<<endl;
			continue;
		}
		if(strlen(in)!=strlen(pre))
		{
			cout<<"输入错误，请重新输入！"<<endl;
			continue;
		}
		for(i=0;i<strlen(in);i++)
		{
			iferror=1;
			for(unsigned int j=0;j<strlen(in);j++)
				if(pre[j]==in[i])
				{
					iferror=0;
					break;
				}
		}
		if(iferror)
		{
			cout<<"输入错误，请重新输入！"<<endl;
			continue;
		}
		else
			break;
	}
	InPreOrder(in,btree->root);                  //构造二叉树
	cout<<"后序遍历结果为："<<endl;
	PostOrder(btree->root);                      //后序遍历
	while(ifcontinue!=48)                        //节点路径查询
	{
		cout<<"请输入要查询的节点："<<endl;
		cin>>a;
		if(Print(btree->root,a))
		{
			cout<<"路径为：";
    		for(int i=pathnum-1;i>=0;i--)
				cout<<path[i];
			cout<<endl;
		}
		else
			cout<<"无此节点！"<<endl;
		pathnum=0;
		cout<<"退出请按0，按任意键继续："<<endl;
		cin>>ifcontinue;
	}
}