如何在 Python 中实现树？
- 2025-02-28 08:23:00
- admin 原创
- 87
问题描述：
如何在 Python 中实现通用树？是否有内置数据结构？
解决方案 1：
我推荐anytree（我是作者）。
例子：
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：
简单树的创建
简单的树修改
预排序树迭代
后序树迭代
解析相对和绝对节点路径
从一个节点走到另一个节点。
树渲染（见上面的例子）
节点连接/分离连接
解决方案 2：
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]
解决方案 3：
通用树是具有零个或多个子节点的节点，每个子节点都是一个适当的（树）节点。它与二叉树不同，它们是不同的数据结构，尽管两者共享一些术语。
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)
# *
# /|\n# 1 2 +
# / \n# 3 4
t = Tree('*', [Tree('1'),
Tree('2'),
Tree('+', [Tree('3'),
Tree('4')])])
解决方案 4：
您可以尝试：
from collections import defaultdict
def tree(): return defaultdict(tree)
users = tree()
users['harold']['username'] = 'hrldcpr'
users['handler']['username'] = 'matthandlersux'
如此处建议：https://gist.github.com/2012250
解决方案 5：
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()
解决方案 6：
虽然没有内置树，但你可以通过从 List 中子类化 Node 类型并编写遍历方法轻松构建一棵树。如果你这样做，我发现bisect很有用。
PyPi上还有许多实现可供您浏览。
如果我没记错的话，Python 标准库不包含树数据结构的原因与 .NET 基类库不包含树数据结构的原因相同：内存局部性降低，导致缓存未命中次数增加。在现代处理器上，将大量内存放入缓存通常更快，而“指针丰富”的数据结构会抵消这种好处。
解决方案 7：
我将有根树实现为字典{child:parent}。例如，对于根节点0，树可能看起来像这样：
tree={1:0, 2:0, 3:1, 4:2, 5:3}
这种结构使得从任意节点到根的路径向上移动变得相当容易，这与我正在研究的问题相关。
解决方案 8：
如果有人需要一种更简单的方法来实现这一点，那么树只是一个递归嵌套的列表（因为集合不是可哈希的）：
[root, [child_1, [[child_11, []], [child_12, []]], [child_2, []]]]
每个树枝都是一对，[ object, [children] ]
每片叶子也是一对：[ object, [] ]
但是如果您需要一个具有方法的类，那么您可以使用anytree。
解决方案 9：
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
通过这种方式，您可以根据需要编辑/添加/删除每个字典级别。所有用于遍历等的字典方法仍然适用。
解决方案 10：
Greg Hewgill 的回答很棒，但如果每个级别需要更多节点，则可以使用列表|字典来创建它们：然后使用方法按名称或顺序（如 id）访问它们
class node(object):
def __init__(self):
self.name=None
self.node=[]
self.otherInfo = None
self.prev=None
def nex(self,child):
"Gets a node by number"
return self.node[child]
def prev(self):
return self.prev
def goto(self,data):
"Gets the node by name"
for child in range(0,len(self.node)):
if(self.node[child].name==data):
return self.node[child]
def add(self):
node1=node()
self.node.append(node1)
node1.prev=self
return node1
现在只需创建一个根并构建它：例如：
tree=node() #create a node
tree.name="root" #name it root
tree.otherInfo="blue" #or what ever
tree=tree.add() #add a node to the root
tree.name="node1" #name it
root
/
child1
tree=tree.add()
tree.name="grandchild1"
root
/
child1
/
grandchild1
tree=tree.prev()
tree=tree.add()
tree.name="gchild2"
root
/
child1
/ \ngrandchild1 gchild2
tree=tree.prev()
tree=tree.prev()
tree=tree.add()
tree=tree.name="child2"
root
/ \n child1 child2
/ \ngrandchild1 gchild2
tree=tree.prev()
tree=tree.goto("child1") or tree=tree.nex(0)
tree.name="changed"
root
/ \n changed child2
/ \n grandchild1 gchild2
这应该足以让你开始弄清楚如何实现这一点
解决方案 11：
我在我的网站上发布了一个 Python 3 树实现：https://web.archive.org/web/20120723175438/www.quesucede.com/page/show/id/python_3_tree_implementation
代码如下：
import uuid
def sanitize_id(id):
return id.strip().replace(" ", "")
(_ADD, _DELETE, _INSERT) = range(3)
(_ROOT, _DEPTH, _WIDTH) = range(3)
class Node:
def __init__(self, name, identifier=None, expanded=True):
self.__identifier = (str(uuid.uuid1()) if identifier is None else
sanitize_id(str(identifier)))
self.name = name
self.expanded = expanded
self.__bpointer = None
self.__fpointer = []
@property
def identifier(self):
return self.__identifier
@property
def bpointer(self):
return self.__bpointer
@bpointer.setter
def bpointer(self, value):
if value is not None:
self.__bpointer = sanitize_id(value)
@property
def fpointer(self):
return self.__fpointer
def update_fpointer(self, identifier, mode=_ADD):
if mode is _ADD:
self.__fpointer.append(sanitize_id(identifier))
elif mode is _DELETE:
self.__fpointer.remove(sanitize_id(identifier))
elif mode is _INSERT:
self.__fpointer = [sanitize_id(identifier)]
class Tree:
def __init__(self):
self.nodes = []
def get_index(self, position):
for index, node in enumerate(self.nodes):
if node.identifier == position:
break
return index
def create_node(self, name, identifier=None, parent=None):
node = Node(name, identifier)
self.nodes.append(node)
self.__update_fpointer(parent, node.identifier, _ADD)
node.bpointer = parent
return node
def show(self, position, level=_ROOT):
queue = self[position].fpointer
if level == _ROOT:
print("{0} [{1}]".format(self[position].name,
self[position].identifier))
else:
print(" "*level, "{0} [{1}]".format(self[position].name,
self[position].identifier))
if self[position].expanded:
level += 1
for element in queue:
self.show(element, level) # recursive call
def expand_tree(self, position, mode=_DEPTH):
# Python generator. Loosly based on an algorithm from 'Essential LISP' by
# John R. Anderson, Albert T. Corbett, and Brian J. Reiser, page 239-241
yield position
queue = self[position].fpointer
while queue:
yield queue[0]
expansion = self[queue[0]].fpointer
if mode is _DEPTH:
queue = expansion + queue[1:] # depth-first
elif mode is _WIDTH:
queue = queue[1:] + expansion # width-first
def is_branch(self, position):
return self[position].fpointer
def __update_fpointer(self, position, identifier, mode):
if position is None:
return
else:
self[position].update_fpointer(identifier, mode)
def __update_bpointer(self, position, identifier):
self[position].bpointer = identifier
def __getitem__(self, key):
return self.nodes[self.get_index(key)]
def __setitem__(self, key, item):
self.nodes[self.get_index(key)] = item
def __len__(self):
return len(self.nodes)
def __contains__(self, identifier):
return [node.identifier for node in self.nodes
if node.identifier is identifier]
if __name__ == "__main__":
tree = Tree()
tree.create_node("Harry", "harry") # root node
tree.create_node("Jane", "jane", parent = "harry")
tree.create_node("Bill", "bill", parent = "harry")
tree.create_node("Joe", "joe", parent = "jane")
tree.create_node("Diane", "diane", parent = "jane")
tree.create_node("George", "george", parent = "diane")
tree.create_node("Mary", "mary", parent = "diane")
tree.create_node("Jill", "jill", parent = "george")
tree.create_node("Carol", "carol", parent = "jill")
tree.create_node("Grace", "grace", parent = "bill")
tree.create_node("Mark", "mark", parent = "jane")
print("="*80)
tree.show("harry")
print("="*80)
for node in tree.expand_tree("harry", mode=_WIDTH):
print(node)
print("="*80)
解决方案 12：
我已经使用嵌套字典实现了树。这很容易做到，而且它对我处理相当大的数据集很有效。我在下面发布了一个示例，你可以在Google 代码中看到更多
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)
解决方案 13：
如果您已经在使用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')
该库使每个节点可以是任何可哈希对象，并且对每个节点的子节点数量没有限制。
解决方案 14：
bigtree是一个 Python 树实现，可与 Python 列表、字典和 pandas DataFrame 集成。它具有 Python 风格，易于学习，并且可扩展到多种类型的工作流程。
有各种组成部分bigtree，即
从列表、字典和 Pandas DataFrame构建树
遍历树
修改树（移动/复制节点）
搜索树
辅助方法（克隆树、修剪树、获取两棵树之间的差异）
导出树（打印到控制台、将树导出到字典、pandas DataFrame、图像等）
其他树结构：二叉树！
其他图形结构：有向无环图（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；）
解决方案 15：
你好，你可以尝试一下itertree (我是作者)。
该包与 anytree 包的方向一致，但重点略有不同。在大型树（>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=[])
解决方案 16：
您可以使用Python 中的dataclasses 模块创建树数据结构。
iter方法可用于使 Tree 可迭代，从而允许您通过更改 Yield 语句的顺序来遍历 Tree 。
contains方法可用于检查树中是否存在特定值。
from dataclasses import dataclass
# A
# / \n# B C
# / \n# D E F
# / \n# 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 ->
解决方案 17：
另一个树的实现大致基于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('
'), 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 '
'.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)
输出内容如下：
根节点
/ /
子节点 0 子节点 1 子节点 2
| /
孙子 1.0 孙子 2.0 孙子 2.1
解决方案 18：
Treelib 也非常适合这个任务。文档可以在treelib 中找到。
from treelib import Node, Tree
tree = Tree() # creating an object
tree.create_node("Harry", "harry") # root node
tree.create_node("Jane", "jane", parent="harry") #adding nodes
tree.create_node("Bill", "bill", parent="harry")
tree.create_node("Diane", "diane", parent="jane")
tree.create_node("Mary", "mary", parent="diane")
tree.create_node("Mark", "mark", parent="jane")
tree.show()
Harry
├── Bill
└── Jane
├── Diane
│ └── Mary
└── Mark
解决方案 19：
在 Python 中创建树的另一个示例是使用littletree（我是作者）。我最初遇到了一个问题，并使用嵌套字典解决了它。在某个时候，我想要一些更像树的东西，于是我尝试了一些树包。我发现它们中的大多数要么有点慢，要么很难扩展到我自己的问题。最终我回到了我原来的方法，并将其重构为一个新的树库。
其基本用法如下：
from littletree import Node
tree = Node(identifier="World")
tree["Asia"] = Node()
tree["Africa"] = Node()
tree["America"] = Node()
tree["Europe"] = Node()
tree.show() # Print the tree to console
tree.to_image().show() # Show tree as an image
点击此处查看其来源和更多示例。
解决方案 20：
这个问题分为两部分。
如何在 Python 中实现通用树
它有内置 DS 吗？
第二个问题似乎已被回答多次，因此我将选择第一个问题。
在 Python 中实现通用树数据结构 [N 元树]
图片来源：YouTube
我尝试实现 N 叉树结构和一些基本操作，例如，
插入
遍历/打印
搜索
from collections import deque
from typing import List, Optional
class GenericTree:
def __init__(self, data: str):
self.data = data
self.children = []
self.parent = None
def add_child(self, child: 'GenericTree') -> None:
"""
Add a child to the current node
"""
child.parent = self
self.children.append(child)
def preorder(self, node: 'GenericTree') -> List[str]:
"""
Preorder traversal of the Tree
"""
return [] if not node else [node.data] + [j for i in node.children for j in self.preorder(i)]
def postorder(self, node: 'GenericTree') -> List[str]:
"""
Postorder traversal of the Tree
"""
return [] if not node else [j for i in node.children for j in self.postorder(i)] + [node.data]
def get_level(self) -> int:
"""
Get the depth of the current node from the root
"""
level = 0
parent = self.parent
while parent:
level += 1
parent = parent.parent
return level
def level_order(self) -> List[List[str]]:
"""
Gets nodes per level/ depth from the root
"""
q = deque([self])
levels = []
while q:
level, level_size = [], len(q)
for _ in range(level_size):
current = q.popleft()
level.append(current.data)
q.extend(current.children)
if level:
levels.append(level)
return levels
def print_tree(self) -> None:
"""
Prints the tree in tree format
"""
prefix = ' ' * self.get_level() + "|__ " if self.parent else ""
print(prefix + self.data)
for child in self.children:
child.print_tree()
def dfs_search(self, key: str) -> bool:
"""
Search for a given Key in the Tree using DFS
"""
if self.data == key:
return True
for child in self.children:
if child.dfs_search(key):
return True
return False
def bfs_search(self, key: str) -> bool:
"""
Search for a node with the specified key using BFS.
"""
q = deque([self])
while q:
current = q.popleft()
if current.data == key:
return True
q.extend(current.children)
return False
def build_tree() -> GenericTree:
"""
Build a generic tree from the given data for demo
"""
tree = GenericTree('Electronics')
laptop = GenericTree('Laptops')
for item in ['iMac', 'Dell', 'PC']:
laptop.add_child(GenericTree(item))
cellphone = GenericTree('CellPhones')
for item in ['pixel', 'iphone', 'Blackberry']:
cellphone.add_child(GenericTree(item))
tv = GenericTree('TV')
for item in ['Sony', 'Samsung', 'LG']:
tv.add_child(GenericTree(item))
for item in [laptop, cellphone, tv]:
tree.add_child(item)
return tree
if __name__ == '__main__':
tree = build_tree()
print("Preorder: ", tree.preorder(tree))
print("--" * 70)
print("Postorder: ", tree.postorder(tree))
print("--" * 70)
print("Level order: ")
for level in tree.level_order():
print(level)
print("--" * 70)
print("Print Tree:")
tree.print_tree()
print("--" * 70)
for search_key in ["iphone", "tesla"]:
print(f"DFS for '{search_key}': {'FOUND' if tree.dfs_search(search_key) else 'NOT Found'}")
print("--" * 70)
for search_key in ["iphone", "tesla"]:
print(f"BFS for '{search_key}': {'FOUND' if tree.bfs_search(search_key) else 'NOT Found'}")
输出将如下所示
Preorder: ['Electronics', 'Laptops', 'iMac', 'Dell', 'PC', 'CellPhones', 'pixel', 'iphone', 'Blackberry', 'TV', 'Sony', 'Samsung', 'LG']
--------------------------------------------------------------------------------------------------------------------------------------------
Postorder: ['iMac', 'Dell', 'PC', 'Laptops', 'pixel', 'iphone', 'Blackberry', 'CellPhones', 'Sony', 'Samsung', 'LG', 'TV', 'Electronics']
--------------------------------------------------------------------------------------------------------------------------------------------
Level order:
['Electronics']
['Laptops', 'CellPhones', 'TV']
['iMac', 'Dell', 'PC', 'pixel', 'iphone', 'Blackberry', 'Sony', 'Samsung', 'LG']
--------------------------------------------------------------------------------------------------------------------------------------------
Print Tree:
Electronics
|__ Laptops
|__ iMac
|__ Dell
|__ PC
|__ CellPhones
|__ pixel
|__ iphone
|__ Blackberry
|__ TV
|__ Sony
|__ Samsung
|__ LG
--------------------------------------------------------------------------------------------------------------------------------------------
DFS for 'iphone': FOUND
DFS for 'tesla': NOT Found
--------------------------------------------------------------------------------------------------------------------------------------------
BFS for 'iphone': FOUND
BFS for 'tesla': NOT Found
Process finished with exit code 0
解决方案 21：
使用字典创建 N-root、N-child 树
E1 E9 E10
/ / \n E2 E3 E11 E12
/ \n E4 E5 E6
/ \n E7 E8
Output:
输出：
TREE:
{'E1': {'E2': {'E4': {}, 'E5': {}}, 'E3': {'E6': {'E7': {}, 'E8': {}}}}, 'E9': {}, 'E10': {'E11': {}, 'E12': {}}}
PRINT:
|-E1
|-|-E2
|-|-|-E4
|-|-|-E5
|-|-E3
|-|-|-E6
|-|-|-|-E7
|-|-|-|-E8
|-E9
|-E10
|-|-E11
|-|-E12
代码：
def print_tree(atree, filler):
filler=filler + '|-'
for k, v in atree.items():
print(f'{filler}{k}')
print_tree(v, filler)
def make_tree(hierarchyList, btree):
for k in hierarchyList:
btree.setdefault(k, {})
btree = btree[k]
branch1 = ['E1', 'E2', 'E4']
branch2 = ['E1', 'E2', 'E5']
branch3 = ['E1', 'E3', 'E6', 'E7']
branch4 = ['E1', 'E3', 'E6', 'E8']
branch5 = ['E9']
branch6 = ['E10', 'E11']
branch7 = ['E10', 'E12']
branches = [branch1, branch2, branch3, branch4, branch5, branch6, branch7]
mytree = {}
for branch in branches:
make_tree(branch, mytree)
print(f'TREE:
{mytree}
PRINT:')
print_tree(mytree, '')
解决方案 22：
如果你想创建一个树形数据结构，那么首先你必须创建 treeElement 对象。如果你创建了 treeElement 对象，那么你就可以决定树的行为方式。
要做到这一点，以下是 TreeElement 类：
class TreeElement (object):
def __init__(self):
self.elementName = None
self.element = []
self.previous = None
self.elementScore = None
self.elementParent = None
self.elementPath = []
self.treeLevel = 0
def goto(self, data):
for child in range(0, len(self.element)):
if (self.element[child].elementName == data):
return self.element[child]
def add(self):
single_element = TreeElement()
single_element.elementName = self.elementName
single_element.previous = self.elementParent
single_element.elementScore = self.elementScore
single_element.elementPath = self.elementPath
single_element.treeLevel = self.treeLevel
self.element.append(single_element)
return single_element
现在，我们必须使用这个元素来创建树，在这个例子中我使用 A* 树。
class AStarAgent(Agent):
# Initialization Function: Called one time when the game starts
def registerInitialState(self, state):
return;
# GetAction Function: Called with every frame
def getAction(self, state):
# Sorting function for the queue
def sortByHeuristic(each_element):
if each_element.elementScore:
individual_score = each_element.elementScore[0][0] + each_element.treeLevel
else:
individual_score = admissibleHeuristic(each_element)
return individual_score
# check the game is over or not
if state.isWin():
print('Job is done')
return Directions.STOP
elif state.isLose():
print('you lost')
return Directions.STOP
# Create empty list for the next states
astar_queue = []
astar_leaf_queue = []
astar_tree_level = 0
parent_tree_level = 0
# Create Tree from the give node element
astar_tree = TreeElement()
astar_tree.elementName = state
astar_tree.treeLevel = astar_tree_level
astar_tree = astar_tree.add()
# Add first element into the queue
astar_queue.append(astar_tree)
# Traverse all the elements of the queue
while astar_queue:
# Sort the element from the queue
if len(astar_queue) > 1:
astar_queue.sort(key=lambda x: sortByHeuristic(x))
# Get the first node from the queue
astar_child_object = astar_queue.pop(0)
astar_child_state = astar_child_object.elementName
# get all legal actions for the current node
current_actions = astar_child_state.getLegalPacmanActions()
if current_actions:
# get all the successor state for these actions
for action in current_actions:
# Get the successor of the current node
next_state = astar_child_state.generatePacmanSuccessor(action)
if next_state:
# evaluate the successor states using scoreEvaluation heuristic
element_scored = [(admissibleHeuristic(next_state), action)]
# Increase the level for the child
parent_tree_level = astar_tree.goto(astar_child_state)
if parent_tree_level:
astar_tree_level = parent_tree_level.treeLevel + 1
else:
astar_tree_level += 1
# create tree for the finding the data
astar_tree.elementName = next_state
astar_tree.elementParent = astar_child_state
astar_tree.elementScore = element_scored
astar_tree.elementPath.append(astar_child_state)
astar_tree.treeLevel = astar_tree_level
astar_object = astar_tree.add()
# If the state exists then add that to the queue
astar_queue.append(astar_object)
else:
# Update the value leaf into the queue
astar_leaf_state = astar_tree.goto(astar_child_state)
astar_leaf_queue.append(astar_leaf_state)
您可以向对象中添加或删除任意元素，但要保持结构完整。
相关推荐
热门文章
项目管理软件有哪些？
热门标签
曾咪二维码
扫码咨询，免费领取项目管理大礼包！
云禅道AD
