用Python做表达式树

Thunderbee

怎么用Python做一个高为h的满二叉树

# 二分木のノードでデータ構造を配列で実現

LABEL, LEFT, RIGHT = 0, 1, 2 # 配列上の位置の定数設定
WS = 10

# 木の表示
def show(node, lside = '', fill = ''):
  _lv_ = '[' + str(node[LABEL]) + ']'                    # ノードのラベル文字列
  if node[RIGHT] == None:  # 右ノードが無い
    print(lside + _lv_)
    if node[LEFT] != None: # 左ノードがある（下に表示が必要）
      print(fill + ' |')
      show(node[LEFT], fill, fill)
  else:                    # 右ノードがある場合
    _ln_ = lside + (_lv_ + '-' * WS)[:WS] # 左側のノード表示文字列
    if node[LEFT] == None: # 左ノードが無い
      show(node[RIGHT], _ln_, fill + ' ' * WS)
    else:                  # 左ノードがある（下に表示が必要）
      show(node[RIGHT], _ln_, fill + ' |' + ' ' * (WS - 2))
      print(fill + ' |')
      show(node[LEFT], fill, fill)
standard = [1,[2,[3,[4, None, None], [5, None, None]],[6,[7, None, None], [8, None, None]]],[9,[10,[11, None, None], [12, None, None]],[13,[14, None, None], [15, None, None]]]]
show(standard)

def mktree(h):
    if h == 0:  # 高さが0ならば葉を生やす
        return ['葉', None, None]
    else:         # h - 1 の木を作り、枝をつなぐ
        return ['枝', mktree(h - 1), mktree(h - 1)]

tree = mktree(3)  # 高さ h = 3 の木を茂らせる
print(tree)
show(tree)