반응형
파이썬에서 트리를 어떻게 구현할 수 있습니까? Java와 같이 Python에 내장 된 데이터 구조가 있습니까?
일반 트리를 만들려고합니다. 파이썬에서 트리를 구현하기 위해 내장 된 데이터 구조가 있습니까?
Anytree
나는 https://pypi.python.org/pypi/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가 있습니다.
- 간단한 트리 생성
- 간단한 트리 수정
- 선주문 트리 반복
- 주문 후 트리 반복
- 상대 및 절대 노드 경로 확인
- 한 노드에서 다른 노드로 걸어갑니다.
- 트리 렌더링 (위 예 참조)
- 노드 연결 / 분리 분리
파이썬에는 자바처럼 광범위한 "내장"데이터 구조가 없습니다. 그러나 파이썬은 동적이기 때문에 일반적인 트리를 쉽게 만들 수 있습니다. 예를 들어 이진 트리는 다음과 같습니다.
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"
일반 트리는 자식이 0 개 이상인 노드이며 각각은 적절한 (트리) 노드입니다. 이진 트리와 동일하지는 않지만 데이터 구조가 다르지만 둘 다 용어를 공유합니다.
파이썬에는 일반 트리에 대한 내장 데이터 구조가 없지만 클래스로 쉽게 구현됩니다.
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 collections import defaultdict
def tree(): return defaultdict(tree)
users = tree()
users['harold']['username'] = 'hrldcpr'
users['handler']['username'] = 'matthandlersux'
여기에 제안 된대로 : https://gist.github.com/2012250
내장 된 트리는 없지만 List에서 Node 유형을 서브 클래 싱하고 순회 메소드를 작성하여 쉽게 트리를 구성 할 수 있습니다. 이 작업을 수행하면 bisect가 유용하다는 것을 알았습니다 .
PyPi 에는 찾아 볼 수있는 많은 구현 이 있습니다.
올바르게 기억한다면 Python 표준 라이브러리에는 .NET 기본 클래스 라이브러리에없는 것과 같은 이유로 트리 데이터 구조가 포함되어 있지 않습니다. 메모리의 지역성이 줄어들어 캐시 누락이 더 많이 발생합니다. 최신 프로세서에서는 일반적으로 많은 양의 메모리를 캐시로 가져 오는 것이 더 빠르며 "포인터가 풍부한"데이터 구조는 이점을 무시합니다.
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}
이 구조는 모든 노드에서 루트까지의 경로를 따라 올라가는 것을 매우 쉽게 만들었습니다.
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
/ \
grandchild1 gchild2
tree=tree.prev()
tree=tree.prev()
tree=tree.add()
tree=tree.name="child2"
root
/ \
child1 child2
/ \
grandchild1 gchild2
tree=tree.prev()
tree=tree.goto("child1") or tree=tree.nex(0)
tree.name="changed"
root
/ \
changed child2
/ \
grandchild1 gchild2
이 작업을 수행하는 방법을 알아 내기에 충분해야합니다.
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
사전으로 작동하지만 원하는만큼 많은 dicts를 제공합니다. 다음을 시도하십시오 :
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'] = '*'
중첩 된 dict ...을 제공하여 실제로 나무로 작동합니다.
{'a': {'1': {'x': '@', 'y': '#'}, '2': {'x': '$'}, '3': '%'}, 'b': '*'}
... 이미 dict을 가지고 있다면 각 레벨을 트리로 캐스트합니다.
d = {'foo': {'amy': {'what': 'runs'} } }
tree = Tree(d)
print(d['foo']['amy']['what']) # returns 'runs'
d['foo']['amy']['when'] = 'now' # add new branch
이 방법으로 원하는대로 각 dict 레벨을 편집 / 추가 / 제거 할 수 있습니다. 순회 등에 대한 모든 dict 방법은 여전히 적용됩니다.
중첩 된 dicts를 사용하여 트리를 구현했습니다. 그것은 매우 쉽고, 매우 큰 데이터 세트로 저에게 효과적이었습니다. 아래에 샘플을 게시했으며 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)
내 사이트에 Python [3] 트리 구현을 게시했습니다 : http://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("\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)
누군가가 더 간단한 방법이 필요하다면, 트리는 재귀 적으로 중첩 된 목록 일뿐입니다 (세트가 해시 가능하지 않기 때문에).
[root, [child_1, [[child_11, []], [child_12, []]], [child_2, []]]]
각 분기가 [object, [children]]
쌍이고 각 리프가 [object, []] 쌍입니다.
그러나 메소드가있는 클래스가 필요한 경우 anytree를 사용할 수 있습니다.
어떤 작업이 필요합니까? 파이썬에는 종종 dict 또는 bisect 모듈과 함께 목록을 사용하는 좋은 솔루션이 있습니다.
PyPI 에는 많은 트리 구현이 있으며, 많은 트리 유형은 순수한 파이썬으로 자신을 구현하는 데 거의 사소합니다. 그러나 이것은 거의 필요하지 않습니다.
브루노의 대답에 기반을 둔 또 다른 트리 구현 :
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)
어느 것을 출력해야합니까?
루트 노드
/ / \
자식 노드 0 자식 노드 1 자식 노드 2
| / \
손자 1.0 손자 2.0 손자 2.1
트리 데이터 구조를 생성하려면 먼저 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 iterative_bfs(graph, start):
'''iterative breadth first search from start'''
bfs_tree = {start: {"parents":[], "children":[], "level":0}}
q = [start]
while q:
current = q.pop(0)
for v in graph[current]:
if not v in bfs_tree:
bfs_tree[v]={"parents":[current], "children":[], "level": bfs_tree[current]["level"] + 1}
bfs_tree[current]["children"].append(v)
q.append(v)
else:
if bfs_tree[v]["level"] > bfs_tree[current]["level"]:
bfs_tree[current]["children"].append(v)
bfs_tree[v]["parents"].append(current)
반응형
'IT story' 카테고리의 다른 글
| 전화 : 텍스트 입력을위한 숫자 키보드 (0) | 2020.06.03 |
|---|---|
| 맵을 통한 C ++ 루프 (0) | 2020.06.03 |
| mockito로 최종 수업을 조롱하는 방법 (0) | 2020.06.03 |
| C #에서 해당 월의 마지막 날을 어떻게 얻을 수 있습니까? (0) | 2020.06.03 |
| HTML에서 PDF의 텍스트 링크 클릭시 "다른 이름으로 저장 ..."팝업을 강제로 엽니 다. (0) | 2020.06.03 |