跳至正文

NOIP_2001.PJ3:求先序排列 解题报告

  • OI路程

在车上想了好久,终于找到了突破口,后序遍历不就是说最后一个节点就是当前书的根节点吗?那不就好说了,先把后序中的最后一个节点在中序中找到下标i,那小于i的便是左子树了,大于的的便是右子树了,而题目要的是先序,那就先把第i个(即后序的最后一个)输出来,然后再分别对左子树和右子树进行递归,然后后序从0~i-1都是左子树,后序i~len – i – 1(len是树的长度)是右子树。
现在解释一下,0~i-1是后序的长度的原因是无论是先序还是后序还是中序都是同一棵树,长度必然相同,现在把一棵树分成了两棵树,长度一定还是相同的,所以这是可以成立的。
然后别的什么我不说了,祝大家细心一点,这题我提交了n次才AC(哪里错了注释在里面的)。。

C语言:

#include <stdio.h>
char mid[90];
char last[90];
char first[90];

void srch(int start, int len, int start2)
/* 第一个参数代表中序中的开头位置, len代表长度, start2 代表后序开头的位置 */
{
 int i;
 if(len <= 0){ //掉了....=_=||| 
 return ;
 }
 printf(%c, last[start2 + len - 1]);
 for(i = 0; i < len; i++){
 if(mid[i + start] == last[start2 + len - 1]){
 break;
 }
 }
 srch(start, i, start2);
 srch(i + 1 + start, len - i - 1, i + start2);
 /* 巨大的错误, 第一个参数忘记加start了, 第三个参数忘记加start2了 */
}

int main(void)
{
 scanf(%s %s, mid, last);
 srch(0, strlen(mid), 0);
 printf(\\n);
 return 0;
}

发表回复

您的电子邮箱地址不会被公开。