如何在Python中实现通用树?这有内置的数据结构吗?
当前回答
你可以试试:
from collections import defaultdict
def tree(): return defaultdict(tree)
users = tree()
users['harold']['username'] = 'hrldcpr'
users['handler']['username'] = 'matthandlersux'
建议在这里:https://gist.github.com/2012250
其他回答
您可以使用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 ->
嗨，你可以试试itertree(我是作者)。
该包与任何树包的方向相同，但关注点略有不同。在巨大的树(>100000个项目)上的性能要好得多，它处理迭代器具有有效的过滤机制。
>>>from itertree import *
>>>root=iTree('root')
>>># add some children:
>>>root.append(iTree('Africa',data={'surface':30200000,'inhabitants':1257000000}))
>>>root.append(iTree('Asia', data={'surface': 44600000, 'inhabitants': 4000000000}))
>>>root.append(iTree('America', data={'surface': 42549000, 'inhabitants': 1009000000}))
>>>root.append(iTree('Australia&Oceania', data={'surface': 8600000, 'inhabitants': 36000000}))
>>>root.append(iTree('Europe', data={'surface': 10523000 , 'inhabitants': 746000000}))
>>># you might use __iadd__ operator for adding too:
>>>root+=iTree('Antarktika', data={'surface': 14000000, 'inhabitants': 1100})
>>># for building next level we select per index:
>>>root[0]+=iTree('Ghana',data={'surface':238537,'inhabitants':30950000})
>>>root[0]+=iTree('Niger', data={'surface': 1267000, 'inhabitants': 23300000})
>>>root[1]+=iTree('China', data={'surface': 9596961, 'inhabitants': 1411780000})
>>>root[1]+=iTree('India', data={'surface': 3287263, 'inhabitants': 1380004000})
>>>root[2]+=iTree('Canada', data={'type': 'country', 'surface': 9984670, 'inhabitants': 38008005})
>>>root[2]+=iTree('Mexico', data={'surface': 1972550, 'inhabitants': 127600000 })
>>># extend multiple items:
>>>root[3].extend([iTree('Australia', data={'surface': 7688287, 'inhabitants': 25700000 }), iTree('New Zealand', data={'surface': 269652, 'inhabitants': 4900000 })])
>>>root[4]+=iTree('France', data={'surface': 632733, 'inhabitants': 67400000 }))
>>># select parent per TagIdx - remember in itertree you might put items with same tag multiple times:
>>>root[TagIdx('Europe'0)]+=iTree('Finland', data={'surface': 338465, 'inhabitants': 5536146 })
创建的树可以被渲染:
>>>root.render()
iTree('root')
└──iTree('Africa', data=iTData({'surface': 30200000, 'inhabitants': 1257000000}))
└──iTree('Ghana', data=iTData({'surface': 238537, 'inhabitants': 30950000}))
└──iTree('Niger', data=iTData({'surface': 1267000, 'inhabitants': 23300000}))
└──iTree('Asia', data=iTData({'surface': 44600000, 'inhabitants': 4000000000}))
└──iTree('China', data=iTData({'surface': 9596961, 'inhabitants': 1411780000}))
└──iTree('India', data=iTData({'surface': 3287263, 'inhabitants': 1380004000}))
└──iTree('America', data=iTData({'surface': 42549000, 'inhabitants': 1009000000}))
└──iTree('Canada', data=iTData({'surface': 9984670, 'inhabitants': 38008005}))
└──iTree('Mexico', data=iTData({'surface': 1972550, 'inhabitants': 127600000}))
└──iTree('Australia&Oceania', data=iTData({'surface': 8600000, 'inhabitants': 36000000}))
└──iTree('Australia', data=iTData({'surface': 7688287, 'inhabitants': 25700000}))
└──iTree('New Zealand', data=iTData({'surface': 269652, 'inhabitants': 4900000}))
└──iTree('Europe', data=iTData({'surface': 10523000, 'inhabitants': 746000000}))
└──iTree('France', data=iTData({'surface': 632733, 'inhabitants': 67400000}))
└──iTree('Finland', data=iTData({'surface': 338465, 'inhabitants': 5536146}))
└──iTree('Antarktika', data=iTData({'surface': 14000000, 'inhabitants': 1100}))
过滤可以这样做:
>>>item_filter = Filter.iTFilterData(data_key='inhabitants', data_value=iTInterval(0, 20000000))
>>>iterator=root.iter_all(item_filter=item_filter)
>>>for i in iterator:
>>> print(i)
iTree("'New Zealand'", data=iTData({'surface': 269652, 'inhabitants': 4900000}), subtree=[])
iTree("'Finland'", data=iTData({'surface': 338465, 'inhabitants': 5536146}), subtree=[])
iTree("'Antarktika'", data=iTData({'surface': 14000000, 'inhabitants': 1100}), subtree=[])
class Node:
"""
Class Node
"""
def __init__(self, value):
self.left = None
self.data = value
self.right = None
class Tree:
"""
Class tree will provide a tree as well as utility functions.
"""
def createNode(self, data):
"""
Utility function to create a node.
"""
return Node(data)
def insert(self, node , data):
"""
Insert function will insert a node into tree.
Duplicate keys are not allowed.
"""
#if tree is empty , return a root node
if node is None:
return self.createNode(data)
# if data is smaller than parent , insert it into left side
if data < node.data:
node.left = self.insert(node.left, data)
elif data > node.data:
node.right = self.insert(node.right, data)
return node
def search(self, node, data):
"""
Search function will search a node into tree.
"""
# if root is None or root is the search data.
if node is None or node.data == data:
return node
if node.data < data:
return self.search(node.right, data)
else:
return self.search(node.left, data)
def deleteNode(self,node,data):
"""
Delete function will delete a node into tree.
Not complete , may need some more scenarion that we can handle
Now it is handling only leaf.
"""
# Check if tree is empty.
if node is None:
return None
# searching key into BST.
if data < node.data:
node.left = self.deleteNode(node.left, data)
elif data > node.data:
node.right = self.deleteNode(node.right, data)
else: # reach to the node that need to delete from BST.
if node.left is None and node.right is None:
del node
if node.left == None:
temp = node.right
del node
return temp
elif node.right == None:
temp = node.left
del node
return temp
return node
def traverseInorder(self, root):
"""
traverse function will print all the node in the tree.
"""
if root is not None:
self.traverseInorder(root.left)
print(root.data)
self.traverseInorder(root.right)
def traversePreorder(self, root):
"""
traverse function will print all the node in the tree.
"""
if root is not None:
print(root.data)
self.traversePreorder(root.left)
self.traversePreorder(root.right)
def traversePostorder(self, root):
"""
traverse function will print all the node in the tree.
"""
if root is not None:
self.traversePostorder(root.left)
self.traversePostorder(root.right)
print(root.data)
def main():
root = None
tree = Tree()
root = tree.insert(root, 10)
print(root)
tree.insert(root, 20)
tree.insert(root, 30)
tree.insert(root, 40)
tree.insert(root, 70)
tree.insert(root, 60)
tree.insert(root, 80)
print("Traverse Inorder")
tree.traverseInorder(root)
print("Traverse Preorder")
tree.traversePreorder(root)
print("Traverse Postorder")
tree.traversePostorder(root)
if __name__ == "__main__":
main()
我将根树实现为字典{child:parent}。比如根节点为0，树可能是这样的:
tree={1:0, 2:0, 3:1, 4:2, 5:3}
这种结构使得沿着一条路径从任意节点向上到根结点非常容易，这与我正在处理的问题有关。
另一个基于Bruno回答的树的实现:
class Node:
def __init__(self):
self.name: str = ''
self.children: List[Node] = []
self.parent: Node = self
def __getitem__(self, i: int) -> 'Node':
return self.children[i]
def add_child(self):
child = Node()
self.children.append(child)
child.parent = self
return child
def __str__(self) -> str:
def _get_character(x, left, right) -> str:
if x < left:
return '/'
elif x >= right:
return '\\'
else:
return '|'
if len(self.children):
children_lines: Sequence[List[str]] = list(map(lambda child: str(child).split('\n'), self.children))
widths: Sequence[int] = list(map(lambda child_lines: len(child_lines[0]), children_lines))
max_height: int = max(map(len, children_lines))
total_width: int = sum(widths) + len(widths) - 1
left: int = (total_width - len(self.name) + 1) // 2
right: int = left + len(self.name)
return '\n'.join((
self.name.center(total_width),
' '.join(map(lambda width, position: _get_character(position - width // 2, left, right).center(width),
widths, accumulate(widths, add))),
*map(
lambda row: ' '.join(map(
lambda child_lines: child_lines[row] if row < len(child_lines) else ' ' * len(child_lines[0]),
children_lines)),
range(max_height))))
else:
return self.name
还有一个如何使用它的例子:
tree = Node()
tree.name = 'Root node'
tree.add_child()
tree[0].name = 'Child node 0'
tree.add_child()
tree[1].name = 'Child node 1'
tree.add_child()
tree[2].name = 'Child node 2'
tree[1].add_child()
tree[1][0].name = 'Grandchild 1.0'
tree[2].add_child()
tree[2][0].name = 'Grandchild 2.0'
tree[2].add_child()
tree[2][1].name = 'Grandchild 2.1'
print(tree)
它应该输出:
Root node
/ / \
Child node 0 Child node 1 Child node 2
| / \
Grandchild 1.0 Grandchild 2.0 Grandchild 2.1
推荐文章
- 证书验证失败:无法获得本地颁发者证书
- 当使用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中获得所有直接子目录
