題目分析：
還是那樣，作為一個二逼青年，我首先想到的還是定義一個NODE的結構體，然後建立樹，然後.......可是，你有沒有想過字符串的感受啊~~也許，你經常忽視的人可能會給你最好的東西。廢話不多說，盡管是二逼青年的想法，也要說出來嘛~都有表達想法的權利是不？
PS：咳咳~~有沒有覺得樓主分析題目的語言诙諧幽默，小自戀一下啦~~~
OK，進入正題。對於樹的操作，最簡單的肯定是遞歸啦。重建樹的步驟：
1、前序遍歷的第一個節點是根節點。
2、在中序遍歷中找到這個根節點，然後把中序遍歷的字符串分成了左串和右串，也就是該根節點的左子樹和右子樹。
3、OK,遞歸下去就可以了，遞歸的出口就是root後面的節點個數小於等於0.3、OK,遞歸下去就可以了，遞歸的出口就是root後面的節點個數小於等於0.
忘了說了，這裡為了避免在Rebuild裡面不斷的申請空間和過後不斷的釋放空間，預先定義了一個node數組。因為最多自由26個節點，所以內存可以重復使用。
按理這果斷不是GC，因為妹紙我馬上要給出另一種方法。搞定之後再發啦~直接基於字符串處理的方法
[cpp]
#include<stdio.h>
#include<string.h>
struct NODE
{
char ch;
NODE *Left;
NODE *Right;
};
const int N = 27;
NODE node[N];
NODE *stack[N];
int num;
void Rebuild(char *PreStr, char *InStr, int nLen, NODE **root)
{
if(nLen <= 0)
return;
if((*root) == NULL)
{
node[++num].ch = PreStr[0];
(*root) = &node[num];
}
else
(*root)->ch = PreStr[0];
if(nLen == 1)
return;
int i;
for(i = 0; i < nLen; ++i)
{
if(PreStr[0] == InStr[i])
break;
}
Rebuild(&PreStr[1], &InStr[0], i, &(*root)->Left);
Rebuild(&PreStr[i + 1], &InStr[i + 1], nLen - i - 1, &(*root)->Right);
}
void Post(NODE *root)
{
if(!root)
return;
Post(root->Left);
Post(root->Right);
printf("%c",root->ch);
}
int main()
{
char PreStr[27];
char InStr[27];
NODE *root;
int nLen;
while(scanf("%s %s", PreStr, InStr) != EOF)
{
root = NULL;
nLen = strlen(PreStr);
memset(node, 0 ,sizeof(node));
num = -1;
Rebuild(PreStr, InStr, nLen, &root);
Post(&node[0]);
printf("\n");
}
return 0;
}
#include<stdio.h>
#include<string.h>
struct NODE
{
char ch;
NODE *Left;
NODE *Right;
};
const int N = 27;
NODE node[N];
NODE *stack[N];
int num;
void Rebuild(char *PreStr, char *InStr, int nLen, NODE **root)
{
if(nLen <= 0)
return;
if((*root) == NULL)
{
node[++num].ch = PreStr[0];
(*root) = &node[num];
}
else
(*root)->ch = PreStr[0];
if(nLen == 1)
return;
int i;
for(i = 0; i < nLen; ++i)
{
if(PreStr[0] == InStr[i])
break;
}
Rebuild(&PreStr[1], &InStr[0], i, &(*root)->Left);
Rebuild(&PreStr[i + 1], &InStr[i + 1], nLen - i - 1, &(*root)->Right);
}
void Post(NODE *root)
{
if(!root)
return;
Post(root->Left);
Post(root->Right);
printf("%c",root->ch);
}
int main()
{
char PreStr[27];
char InStr[27];
NODE *root;
int nLen;
while(scanf("%s %s", PreStr, InStr) != EOF)
{
root = NULL;
nLen = strlen(PreStr);
memset(node, 0 ,sizeof(node));
num = -1;
Rebuild(PreStr, InStr, nLen, &root);
Post(&node[0]);
printf("\n");
}
return 0;
}
