mid_pre_post.cpp

由二叉树的中序访问序列和后序访问序列

// Mid_Pre_Post.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <iostream.h>
#include <string.h>
const int MaxEle=3;				//访问序列最大字符长度	
int k=0;
char Mid[MaxEle],Post[MaxEle],Pre[MaxEle];
void Init(void);					//初始化
void Find(char*);			//找先序的递归算法
void Init()
{
cout << "Mid-order:";
cin >> Mid;
cout << "Post-order:";
cin >> Post;
cout << "Pre-order:";
}
void Find(char* s)
{
	int i,q,j,p;
	char t[MaxEle+1];

	if (!strcmp((char *)s,"")) return;
	if (strlen(s) == 1) {
		Pre[k++]=*s;
		return;
	}
	for(p=MaxEle-1;p>=0;p--){
		j=0;
		while(s[j]!='\0' && s[j]!=Post[p]) j++;
		if (j!=strlen(s)) break;
	}
		
	for (i=strlen(s)-1;i>=0;i--) {
		if (s[i]==Post[p]) {
			q=i;
			Pre[k++]=Post[p--];
			break;
		}
	}
	
	for (i=0;i<q;i++)
		t[i]=s[i];
	t[q]='\0';
	Find(t);								//左子树递归

	for (i=q+1;s[i]!='\0';i++)
		t[i-q-1]=s[i];
	t[strlen(s)-q-1]='\0';
	Find(t);								//右子树递归
	
	return;
}

int main(int argc, char* argv[])
{
	Init();
	Find(Mid);
	cout<<Pre<<endl;
	return 0;
}