如何將平面列表轉換爲二進制樹

-2

flat_list = [None, 10, 5, 15, None, None, 11, 22]

我知道的算法從一個坐落列表創建樹是這樣：

def create_tree_from_nested_list(node_list): 
    if not node_list: 
     return node_list 
    d, l, r = node_list 
    tree = BinaryTree(d) 
    tree.set_left(create_tree_from_nested_list(l)) 
    tree.set_right(create_tree_from_nested_list(r)) 
    return tree

的代碼的輸出上面會：

10 
(l) 5 
(r) 15 
(l)  11 
(r)  22

我將如何去創造，以平面列表的功能到樹木，使左者存儲在索引位置2*i，正確的存儲在索引位置2 * i + 1，並且輸出與嵌套列表的輸出相同。任何幫助表示讚賞。

來源

2017-02-02 R. Mercy

對於圭多的愛！停止與吸氣和安裝人員。這不是Java。 –

無論如何，我真的不知道你的問題。什麼是預期的輸出？什麼是等效的嵌套列表？ –

對不起，我應該澄清更好。輸出對於嵌套列表和平面列表應該是相同的。 –

您可以修改您的嵌套列表代碼以在平面列表上工作。由於沒有簡單的方法來拆分子樹列表，我建議將相應的節點索引作爲參數傳遞給整個扁平列表。該指數將有1一個默認的（這樣你就不會需要通過它的根節點）：

def create_tree_from_flat_list(node_list, index=1): 
    if index >= len(node_list) or node_list[index] is None: 
     return None 
    d = node_list[index] 
    l = index * 2 
    r = l + 1 
    tree = BinaryTree(d) 
    tree.set_left(create_tree_from_flat_list(node_list, l)) 
    tree.set_right(create_tree_from_flat_list(node_list, r)) 
    return tree

這不是在所有必須有獨立的d，l和r變量在這個函數（他們每個人都可以在他們使用的地方進行計算）。我這樣做是爲了使函數更明顯地與嵌套列表版本平行。 l和r是左右子樹的根的索引。

輸出示例：

> print(create_tree_from_flat_list([None, 10, 5, 15, None, None, 11, 22])) 
10 
(l) 5 
(r) 15 
(l)  11 
(r)  22

來源

2017-02-03 00:35:25 Blckknght

如何將平面列表轉換爲二進制樹

回答

相關問題