4

重複の可能性：
ヒープツリーのK番目の要素

二分木が与えられた場合、親が0の場合、左の子は0、右の子は1です。親が1の場合、左の子は1、右の子は0です。ツリーのルートは0です。k番目のノード値を見つけます。 N番目のレベルに存在します

私はこのように解決しようとしました。第1レベルに0、第2レベルに01、第3レベルに 01 - 10（つまり、前半の補数）があるとします。
同様0110 1001に第4レベル。

では、このソリューションまたはこの質問を解決する他の方法を一般化するにはどうすればよいですか？

4

2 に答える 2

3

あなたの考えを一般化するために、ツリーのn番目のレベルの要素のリストを与える再帰的な手順を書くことができます.

getLevel(level)

  if level == 0
    return [0]

  upperLevel = getLevel(level - 1)

  return upperLevel + complement(upperLevel)

はリスト[...]、+はリストの連結であり、 への変更、complementおよびその逆です。01

これがあれば、 によって生成されたリストのkth要素を取得するだけですgetLevel(n)。

これはおそらく最適な解決策ではなく、あなたのアイデアに基づいて構築されているだけです (そして簡単です)。

于 2012-12-18T19:09:12.543 に答える
2

最初の数ビットを手動で生成したところ、0110100110010110 が得られました。Google は、これがThue-Morse シーケンスであることを明らかにしています。OEIS のシーケンスA010060。OEIS ページのコメントには次の行があります。

a(n) = S2(n) mod 2、ここで、S2(n) = n の数字の合計、基数 2 表記の n。

nこれがあなたの場合のkでありN、あなたの場合は問題ではありません。したがって、a(n) を決定するには、 の 1 の数を計算しn、この合計の最下位ビットを取得します。

于 2012-12-18T18:54:18.123 に答える