如何在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)
你可以从对象中添加/删除任何元素,但要使结构为完整的。
其他回答
我使用嵌套字典实现了树。这很容易做到,而且对我来说,它在相当大的数据集上很有效。我在下面发布了一个示例,你可以在谷歌代码中看到更多
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)
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]
另一个基于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
我已经在我的网站https://web.archive.org/web/20120723175438/www.quesucede.com/page/show/id/python_3_tree_implementation上发布了一个Python 3树的实现
代码如下:
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("\t"*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)
并没有内置树,但是可以通过从List继承Node类型并编写遍历方法来轻松地构造一个树。如果你这样做,我发现平分法很有用。
您还可以浏览PyPi上的许多实现。
如果我没记错的话,Python标准库不包含树数据结构,原因和。net基类库不包含树数据结构是一样的:内存的局部性降低了,导致缓存丢失更多。在现代处理器上,将大量内存放入缓存通常会更快,而“指针丰富”的数据结构会抵消这种好处。
推荐文章
- 证书验证失败:无法获得本地颁发者证书
- 当使用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中获得所有直接子目录