6

文字列、つまり「CPHBDZ」が与えられます。BSTに（この順序で）文字を挿入することにより、次のようになります。

  C
 / \
B   P
   / \
  H   Z
 /
D

文字列の順序を「CBPHDZ」に変更すると、同じツリーが得られます。そして、同じBSTを提供する入力文字列のすべての順列を見つけてリストする必要があります。私はそれらの順列の数を計算する方法を思いついたが、実際にそれらを見つけるアルゴリズムを理解することはできない。

4

2 に答える 2

6

ツリーのバランスをとるためにローテーション (など) を行っていないと仮定すると、ツリーの構造から答えを導き出すことができます。独自の子孫ですが、「ピア」(親でも子孫でもないもの) で自由に再配置できます。

たとえばC、ツリーのルートとしてC持っているので、ストリームから読み取られた最初のアイテムである必要があります。その子孫はBとPであるため、入力の次の項目はこれら 2 つのうちの 1 つでなければなりません。Bには子孫がありませんが、とのP2 つがあるため、 の後に読む必要がありましたが、 に関しては任意の順序で読むことができます。同様に、はおよびに対してどのような順序でもかまいませんが、 の前になければなりません。HZPBZHDHD

編集:これらすべての順列の生成に関して、1 つの簡単な (不正行為) 方法は、Prolog を使用することです。基本的に、その依存関係を「事実」としてエンコードすると、それらの事実に適合するすべての順列が生成されます。実際 (しゃれは意図されていません)、これは Prolog が何であるか/何をするかのほとんどの説明です。

自分でそれを行う場合、おそらくほとんどの作業を再帰的に行いたいと思うでしょう。有効な順序付けは、ルートの後に、その子孫の有効な順序のインターリーブが続きます。

インターリーブを行う方法に関しては、(たとえば) 左側のサブツリーの有効な順序を 1 つ生成し、右側のサブツリーの有効な順序を 1 つ生成します。左側のサブツリーのすべてのアイテムを最初に、右側のサブツリーのすべてのアイテムを最後にして、それらを配列にまとめます。Aデモンストレーションのために、ツリーに(表示されているの子孫として)も含まれていると仮定しましょうB。配列では、サブツリーからのデータは次のようになります。

B A P H Z D

次に、左のサブツリーの最後の項目から開始し、配列を右に「歩き」、毎回新しい順列を生成します。

B P A H Z D
P B A H Z D
B P H A Z D
P B H A Z D
P H B A Z D
[ ... ]

左のサブツリーの有効な順序ごとに、右のサブツリーの有効な順序ごとにこれらすべてのインターリーブを実行する必要があります (親に戻すと、同じことが行われます)。

于 2012-11-20T17:03:45.113 に答える
3

パイソンでは、

tree = {
    'C' : ['B', 'P'],
    'P' : ['H','Z'],
    'H' : ['D']}

def f(tree,  ready):
    if not ready:
        return [[]]
    else:
        rv = []
        for r in ready:
            for rest in f(tree,
                          [n for n in ready if r != n] + tree.get(r, [])):
               rv.append([r] + rest)
        return rv

for o in f(tree, 'C'):
    print ''.join(o)
于 2012-11-20T20:09:26.863 に答える