將輸入列表映射到最低級別的嵌套列表

我有一個Python類，它存儲了更多類型的本身，作爲鋸齒狀的樹結構。最高層和中間層不存儲任何數據，但最低層不會。我有一個列表，例如[8, 2, 5, 3]，我想將每個值分配給樹中最低級別的相應插槽： tree 每個節點可以有不同數量的連接向下，並且可以有任意數量的層。我的問題是，我不能使用類似問題中提供的traverse函數，因爲我正在分配多個值，並且我無法輕鬆獲得底部每個值的索引。這裏是節點類別：將輸入列表映射到最低級別的嵌套列表

class Node(object): 
     def __init__(self, branches): 
      self.branches = branches # This is a list of Node objects 
      self.value = 0

分支列表包含更多節點，其中有節點列表本身。該值默認爲0，但如前所述，稍後將有一個列表映射到它們。下面是如何創建一個樹一個例子，我想做什麼：

tree = Node([ 
     Node([ 
      Node([ 
       None # This node's value is 1 
      ]), 
      Node([ 
       None # This node's value is 2 
      ]) 
     ]), 

     Node([ 
      Node([ 
       None # This node's value is 3 
      ]), 
      Node([ 
       None # This node's value is 4 
      ]) 
     ]) 
    ]) 

    tree.set_inputs([1, 2, 3, 4]) # See above comments, this is what I want

我怎樣才能做到這一點？我的唯一的想法是遞歸函數，輪流對輸入的索引成二進制（這基於分支的數目可以改變）數目如0100110確定由索引及其分支採取在每一遞歸的方向：

# In the example above: b0 -> b1 -> b0 -> b0 -> b1 -> b1 -> b0.

如果這是解決這個問題的方法，我需要一些幫助來實現它。否則，任何有關我的問題的幫助表示讚賞。

來源

2015-06-28 pengowen123

有很多問題需要得到回答之前，我們可以提供幫助的問題。你的代碼是什麼樣的？節點的孩子是否有序？您爲葉節點賦值的順序很重要，還是僅僅分配了每個值？ – jme

感謝您的建議，對不起，我忘了代碼示例。我已經編輯了這個問題來包含一個。另外，順序很重要。從左到右或從右到左是無關緊要的，只是它保持一致。 – pengowen123

深度優先搜索可以按照從左到右或從右到左的順序生成樹的葉節點，這取決於它如何實現。首先，我要添加一個name屬性和__repr__您Node，使之更容易看到發生了什麼：

class Node(object): 
    def __init__(self, name, branches): 
     self.branches = branches # This is a list of Node objects 
     self.value = 0 
     self.name = name 

    def __repr__(self): 
     return '<Node {}>'.format(self.name)

現在，我們將定義兩個函數。首先在深度優先搜索中產生節點：

from collections import deque 

def dfs(root): 
    stack = deque([root]) 
    while stack: 
     node = stack.pop() 
     yield node 
     if node.branches is not None: 
      for child in reversed(node.branches): 
       stack.append(child)

請注意關於此代碼的一些事情。首先，我們遍歷節點的子節點reversed。這導致葉子從左到右產生。如果我們刪除reversed，葉子將從右到左迭代。另外，請注意，也許一個沒有任何孩子的葉子節點的更清晰的表示是將空的可迭代元素（如空元組）分配給node.branches。然後可以完全刪除node.branches is not None檢查。

以上代碼當然會生成所有節點。我們只想要樹葉：

def leaves(root): 
    for node in dfs(root): 
     if node.branches is None: 
      yield node

讓我們來測試一下。這裏有一個簡單的樹：

#  g 
# /\ 
# / \ 
# e  f 
# /\ /\ 
# a b c d 

a, b, c, d = [Node(name, None) for name in 'abcd'] 
e = Node('e', (a,b)) 
f = Node('f', (c,d)) 
g = Node('g', (e,f))

而且我們列出的葉子：

>>> list(leaves(g)) 
[<Node a>, <Node b>, <Node c>, <Node d>]

注意，他們是爲了自左到右。現在分配值很簡單：

values = [1, 2, 3, 4] 
for leaf, value in zip(leaves(g), values): 
    leaf.value = value

這樣：

for node in (a, b, c, d): 
    print(node.name, node.value)

給出：

a 1 
b 2 
c 3 
d 4

來源

2015-06-29 05:49:38 jme

將輸入列表映射到最低級別的嵌套列表

回答

相關問題