如何在Python中实现通用树?这有内置的数据结构吗?
当前回答
如果您想要创建树数据结构,那么首先必须创建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)
你可以从对象中添加/删除任何元素,但要使结构为完整的。
其他回答
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的创造者;)
泛型树是一个具有零个或多个子节点的节点,每个子节点都是一个合适的(树)节点。它与二叉树不同,它们是不同的数据结构,尽管它们都有一些相同的术语。
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')])])
我使用嵌套字典实现了树。这很容易做到,而且对我来说,它在相当大的数据集上很有效。我在下面发布了一个示例,你可以在谷歌代码中看到更多
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)
如果您想要创建树数据结构,那么首先必须创建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)
你可以从对象中添加/删除任何元素,但要使结构为完整的。
如果您已经在使用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')
该库允许每个节点是任何可哈希对象,并且不限制每个节点拥有的子节点的数量。
推荐文章
- 如何更新SQLAlchemy行条目?
- name 'reduce'在Python中没有定义
- 如何计算一个NumPy bool数组中的真实元素的数量
- 在python中,在函数结束(例如检查失败)之前退出函数(没有返回值)的最佳方法是什么?
- 在Python中检查一个单词是否在字符串中
- Python glob多个文件类型
- 如何可靠地打开与当前运行脚本在同一目录下的文件
- Python csv字符串到数组
- 如何在Python中进行热编码?
- 如何嵌入HTML到IPython输出?
- 在Python生成器上使用“send”函数的目的是什么?
- 段树、区间树、二叉索引树和范围树之间有什么区别?
- 是否可以将已编译的.pyc文件反编译为.py文件?
- Django模型表单对象的自动创建日期
- 在Python中包装长行