일반 트리를 구성하려고합니다.
그것을 구현하기 위해 파이썬에 내장 데이터 구조가 있습니까?
답변
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
답변
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()답변
트리가 내장되어 있지 않지만 List에서 Node 유형을 서브 클래 싱하고 순회 메소드를 작성하여 쉽게 트리를 구성 할 수 있습니다. 이 작업을 수행하면 bisect가 유용하다는 것을 알았습니다 .
PyPi 에는 찾아 볼 수있는 많은 구현 이 있습니다.
올바르게 기억한다면 Python 표준 라이브러리에는 .NET 기본 클래스 라이브러리에없는 것과 같은 이유로 트리 데이터 구조가 포함되어 있지 않습니다. 메모리의 지역성이 줄어들어 캐시 누락이 더 많이 발생합니다. 최신 프로세서에서는 일반적으로 많은 양의 메모리를 캐시로 가져 오는 것이 더 빠르며 “포인터가 풍부한”데이터 구조는 이점을 무시합니다.
답변
루팅 된 트리를 사전으로 구현했습니다 {child:parent}. 예를 들어 루트 노드 0의 경우 트리는 다음과 같습니다.
tree={1:0, 2:0, 3:1, 4:2, 5:3}이 구조는 모든 노드에서 루트까지의 경로를 따라 올라가는 것을 매우 쉽게 만들었습니다. 이는 내가 작업중 인 문제와 관련이 있습니다.
