如何在Python中实现通用树?这有内置的数据结构吗?
当前回答
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方法仍然适用。
其他回答
泛型树是一个具有零个或多个子节点的节点,每个子节点都是一个合适的(树)节点。它与二叉树不同,它们是不同的数据结构,尽管它们都有一些相同的术语。
Python中没有任何用于泛型树的内置数据结构,但很容易通过类实现。
class Tree(object):
"Generic tree node."
def __init__(self, name='root', children=None):
self.name = name
self.children = []
if children is not None:
for child in children:
self.add_child(child)
def __repr__(self):
return self.name
def add_child(self, node):
assert isinstance(node, Tree)
self.children.append(node)
# *
# /|\
# 1 2 +
# / \
# 3 4
t = Tree('*', [Tree('1'),
Tree('2'),
Tree('+', [Tree('3'),
Tree('4')])])
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方法仍然适用。
您可以使用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 ->
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]
你可以试试:
from collections import defaultdict
def tree(): return defaultdict(tree)
users = tree()
users['harold']['username'] = 'hrldcpr'
users['handler']['username'] = 'matthandlersux'
建议在这里:https://gist.github.com/2012250
推荐文章
- 在每个列表元素上调用int()函数?
- 当使用代码存储库时,如何引用资源的相对路径
- 如何在Flask-SQLAlchemy中按id删除记录
- 在Python中插入列表的第一个位置
- 在javascript中从平面数组构建树数组
- Python Pandas只合并某些列
- 如何在一行中连接两个集而不使用“|”
- 从字符串中移除前缀
- 代码结束时发出警报
- 如何在Python中按字母顺序排序字符串中的字母
- 在matplotlib中将y轴标签添加到次要y轴
- 如何消除数独方块的凹凸缺陷?
- 为什么出现这个UnboundLocalError(闭包)?
- 使用Python请求的异步请求
- 如何检查一个对象是否是python中的生成器对象?