如何在Python中实现通用树?这有内置的数据结构吗?
当前回答
您可以使用Python中的dataclasses模块创建Tree数据结构。
iter方法可用于使树可迭代,允许您通过改变yield语句的顺序来遍历树。
contains方法可用于检查树中是否存在特定值。
from dataclasses import dataclass
# A
# / \
# B C
# / \ \
# D E F
# / \
# G H
@dataclass
class Node:
data: str
left: Node = None
right: Node = None
def __iter__(self):
if self.left:
yield from self.left
yield self
if self.right:
yield from self.right
def __contains__(self, other):
for node in self:
if node.data == other:
return True
return False
t = Node(
'A',
Node(
'B',
Node(
'D',
Node('G'),
Node('H'),
),
Node('E'),
),
Node(
'C',
right=Node('F'),
),
)
assert ('A' in t) is True
assert ('I' in t) is not True
for node in t:
print(node.data, ' -> ', end='')
# G -> D -> H -> B -> E -> A -> C -> F ->
其他回答
并没有内置树,但是可以通过从List继承Node类型并编写遍历方法来轻松地构造一个树。如果你这样做,我发现平分法很有用。
您还可以浏览PyPi上的许多实现。
如果我没记错的话,Python标准库不包含树数据结构,原因和。net基类库不包含树数据结构是一样的:内存的局部性降低了,导致缓存丢失更多。在现代处理器上,将大量内存放入缓存通常会更快,而“指针丰富”的数据结构会抵消这种好处。
如果有人需要一个更简单的方法,树只是一个递归嵌套的列表(因为set是不可哈希的):
[root, [child_1, [[child_11, []], [child_12, []]], [child_2, []]]]
每个分支都是一对:[object, [children]] 每个叶子是一对:[object, []]
但是如果你需要一个带有方法的类,你可以使用任何树。
如果您已经在使用networkx库,那么您可以使用它实现一个树。
NetworkX是一个用于创建、操作和研究的Python包 复杂网络的结构、动力学和功能。
因为“树”是(通常根)连接无环图的另一个术语,这些在NetworkX中被称为“树状图”。
你可能想要实现一个平面树(又名有序树),其中每个兄弟姐妹都有一个唯一的秩,这通常通过标记节点来完成。
然而,图语言看起来不同于树语言,“扎根”树的方法通常是使用有向图,因此,虽然有一些非常酷的功能和相应的可视化可用,但如果你还没有使用networkx,它可能不是一个理想的选择。
一个构建树的例子:
import networkx as nx
G = nx.Graph()
G.add_edge('A', 'B')
G.add_edge('B', 'C')
G.add_edge('B', 'D')
G.add_edge('A', 'E')
G.add_edge('E', 'F')
该库允许每个节点是任何可哈希对象,并且不限制每个节点拥有的子节点的数量。
Python不像Java那样具有相当广泛的“内置”数据结构。但是,因为Python是动态的,所以很容易创建通用树。例如,二叉树可能是:
class Tree:
def __init__(self):
self.left = None
self.right = None
self.data = None
你可以这样使用它:
root = Tree()
root.data = "root"
root.left = Tree()
root.left.data = "left"
root.right = Tree()
root.right.data = "right"
如果每个节点需要任意数量的子节点,则使用子节点列表:
class Tree:
def __init__(self, data):
self.children = []
self.data = data
left = Tree("left")
middle = Tree("middle")
right = Tree("right")
root = Tree("root")
root.children = [left, middle, right]
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的创造者;)
推荐文章
- 证书验证失败:无法获得本地颁发者证书
- 当使用pip3安装包时,“Python中的ssl模块不可用”
- 无法切换Python与pyenv
- Python if not == vs if !=
- 如何从scikit-learn决策树中提取决策规则?
- 为什么在Mac OS X v10.9 (Mavericks)的终端中apt-get功能不起作用?
- 将旋转的xtick标签与各自的xtick对齐
- 为什么元组可以包含可变项?
- 如何合并字典的字典?
- 如何创建类属性?
- 不区分大小写的“in”
- 在Python中获取迭代器中的元素个数
- 解析日期字符串并更改格式
- 使用try和。Python中的if
- 如何在Python中获得所有直接子目录