선행 및 후행 트래버스에서 k-ary 트리의 수

Question

선행 및 후행 탐색 및 k가 주어진 것으로 가정합니다. 얼마나 많은 k-ary 나무가이 횡단과 함께 있습니까?

k-ary 트리는 각 꼭지점이 최대 k 개의 자식을 갖는 루트 트리입니다.

Answer 1

특정 트래버 설 쌍에 따라 다릅니다. (당신이 일관성이 통과 쌍을 포함하지 않는 한, 가장 적은 수) 예를 들어

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

는 단지 하나의 가능한 트리를 설명합니다. 한편 :

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

2^(3-1) = 4 나무합니다 (순회 아무것도 할 수 3 개 노드 (K)가 모든 시나리오 사이에서 최대한), 즉 4 3 노드 라인을 설명 .

Answer 2

선주문 및 순차적 순회가 가능한 이진 트리의 수를 알고 싶다면 먼저 가능한 트리 하나를 그려야합니다. 한 명의 자식 만 가진 노드의 수를 세십시오. 가능한 나무의 총 수는 다음과 같습니다 예를 들어

2^(단일 자식 노드의 수) : 사전 : adbefgchij 게시물 : dgfebijhca

내가 3 단일 자식 노드가 하나의 트리를 그릴 . 따라서 가능한 나무의 수는 8입니다.

Answer 3

먼저 서브 트리의 해당 범위를 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; 
}