math - 前順および後順トラバーサルからの k-ary ツリーの数

Question

プレオーダーおよびポストオーダーのトラバーサルと k が与えられているとします。これらのトラバーサルを含む k-ary ツリーはいくつありますか?

k 分木は、各頂点が最大 k 個の子を持つ根付き木です。

Answer 1

これは、特定のトラバーサル ペアによって異なります。例えば

pre-order:  a b c
post-order: b c a

可能なツリーを 1 つだけ記述します (一貫性のないトラバーサル ペアを含めない限り、可能な限り少ない)。一方で：

pre-order:  a b c
post-order: c b a

は 2^(3-1) = 4 ツリー (トラバーサルに 3 つのノードがあり、k は何でもよいすべてのシナリオの中で最も可能性が高い)、つまり 4 つの 3 ノード ラインを表します。

Answer 2

まず、DFSで対応する部分木の範囲を決定し、部分木の量を取得してから、部分木の組み合わせで解決します。

const int maxn = 30;
int C[maxn][maxn];
char pre[maxn],post[maxn];
int n,m;

void prepare()
{
    memset(C,0,sizeof(C));
    for(int i=0;i<maxn;i++)
    {
        C[i][0] = 1;
    }
    for(int i=1;i<maxn;i++)
    {
        for(int j=1;j<=i;j++)
        {
            C[i][j] = C[i-1][j-1] + C[i-1][j];
        }
    }
    return;
}

int dfs(int rs,int rt,int os,int ot)
{
    if(rs == rt) return 1;
    int son = 0,res = 1;
    int l = rs + 1,r = os;
    while(l <= rt)
    {
        while(r < ot)
        {
            if(pre[l] == post[r])
            {
                son++;
                break;
            }
            r++;
        }
        res *= dfs(l , l + r - os , os , r);
        l += r - os + 1;
        rs = l - 1;
        os = ++r;
    }
    return res * C[m][son];
}

int main()
{
    prepare();
    while(scanf("%d",&m) && m)
    {
        scanf("%s %s",pre,post);
        n = strlen(pre);
        printf("%d\n",dfs(0,n-1,0,n-1));
    }
    return 0;
}

Answer 3

Pre-order トラバーサルと Post-order トラバーサルを持つ可能なバイナリ ツリーの数を知りたい場合は、最初に 1 つの可能なツリーを描画する必要があります。次に、子が 1 つだけのノードの数を数えます。可能なツリーの総数は次のようになります: 2^(単一の子ノードの数)

例: pre: adbefgchij post: dgfebijhca

3 つの単一の子ノードを持つ 1 つのツリーを描画します。したがって、可能な木の数は 8 です。