考慮到我有：名為的相鄰鍵（子級(jí) - 父級(jí)）列表ATree一個(gè)名為存儲(chǔ)其自己的節(jié)點(diǎn)鍵（整數(shù)）和子節(jié)點(diǎn)（類(lèi)）的樹(shù)類(lèi)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)如何構(gòu)建一個(gè) Tree 對(duì)象，使其根據(jù)鄰接關(guān)系封裝所有內(nèi)部樹(shù)？（如下所示）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)))))我正在考慮以遞歸方式創(chuàng)建樹(shù)，但我不知道如何正確遍歷和填充它。這是我失敗的嘗試：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貢獻(xiàn)1848條經(jīng)驗(yàn) 獲得超10個(gè)贊
您在這段代碼中提到了兩個(gè)問(wèn)題：
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
您可以通過(guò)本質(zhì)上將for循環(huán)移至第二個(gè)參數(shù)來(lái)解決它們，以列表理解的形式并潑濺該列表，使它們成為參數(shù)。然后確保您的遞歸函數(shù)返回創(chuàng)建的樹(shù)：
return Tree(k, *[build_tree(child) for child in d[k]] )
更多想法
與您的問(wèn)題無(wú)關(guān)，但這里還有一些您可以使用的想法。
建議您的代碼成為一個(gè)可以作為
A參數(shù)傳遞給的函數(shù)，這樣字典的作用域就只是該函數(shù)的本地作用域，而不會(huì)影響全局作用域。由于此功能與類(lèi)密切相關(guān)
Tree，因此最好將其定義為類(lèi)中的靜態(tài)方法或類(lèi)方法。當(dāng)您擁有樹(shù)的（子、父）元組時(shí)，這些元組隱式定義哪個(gè)節(jié)點(diǎn)是根，因此您可以省略將文字 66 傳遞給函數(shù)。該函數(shù)應(yīng)該能夠自行找出哪個(gè)是根。在創(chuàng)建字典時(shí)，它還可以收集哪些節(jié)點(diǎn)有父節(jié)點(diǎn)。根就是不在該集合中的節(jié)點(diǎn)。
所以把所有這些放在一起你會(huì)得到這個(gè)：
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)
開(kāi)滿(mǎn)天機(jī)
TA貢獻(xiàn)1786條經(jīng)驗(yàn) 獲得超13個(gè)贊
你很接近了。關(guān)鍵是將新節(jié)點(diǎn)返回給父節(jié)點(diǎn)并將其追加到父節(jié)點(diǎn)的子節(jié)點(diǎn)列表中。如果您的父級(jí)列表在初始化時(shí)是固定的，只需使用臨時(shí)列表，然后在訪問(wèn)并創(chuàng)建子級(jí)后創(chuàng)建父級(jí)。
這是一個(gè)最小的例子：
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
萬(wàn)千封印
TA貢獻(xiàn)1891條經(jīng)驗(yàn) 獲得超3個(gè)贊
這是了解可重用模塊和相互遞歸的機(jī)會(huì)。
首先，我們將定義特定于(id, parent)輸入結(jié)構(gòu)形狀的函數(shù) -
# main.py
def id(node):
? return node[0]
def parent(node):
? return node[1]
n = (12,34)
id(n)? ? ?# => 12
parent(n) # => 34
也許你知道根節(jié)點(diǎn)是66，但這對(duì)我們的程序來(lái)說(shuō)很難推斷，但對(duì)我們來(lái)說(shuō)很容易定義。讓我們明確地包含(66, None)在您的輸入數(shù)據(jù)中，其中parent=None表示根節(jié)點(diǎn)-
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
? ]
現(xiàn)在我們可以使用該tree模塊輕松構(gòu)建我們的樹(shù) -
# 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, [])])]
請(qǐng)注意，如何tree不關(guān)心輸入的形狀；可以使用任何節(jié)點(diǎn)結(jié)構(gòu)。該tree功能很靈活，允許我們構(gòu)造與輸入節(jié)點(diǎn)完全不同的形狀的樹(shù)節(jié)點(diǎn) -
# 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": [] }
? ? ? ]
? }
]
現(xiàn)在我們可以看看 的實(shí)現(xiàn)tree。請(qǐng)注意如何tree不對(duì)輸入節(jié)點(diǎn)的形狀做出任何假設(shè) -
# 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))
我們的實(shí)現(xiàn)tree依賴(lài)于另一個(gè)模塊，index. 將數(shù)據(jù)結(jié)構(gòu)（例如索引）以及對(duì)這些數(shù)據(jù)結(jié)構(gòu)進(jìn)行操作的函數(shù)進(jìn)行分組是在模塊之間劃定界限的好方法。這里也沒(méi)有對(duì)輸入形狀做出任何假設(shè) -
# 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()
? ? )
通過(guò)在瀏覽器中運(yùn)行來(lái)驗(yàn)證我們的結(jié)果：run this program on repl.it
添加回答
舉報(bào)
0/150
提交
取消