NYOJ221 Tree

题目分析：
还是那样，作为一个二逼青年，我首先想到的还是定义一个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;
}

补充：软件开发 , C++ ,