如何在Python中实现通用树?这有内置的数据结构吗?
当前回答
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
其他回答
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的创造者;)
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
这应该足够让你开始思考如何让它工作了
如果您想要创建树数据结构,那么首先必须创建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)
你可以从对象中添加/删除任何元素,但要使结构为完整的。
您可以使用Python中的dataclasses模块创建Tree数据结构。
iter方法可用于使树可迭代,允许您通过改变yield语句的顺序来遍历树。
contains方法可用于检查树中是否存在特定值。
from dataclasses import dataclass
# A
# / \
# B C
# / \ \
# D E F
# / \
# 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 ->
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()
推荐文章
- 证书验证失败:无法获得本地颁发者证书
- 当使用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中获得所有直接子目录