可能なすべてのバイナリツリーが1回のトラバーサルで与えられる

Question

バイナリツリー（必ずしもBSTではない）のインバーストラバーサルのみ（またはポストオーダー/プリオーダのみ）のトラバースが与えられた場合、このトラバーサルで可能なすべてのバイナリツリーを生成する方法は？

「n」ノードで与えられたバイナリツリーの数は（2^n）-nですが、ツリーの単一のトラバーサルにアクセスできる場合、このアルゴリズムをどのようにコード化できますか？

Answer 1

再帰的に行います。

def emptyTree(): 
    return None 

def node(l,d,r): 
    return (l,d,r) 

def singleton(x): 
    return (emptyTree(),x,emptyTree()) 

def allBT(trav,length): 
    if length == 0: 
     return [emptyTree()] 
    if length == 1: 
     return [singleton(trav[0])] 
    trees = [node(emptyTree(),trav[0],right) for right in allBT(trav[1:],length-1)] 
    trees += [node(left,trav[i],right) for i in xrange(1,length-1) for left in allBT(trav[:i],i) for right in allBT(trav[i+1:],length-i-1)] 
    trees += [node(left,trav[length-1],emptyTree()) for left in allBT(trav[:length-1],length-1)] 
    return trees 

def allBinaryTrees(trav): 
    return allBT(trav,len(trav)) 

ところで、あなたのバイナリツリーの数は間違っています。ノードが0個、ノードが1個のツリーが1つあり、ノードが2個あるツリーが2個あります。私たちはrootに各項目を選ぶことができますし、後にn-i-1ノードに対するそれぞれの可能性を持つ前にiノードに対して各可能性を組み合わせることができますので、再帰は

T(n) = \sum_{i = 0}^{n-1} T(i)*T(n-i-1) 

です。したがってT(3) = 5, T(4) = 14, T(5) = 42, T(6) = 132, ...