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

如果您想要创建树数据结构，那么首先必须创建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)

你可以从对象中添加/删除任何元素，但要使结构为完整的。

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

作为一个字典，但提供尽可能多的嵌套字典。 试试下面的方法:

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']            = '*'

将传递一个嵌套的字典…就像树一样。

{'a': {'1': {'x': '@', 'y': '#'}, '2': {'x': '$'}, '3': '%'}, 'b': '*'}

．.． 如果你已经有字典了，它会把每一层都投射到一棵树上:

d = {'foo': {'amy': {'what': 'runs'} } }
tree = Tree(d)

print(d['foo']['amy']['what']) # returns 'runs'
d['foo']['amy']['when'] = 'now' # add new branch

这样，你就可以随心所欲地编辑/添加/删除每个词典级别。 遍历等所有dict方法仍然适用。

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

您可以使用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  -> 

并没有内置树，但是可以通过从List继承Node类型并编写遍历方法来轻松地构造一个树。如果你这样做，我发现平分法很有用。

您还可以浏览PyPi上的许多实现。

如果我没记错的话，Python标准库不包含树数据结构，原因和。net基类库不包含树数据结构是一样的:内存的局部性降低了，导致缓存丢失更多。在现代处理器上，将大量内存放入缓存通常会更快，而“指针丰富”的数据结构会抵消这种好处。