用Python做表达式树

Thunderbee

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

1. # 二分木のノードでデータ構造を配列で実現
   
2. 
   
3. LABEL, LEFT, RIGHT = 0, 1, 2 # 配列上の位置の定数設定
   
4. WS = 10
   
5. 
   
6. # 木の表示
   
7. def show(node, lside = '', fill = ''):
   
8.   _lv_ = '[' + str(node[LABEL]) + ']'                    # ノードのラベル文字列
   
9.   if node[RIGHT] == None:  # 右ノードが無い
   
10.     print(lside + _lv_)
    
11.     if node[LEFT] != None: # 左ノードがある（下に表示が必要）
    
12.       print(fill + ' |')
    
13.       show(node[LEFT], fill, fill)
    
14.   else:                    # 右ノードがある場合
    
15.     _ln_ = lside + (_lv_ + '-' * WS)[:WS] # 左側のノード表示文字列
    
16.     if node[LEFT] == None: # 左ノードが無い
    
17.       show(node[RIGHT], _ln_, fill + ' ' * WS)
    
18.     else:                  # 左ノードがある（下に表示が必要）
    
19.       show(node[RIGHT], _ln_, fill + ' |' + ' ' * (WS - 2))
    
20.       print(fill + ' |')
    
21.       show(node[LEFT], fill, fill)
    
22. 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]]]]
    
23. show(standard)
    
24. 
    
25. def mktree(h):
    
26.     if h == 0:  # 高さが0ならば葉を生やす
    
27.         return ['葉', None, None]
    
28.     else:         # h - 1 の木を作り、枝をつなぐ
    
29.         return ['枝', mktree(h - 1), mktree(h - 1)]
    
30. 
    
31. tree = mktree(3)  # 高さ h = 3 の木を茂らせる
    
32. print(tree)
    
33. show(tree)

复制代码