從python中的列表構造二叉樹的最佳方法

假設每個節點都有self.left,self.right和self.data，那麼從數字列表中構建二叉樹而不是二叉搜索樹（BST）的最佳方法是什麼？是每個級別給出的。第一個數字是第一個數字，第二個數字是第二個數字，第四個數字是第三個數字，以此類推。例如從python中的列表構造二叉樹的最佳方法

input: [3,5,2,1,4,6,7,8,9,10,11,12,13,14]

構建一個樹：

  3 
    / \ 
    5   2 
    /\   /\ 
    1 4  6 7 
    /\ /\  /\ /\ 
8 9 10 11 12 13 14

一種解決方案是：

for node at index i, 
left child index = 2i+1 
right child index = 2i+2

是否有其他可能的方式

來源

2017-03-29 user1179317

我會說，開始的最好方式是實現一個或兩個算法，然後比較性能並使用反饋循環來改進代碼。 –

這裏是想知道，以實現解決方案的一種方式：創建一個樹節點列表，每個樹節點的索引位置對應於原始數據列表。然後，我們可以修復左側和右側的鏈接。

import logging 

logging.basicConfig(level=logging.DEBUG) 
logger = logging.getLogger(__name__) 

class Tree(object): 
    def __init__(self, data, left=None, right=None): 
     self.data = data 
     self.left = left 
     self.right = right 

    def __repr__(self): 
     left = None if self.left is None else self.left.data 
     right = None if self.right is None else self.right.data 
     return '(D:{}, L:{}, R:{})'.format(self.data, left, right) 

def build_tree_breadth_first(sequence): 
    # Create a list of trees 
    forest = [Tree(x) for x in sequence] 

    # Fix up the left- and right links 
    count = len(forest) 
    for index, tree in enumerate(forest): 
     left_index = 2 * index + 1 
     if left_index < count: 
      tree.left = forest[left_index] 

     right_index = 2 * index + 2 
     if right_index < count: 
      tree.right = forest[right_index] 

    for index, tree in enumerate(forest): 
     logger.debug('[{}]: {}'.format(index, tree)) 
    return forest[0] # root 

def main(): 
    data = [3, 5, 2, 1, 4, 6, 7, 8, 9, 10, 11, 12, 13, 14] 
    root = build_tree_breadth_first(data) 
    print 'Root is:', root 

if __name__ == '__main__': 
    main()

輸出：

DEBUG:__main__:[0]: (D:3, L:5, R:2) 
DEBUG:__main__:[1]: (D:5, L:1, R:4) 
DEBUG:__main__:[2]: (D:2, L:6, R:7) 
DEBUG:__main__:[3]: (D:1, L:8, R:9) 
DEBUG:__main__:[4]: (D:4, L:10, R:11) 
DEBUG:__main__:[5]: (D:6, L:12, R:13) 
DEBUG:__main__:[6]: (D:7, L:14, R:None) 
DEBUG:__main__:[7]: (D:8, L:None, R:None) 
DEBUG:__main__:[8]: (D:9, L:None, R:None) 
DEBUG:__main__:[9]: (D:10, L:None, R:None) 
DEBUG:__main__:[10]: (D:11, L:None, R:None) 
DEBUG:__main__:[11]: (D:12, L:None, R:None) 
DEBUG:__main__:[12]: (D:13, L:None, R:None) 
DEBUG:__main__:[13]: (D:14, L:None, R:None) 
Root is: (D:3, L:5, R:2)

來源

2017-03-29 16:13:27

一種方式做到這一點是建立在當前的樹葉fringe。

假設Node類：

class Node(object): 
    def __init__(self, data): 
     self.data = data 
     self.left = '*' 
     self.right = '*' 
    def __str__(self): 
     return f'<{self.data}, {self.left}, {self.right}>' # Py 3.6

然後，你可以管理fringe和迭代data：

from collections import deque 

data = [3,5,2,1,4,6,7,8,9,10,11,12,13,14] 
n = iter(data) 
tree = Node(next(n)) 
fringe = deque([tree]) 
while True: 
    head = fringe.popleft() 
    try: 
     head.left = Node(next(n)) 
     fringe.append(head.left) 
     head.right = Node(next(n)) 
     fringe.append(head.right) 
    except StopIteration: 
     break 

print(tree) 
# <3, <5, <1, <8, *, *>, <9, *, *>>, <4, <10, *, *>, <11, *, *>>>, <2, <6, <12, *, *>, <13, *, *>>, <7, <14, *, *>, *>>>

來源

2017-03-29 16:46:43 AChampion

很酷的解決方案。爲了構建樹，我一直試圖「逆向工程」廣度優先遍歷，但沒有成功。 –

從python中的列表構造二叉樹的最佳方法

回答

相關問題