考慮到我有：名為的相鄰鍵（子級 - 父級）列表ATree一個名為存儲其自己的節點鍵（整數）和子節點（類）的樹類A = [(61, 66), (50, 61), (68, 61), (33, 61), (57, 66), (72, 66), (37, 68), (71, 33), (6, 50), (11, 37), (5, 37)]class Tree: def __init__(self, node, *children): self.node = node if children: self.children = children else: self.children = [] def __str__(self): return "%s" % (self.node) def __repr__(self): return "%s" % (self.node) def __getitem__(self, k): if isinstance(k, int) or isinstance(k, slice): return self.children[k] if isinstance(k, str): for child in self.children: if child.node == k: return child def __iter__(self): return self.children.__iter__() def __len__(self): return len(self.children)如何構建一個 Tree 對象，使其根據鄰接關系封裝所有內部樹？（如下所示）t = Tree(66, Tree(72), Tree(57), Tree(61, Tree(33, Tree(71)), Tree(50, Tree(6)), Tree(68, Tree(37, Tree(11), Tree(5)))))我正在考慮以遞歸方式創建樹，但我不知道如何正確遍歷和填充它。這是我失敗的嘗試：from collections import defaultdict# Create a dictionary: key = parent, values = childrend = defaultdict(list)for child, parent in A: d[parent].append(child)# Failed attemptdef build_tree(k): if k in d: tree = Tree(k, d[k]) #1st issue: should input a Tree() as 2nd parameter for child in d[k]: build_tree(child) #2nd issue: should populate tree, not iterate recursively over children keys#I know that the root node is 66.full_tree = build_tree(66)
3 回答
慕桂英546537
TA貢獻1848條經驗 獲得超10個贊
您在這段代碼中提到了兩個問題：
tree = Tree(k, d[k]) #1st issue: should input a Tree() as 2nd parameter for child in d[k]: build_tree(child) #2nd issue: should populate tree, not iterate recursively over children keys
您可以通過本質上將for循環移至第二個參數來解決它們，以列表理解的形式并潑濺該列表，使它們成為參數。然后確保您的遞歸函數返回創建的樹：
return Tree(k, *[build_tree(child) for child in d[k]] )
更多想法
與您的問題無關，但這里還有一些您可以使用的想法。
建議您的代碼成為一個可以作為
A參數傳遞給的函數，這樣字典的作用域就只是該函數的本地作用域，而不會影響全局作用域。由于此功能與類密切相關
Tree，因此最好將其定義為類中的靜態方法或類方法。當您擁有樹的（子、父）元組時，這些元組隱式定義哪個節點是根，因此您可以省略將文字 66 傳遞給函數。該函數應該能夠自行找出哪個是根。在創建字典時，它還可以收集哪些節點有父節點。根就是不在該集合中的節點。
所以把所有這些放在一起你會得到這個：
from collections import defaultdict
class Tree:
def __init__(self, node, *children):
self.node = node
self.children = children if children else []
def __str__(self):
return "%s" % (self.node)
def __repr__(self):
return "%s" % (self.node)
def __getitem__(self, k):
if isinstance(k, int) or isinstance(k, slice):
return self.children[k]
if isinstance(k, str):
for child in self.children:
if child.node == k:
return child
def __iter__(self):
return self.children.__iter__()
def __len__(self):
return len(self.children)
@classmethod
def from_pairs(Cls, pairs):
# Turn pairs into nested dictionary
d = defaultdict(list)
children = set()
for child, parent in pairs:
d[parent].append(child)
# collect nodes that have a parent
children.add(child)
# Find root: it does not have a parent
root = next(parent for parent in d if parent not in children)
# Build nested Tree instances recursively from the dictionary
def subtree(k):
return Cls(k, *[subtree(child) for child in d[k]])
return subtree(root)
# Sample run
A = [(61, 66), (50, 61), (68, 61), (33, 61), (57, 66), (72, 66), (37, 68), (71, 33), (6, 50), (11, 37), (5, 37)]
tree = Tree.from_pairs(A)
開滿天機
TA貢獻1786條經驗 獲得超13個贊
你很接近了。關鍵是將新節點返回給父節點并將其追加到父節點的子節點列表中。如果您的父級列表在初始化時是固定的，只需使用臨時列表，然后在訪問并創建子級后創建父級。
這是一個最小的例子：
from collections import defaultdict, namedtuple
def build_tree(tree, root):
if root:
return Node(root, [build_tree(tree, x) for x in tree.get(root, [])])
def print_tree(root, indent=0):
if root:
print(" " * indent + str(root.val))
for child in root.children:
print_tree(child, indent + 2)
if __name__ == "__main__":
A = [(61, 66), (50, 61), (68, 61), (33, 61), (57, 66), (72, 66),
(37, 68), (71, 33), (6, 50), (11, 37), (5, 37)]
Node = namedtuple("Node", "val children")
nodes = defaultdict(list)
for child, parent in A:
nodes[parent].append(child)
print_tree(build_tree(nodes, 66))
輸出：
66
61
50
6
68
37
11
5
33
71
57
72
萬千封印
TA貢獻1891條經驗 獲得超3個贊
這是了解可重用模塊和相互遞歸的機會。
首先，我們將定義特定于(id, parent)輸入結構形狀的函數 -
# main.py
def id(node):
? return node[0]
def parent(node):
? return node[1]
n = (12,34)
id(n)? ? ?# => 12
parent(n) # => 34
也許你知道根節點是66，但這對我們的程序來說很難推斷，但對我們來說很容易定義。讓我們明確地包含(66, None)在您的輸入數據中，其中parent=None表示根節點-
A = \
? [ (61, 66), (50, 61), (68, 61), (33, 61)
? , (57, 66), (72, 66), (37, 68), (71, 33)
? , (6, 50), (11, 37), (5, 37), (66, None) # don't forget root node, 66
? ]
現在我們可以使用該tree模塊輕松構建我們的樹 -
# main.py
from tree import tree
def id #...
def parent #...
A = [ ... ]
B = tree \
? ( A? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? # list of nodes
? , parent? ? ? ? ? ? ? ? ? ? ? ? ? ?# foreign key
? , lambda node, children:? ? ? ? ? ?# node reconstructor
? ? ? (id(node), children(id(node))) # primary key?
? )
print(B)
# [(66, [(61, [(50, [(6, [])]), (68, [(37, [(11, []), (5, [])])]), (33, [(71, [])])]), (57, []), (72, [])])]
請注意，如何tree不關心輸入的形狀；可以使用任何節點結構。該tree功能很靈活，允許我們構造與輸入節點完全不同的形狀的樹節點 -
# main.py
from tree import tree
from json import dumps
def id #...
def parent #...
A = [ ... ]
C = tree \
? ( A
? , parent
? , lambda node, children:
? ? ? dict([("id", id(node)), ("children", children(id(node)))])
? )
print(dumps(C))
[ { "id": 66
? , "children":
? ? ? [ { "id": 61
? ? ? ? , "children":
? ? ? ? ? ? [ { "id": 50
? ? ? ? ? ? ? , "children":
? ? ? ? ? ? ? ? ? [ { "id": 6, "children": [] }
? ? ? ? ? ? ? ? ? ]
? ? ? ? ? ? ? }
? ? ? ? ? ? , { "id": 68
? ? ? ? ? ? ? , "children":
? ? ? ? ? ? ? ? [ { "id": 37
? ? ? ? ? ? ? ? ? , "children":
? ? ? ? ? ? ? ? ? ? ? [ { "id": 11, "children": [] }
? ? ? ? ? ? ? ? ? ? ? , { "id": 5, "children": [] }
? ? ? ? ? ? ? ? ? ? ? ]
? ? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? ]
? ? ? ? ? ? ? }
? ? ? ? ? ? , { "id": 33
? ? ? ? ? ? ? , "children":
? ? ? ? ? ? ? ? ? [ { "id": 71, "children": [] }
? ? ? ? ? ? ? ? ? ]
? ? ? ? ? ? ? }
? ? ? ? ? ? ]
? ? ? ? }
? ? ? , { "id": 57, "children": [] }
? ? ? , { "id": 72, "children": [] }
? ? ? ]
? }
]
現在我們可以看看 的實現tree。請注意如何tree不對輸入節點的形狀做出任何假設 -
# tree.py
from index import index, get
def empty():
? return []
def tree (all, indexer, maker, root = None):
? mem = index(all, indexer)
? def many(all):
? ? return list(map(one, all))
??
? def one(single):
? ? return maker(single, lambda r: many(get(mem, r, empty())))
??
? return many(get(mem, root))
我們的實現tree依賴于另一個模塊，index. 將數據結構（例如索引）以及對這些數據結構進行操作的函數進行分組是在模塊之間劃定界限的好方法。這里也沒有對輸入形狀做出任何假設 -
# index.py
from functools import reduce
def empty():
? return {}
def update(t, k, f):
? if k in t:
? ? return { **t, k: f(get(t, k)) }
? else:
? ? return { **t, k: f() }
def get(t, k, default = None):
? if k in t:
? ? return t[k]
? else:
? ? return default
def append(t, k, v):
? return update(t, k, lambda r = []: [ *r, v ])
def index(ls, indexer):
? return reduce \
? ? ( lambda t, v: append(t, indexer(v), v)
? ? , ls
? ? , empty()
? ? )
通過在瀏覽器中運行來驗證我們的結果：run this program on repl.it
添加回答
舉報
0/150
提交
取消