1029 遍歷問題

    我們都很熟悉二叉樹的前序、中序、後序遍歷，在數據結構中常提出這樣的問題：已知一棵二叉樹的前序和中序遍歷，求它的後序遍歷，相應的，已知一棵二叉樹的後序遍歷和中序遍歷序列你也能求出它的前序遍歷。然而給定一棵二叉樹的前序和後序，你卻不能確定其中序遍歷序列，考慮如下圖中的幾棵二叉樹：

    所有這些二叉樹都有著相同的前序遍歷和後序遍歷，但中序遍歷卻不相同。

    輸入文件共2行，第一行表示該樹的前序遍歷結果，第二行表示該樹的後序遍歷結果。輸入的字元集合為{a-z}，長度不超過26。

    輸出文件只包含一個不超過長整型的整數，表示可能的中序遍歷序列的總數。

abc

cba

4

思路

只有一個兒子 的節點 才會在知道 前序後序 的情況下有不同的中序遍歷，所以將題目轉化成找 只有一個兒子的節點個數。

可以很容易的找出這類節點在前序後序中出現的規律。（前序中出現AB，後序中出現BA，則這個節點只有一個兒子）

每個這類節點有兩種中序遍歷（及兒子在左，兒子在右）根據乘法原理中序遍曆數為 2^節點個數 種

代碼

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
char qian[30];
char hou[30];
int ans=0;
int main()
{
    scanf("%s%s",qian,hou);
    for(int i=0;i<=strlen(qian)-1;i++)
        for(int j=1;j<=strlen(hou)-1;j++)
            if(qian[i]==hou[j]&&qian[i+1]==hou[j-1])
                ans++;
    printf("%d",1<<ans);
}

2010 求後序遍歷

輸入一棵二叉樹的先序和中序遍歷序列，輸出其後序遍歷序列。

共兩行，第一行一個字元串，表示樹的先序遍歷，第二行一個字元串，表示樹的中序遍歷。

僅一行，表示樹的後序遍歷序列。

abdehicfg

dbheiafcg

dhiebfgca

輸入長度不大於255。

代碼

#include<iostream>
using namespace std;
int len;
string s1,s2;
void dfs(int s,int l,int r)
{
    if(l==r)return;
    int pos=l;
    for(int i=l;i<=r;i++)if(s1[s]==s2[i]){pos=i;break;}
    dfs(s+1,l,pos);
    dfs(s+pos-l+1,pos+1,r);
    cout<<s1[s];
}
int main()
{
    cin>>s1>>s2;
    len=s1.length();
    dfs(0,0,len);
}

3143 二叉樹的序遍歷

求一棵二叉樹的前序遍歷，中序遍歷和後序遍歷

第一行一個整數n，表示這棵樹的節點個數。

接下來n行每行2個整數L和R。第i行的兩個整數Li和Ri代表編號為i的節點的左兒子編號和右兒子編號。

輸出一共三行，分別為前序遍歷，中序遍歷和後序遍歷。編號之間用空格隔開。

5

2 3

4 5

0 0

0 0

0 0

1 2 4 5 3

4 2 5 1 3

4 5 2 3 1

n <= 16

代碼

#include<iostream>
using namespace std;
int n;
struct node{
    int l,r;
}tree[20];
void dfs(int v)
{
    cout<<v<<' ';
    if(tree[v].l!=0)dfs(tree[v].l);
    if(tree[v].r!=0)dfs(tree[v].r);
}
void afs(int v)
{
    if(tree[v].l!=0)afs(tree[v].l);
    cout<<v<<' ';
    if(tree[v].r!=0)afs(tree[v].r);
}
void cfs(int v)
{
    if(tree[v].l!=0)cfs(tree[v].l);
    if(tree[v].r!=0)cfs(tree[v].r);
    cout<<v<<' ';
}
int main()
{
    cin>>n;
    int x,y;
    for(int i=1;i<=n;i++)
    {
        cin>>x>>y;
        tree[i].l=x;
        tree[i].r=y;
    }
    dfs(1);cout<<endl;
    afs(1);cout<<endl;
    cfs(1);
}