完全二分木の生成の方法

Question

###完全二分木の生成の方法

pythonで深さｎの完全二分木を作ってそれで木構造に基づいて数式を作ろうと考えています。
しかし深さが十分に大きいものを作ろうとしているため、一つ一つノードを決めて作ることができません。
どのように完全二分木の構造を作ればよいかお教え願います。

Answer 1

要素数が2^(n+1)のリストaを，以下のようにして
深さnの完全二分木に見立てるのはいかがでしょうか？

• a[0]は使わない
• a[1]を完全二分木の根とする
• i=1,2,...,2^n-1について
  a[i]の左の子はa[2i]，a[i]の右の子はa[2i+1]
• i=2,3,...,2^(n+1)-1について
  a[i]の親はai/2

例) nが7，iが43のとき
リストaの要素数は2^8=256，a[1]が根，深さは7
a[43]の左の子はa[86]，右の子はa[87]，親はa[21]

Comments

[milano]

ありがとうございます。参考になりました。