如何在Python中实现通用树?这有内置的数据结构吗?
当前回答
我使用嵌套字典实现了树。这很容易做到,而且对我来说,它在相当大的数据集上很有效。我在下面发布了一个示例,你可以在谷歌代码中看到更多
def addBallotToTree(self, tree, ballotIndex, ballot=""):
"""Add one ballot to the tree.
The root of the tree is a dictionary that has as keys the indicies of all
continuing and winning candidates. For each candidate, the value is also
a dictionary, and the keys of that dictionary include "n" and "bi".
tree[c]["n"] is the number of ballots that rank candidate c first.
tree[c]["bi"] is a list of ballot indices where the ballots rank c first.
If candidate c is a winning candidate, then that portion of the tree is
expanded to indicate the breakdown of the subsequently ranked candidates.
In this situation, additional keys are added to the tree[c] dictionary
corresponding to subsequently ranked candidates.
tree[c]["n"] is the number of ballots that rank candidate c first.
tree[c]["bi"] is a list of ballot indices where the ballots rank c first.
tree[c][d]["n"] is the number of ballots that rank c first and d second.
tree[c][d]["bi"] is a list of the corresponding ballot indices.
Where the second ranked candidates is also a winner, then the tree is
expanded to the next level.
Losing candidates are ignored and treated as if they do not appear on the
ballots. For example, tree[c][d]["n"] is the total number of ballots
where candidate c is the first non-losing candidate, c is a winner, and
d is the next non-losing candidate. This will include the following
ballots, where x represents a losing candidate:
[c d]
[x c d]
[c x d]
[x c x x d]
During the count, the tree is dynamically updated as candidates change
their status. The parameter "tree" to this method may be the root of the
tree or may be a sub-tree.
"""
if ballot == "":
# Add the complete ballot to the tree
weight, ballot = self.b.getWeightedBallot(ballotIndex)
else:
# When ballot is not "", we are adding a truncated ballot to the tree,
# because a higher-ranked candidate is a winner.
weight = self.b.getWeight(ballotIndex)
# Get the top choice among candidates still in the running
# Note that we can't use Ballots.getTopChoiceFromWeightedBallot since
# we are looking for the top choice over a truncated ballot.
for c in ballot:
if c in self.continuing | self.winners:
break # c is the top choice so stop
else:
c = None # no candidates left on this ballot
if c is None:
# This will happen if the ballot contains only winning and losing
# candidates. The ballot index will not need to be transferred
# again so it can be thrown away.
return
# Create space if necessary.
if not tree.has_key(c):
tree[c] = {}
tree[c]["n"] = 0
tree[c]["bi"] = []
tree[c]["n"] += weight
if c in self.winners:
# Because candidate is a winner, a portion of the ballot goes to
# the next candidate. Pass on a truncated ballot so that the same
# candidate doesn't get counted twice.
i = ballot.index(c)
ballot2 = ballot[i+1:]
self.addBallotToTree(tree[c], ballotIndex, ballot2)
else:
# Candidate is in continuing so we stop here.
tree[c]["bi"].append(ballotIndex)
其他回答
我将根树实现为字典{child:parent}。比如根节点为0,树可能是这样的:
tree={1:0, 2:0, 3:1, 4:2, 5:3}
这种结构使得沿着一条路径从任意节点向上到根结点非常容易,这与我正在处理的问题有关。
bigtree是一个Python树实现,集成了Python列表、字典和pandas DataFrame。它是python式的,易于学习,并可扩展到许多类型的工作流。
bigtree有很多组成部分,即
从列表、字典和熊猫数据框架构建树 遍历树 修改树(移位/复制节点) 搜索树 辅助方法(克隆树,修剪树,获取两个树之间的差异) 导出树(打印到控制台,导出树到字典,熊猫数据框架,图像等) 其他树结构:二叉树! 其他图结构:有向无环图(dag)!
我还能说什么呢……是的,这也是有据可查的。
一些例子:
from bigtree import list_to_tree, tree_to_dict, tree_to_dot
# Create tree from list, print tree
root = list_to_tree(["a/b/d", "a/c"])
print_tree(root)
# a
# ├── b
# │ └── d
# └── c
# Query tree
root.children
# (Node(/a/b, ), Node(/a/c, ))
# Export tree to dictionary / image
tree_to_dict(root)
# {
# '/a': {'name': 'a'},
# '/a/b': {'name': 'b'},
# '/a/b/d': {'name': 'd'},
# '/a/c': {'name': 'c'}
# }
graph = tree_to_dot(root, node_colour="gold")
graph.write_png("tree.png")
来源/免责声明:我是bigtree的创造者;)
如果有人需要一个更简单的方法,树只是一个递归嵌套的列表(因为set是不可哈希的):
[root, [child_1, [[child_11, []], [child_12, []]], [child_2, []]]]
每个分支都是一对:[object, [children]] 每个叶子是一对:[object, []]
但是如果你需要一个带有方法的类,你可以使用任何树。
class Tree(dict):
"""A tree implementation using python's autovivification feature."""
def __missing__(self, key):
value = self[key] = type(self)()
return value
#cast a (nested) dict to a (nested) Tree class
def __init__(self, data={}):
for k, data in data.items():
if isinstance(data, dict):
self[k] = type(self)(data)
else:
self[k] = data
作为一个字典,但提供尽可能多的嵌套字典。 试试下面的方法:
your_tree = Tree()
your_tree['a']['1']['x'] = '@'
your_tree['a']['1']['y'] = '#'
your_tree['a']['2']['x'] = '$'
your_tree['a']['3'] = '%'
your_tree['b'] = '*'
将传递一个嵌套的字典…就像树一样。
{'a': {'1': {'x': '@', 'y': '#'}, '2': {'x': '$'}, '3': '%'}, 'b': '*'}
... 如果你已经有字典了,它会把每一层都投射到一棵树上:
d = {'foo': {'amy': {'what': 'runs'} } }
tree = Tree(d)
print(d['foo']['amy']['what']) # returns 'runs'
d['foo']['amy']['when'] = 'now' # add new branch
这样,你就可以随心所欲地编辑/添加/删除每个词典级别。 遍历等所有dict方法仍然适用。
并没有内置树,但是可以通过从List继承Node类型并编写遍历方法来轻松地构造一个树。如果你这样做,我发现平分法很有用。
您还可以浏览PyPi上的许多实现。
如果我没记错的话,Python标准库不包含树数据结构,原因和。net基类库不包含树数据结构是一样的:内存的局部性降低了,导致缓存丢失更多。在现代处理器上,将大量内存放入缓存通常会更快,而“指针丰富”的数据结构会抵消这种好处。
推荐文章
- 如何更新SQLAlchemy行条目?
- name 'reduce'在Python中没有定义
- 如何计算一个NumPy bool数组中的真实元素的数量
- 在python中,在函数结束(例如检查失败)之前退出函数(没有返回值)的最佳方法是什么?
- 在Python中检查一个单词是否在字符串中
- Python glob多个文件类型
- 如何可靠地打开与当前运行脚本在同一目录下的文件
- Python csv字符串到数组
- 如何在Python中进行热编码?
- 如何嵌入HTML到IPython输出?
- 在Python生成器上使用“send”函数的目的是什么?
- 段树、区间树、二叉索引树和范围树之间有什么区别?
- 是否可以将已编译的.pyc文件反编译为.py文件?
- Django模型表单对象的自动创建日期
- 在Python中包装长行