OI

【树】各种树的先序后序

今天集中把二叉树的各种遍历刷掉了。（虽然都写得很暴力，但是暴力有暴力的好处嘛）

P1305新二叉树

本来是应该用结构体然后指针指儿子建树的，可是一看只有26个字母，就直接一维数组存了，最坏情况也就2^26-1个节点，而且刚好用char存只占一个字节比int省了（爽到）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include<stdio.h>
char tree[67108870];
int hash[300]={0};
void first(int rt){
    if(tree[rt]=='*')return;
    printf("%c",tree[rt]);
    first(rt*2+1);
    first(rt*2+2);
}
int main(){
    int n,i,j,rt;
    char t[10];
    scanf("%d",&n);
    for(i=1;i<=n;i++){
        scanf("%s",t);
        rt=hash[t[0]];
        tree[rt]=t[0];
        tree[rt*2+1]=t[1];
        tree[rt*2+2]=t[2];
        hash[t[0]]=rt;
        hash[t[1]]=rt*2+1;
        hash[t[2]]=rt*2+2;
    }
    first(0);
    return 0;
}

P1030求先序排列

这题更暴力

根据遍历定义和二叉树的性质就知道应该是二分递归求解的。

中序：左根右

后序：左右根

先序：根左右

由此，方法就是

1
2
3
4
5
6
7
f(中序，后序){
    输出根；//后序的最后一个
    在中序中找到左右子树；
    在后序中找到左右子树；
    f(左子树中序，左子树后序)；
    f(右子树中序，右子树后序)；
}

中序只要找到根节点，左右子树马上就有了。后序呢？
后序就暴力了，枚举了中序的左子树找右边界或者枚举右子树找左边界……

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include<stdio.h>
#include<string.h>
char mid[100],last[100];

void first(int midl,int midr,int lastl,int lastr){
    if(midl>midr||lastl>lastr)return;
    char t=last[lastr];
    int i,j,mrt,max=-1,min=100;
    printf("%c",t);
    for(i=midl;i<=midr;i++)
        if(t==mid[i]){mrt=i;break;}
    for(i=midl;i<mrt;i++)
      for(j=lastl;j<lastr;j++)
        if(mid[i]==last[j]&&j>max)max=j;
    for(i=mrt+1;i<=midr;i++)
      for(j=lastl;j<lastr;j++)
        if(mid[i]==last[j]&&j<min)min=j;
    if(min!=100)max=min-1;
    else if(max!=-1)min=max+1;
    first(midl,mrt-1,lastl,max);
    first(mrt+1,midr,min,lastr-1);
}

int main(){
    int len;
    scanf("%s",mid);
    scanf("%s",last); 
    len=strlen(mid);
    first(0,len-1,0,len-1);
    return 0;
}

另外，一定要用scanf/printf，原因不明……