如何在Python中实现通用树?这有内置的数据结构吗?
当前回答
另一个基于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
其他回答
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]
泛型树是一个具有零个或多个子节点的节点,每个子节点都是一个合适的(树)节点。它与二叉树不同,它们是不同的数据结构,尽管它们都有一些相同的术语。
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')])])
我推荐任何树(我是作者)。
例子:
from anytree import Node, RenderTree
udo = Node("Udo")
marc = Node("Marc", parent=udo)
lian = Node("Lian", parent=marc)
dan = Node("Dan", parent=udo)
jet = Node("Jet", parent=dan)
jan = Node("Jan", parent=dan)
joe = Node("Joe", parent=dan)
print(udo)
Node('/Udo')
print(joe)
Node('/Udo/Dan/Joe')
for pre, fill, node in RenderTree(udo):
print("%s%s" % (pre, node.name))
Udo
├── Marc
│ └── Lian
└── Dan
├── Jet
├── Jan
└── Joe
print(dan.children)
(Node('/Udo/Dan/Jet'), Node('/Udo/Dan/Jan'), Node('/Udo/Dan/Joe'))
anytree也有一个强大的API:
简单的树创建 简单树修改 预序树迭代 后序树迭代 解析相对节点路径和绝对节点路径 从一个节点移动到另一个节点。 树渲染(参见上面的例子) 节点连接/分离连接
并没有内置树,但是可以通过从List继承Node类型并编写遍历方法来轻松地构造一个树。如果你这样做,我发现平分法很有用。
您还可以浏览PyPi上的许多实现。
如果我没记错的话,Python标准库不包含树数据结构,原因和。net基类库不包含树数据结构是一样的:内存的局部性降低了,导致缓存丢失更多。在现代处理器上,将大量内存放入缓存通常会更快,而“指针丰富”的数据结构会抵消这种好处。
你可以试试:
from collections import defaultdict
def tree(): return defaultdict(tree)
users = tree()
users['harold']['username'] = 'hrldcpr'
users['handler']['username'] = 'matthandlersux'
建议在这里:https://gist.github.com/2012250
推荐文章
- 插入一行到熊猫数据框架
- 要列出Pandas DataFrame列
- 在Django模型中存储电话号码的最佳方法是什么?
- 从导入的模块中模拟函数
- 滚动或滑动窗口迭代器?
- python的方法找到最大值和它的索引在一个列表?
- 如何读取文件的前N行?
- 如何删除matplotlib中的顶部和右侧轴?
- 解析.py文件,读取AST,修改它,然后写回修改后的源代码
- Visual Studio Code:如何调试Python脚本的参数
- 使用元组/列表等等。从输入vs直接引用类型如list/tuple/etc
- 结合conda环境。Yml和PIP requirements.txt
- 将命名元组转换为字典
- 如何使x轴和y轴的刻度相等呢?
- Numpy在这里函数多个条件