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

我已经在我的网站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基类库不包含树数据结构是一样的:内存的局部性降低了，导致缓存丢失更多。在现代处理器上，将大量内存放入缓存通常会更快，而“指针丰富”的数据结构会抵消这种好处。

泛型树是一个具有零个或多个子节点的节点，每个子节点都是一个合适的(树)节点。它与二叉树不同，它们是不同的数据结构，尽管它们都有一些相同的术语。

Python中没有任何用于泛型树的内置数据结构，但很容易通过类实现。

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')])])

我将根树实现为字典{child:parent}。比如根节点为0，树可能是这样的:

tree={1:0, 2:0, 3:1, 4:2, 5:3}

这种结构使得沿着一条路径从任意节点向上到根结点非常容易，这与我正在处理的问题有关。

嗨，你可以试试itertree(我是作者)。

该包与任何树包的方向相同，但关注点略有不同。在巨大的树(>100000个项目)上的性能要好得多，它处理迭代器具有有效的过滤机制。

>>>from itertree import *
>>>root=iTree('root')

>>># add some children:
>>>root.append(iTree('Africa',data={'surface':30200000,'inhabitants':1257000000}))
>>>root.append(iTree('Asia', data={'surface': 44600000, 'inhabitants': 4000000000}))
>>>root.append(iTree('America', data={'surface': 42549000, 'inhabitants': 1009000000}))
>>>root.append(iTree('Australia&Oceania', data={'surface': 8600000, 'inhabitants': 36000000}))
>>>root.append(iTree('Europe', data={'surface': 10523000 , 'inhabitants': 746000000}))
>>># you might use __iadd__ operator for adding too:
>>>root+=iTree('Antarktika', data={'surface': 14000000, 'inhabitants': 1100})

>>># for building next level we select per index:
>>>root[0]+=iTree('Ghana',data={'surface':238537,'inhabitants':30950000})
>>>root[0]+=iTree('Niger', data={'surface': 1267000, 'inhabitants': 23300000})
>>>root[1]+=iTree('China', data={'surface': 9596961, 'inhabitants': 1411780000})
>>>root[1]+=iTree('India', data={'surface': 3287263, 'inhabitants': 1380004000})
>>>root[2]+=iTree('Canada', data={'type': 'country', 'surface': 9984670, 'inhabitants': 38008005})    
>>>root[2]+=iTree('Mexico', data={'surface': 1972550, 'inhabitants': 127600000 })
>>># extend multiple items:
>>>root[3].extend([iTree('Australia', data={'surface': 7688287, 'inhabitants': 25700000 }), iTree('New Zealand', data={'surface': 269652, 'inhabitants': 4900000 })])
>>>root[4]+=iTree('France', data={'surface': 632733, 'inhabitants': 67400000 }))
>>># select parent per TagIdx - remember in itertree you might put items with same tag multiple times:
>>>root[TagIdx('Europe'0)]+=iTree('Finland', data={'surface': 338465, 'inhabitants': 5536146 })

创建的树可以被渲染:

>>>root.render()
iTree('root')
     └──iTree('Africa', data=iTData({'surface': 30200000, 'inhabitants': 1257000000}))
         └──iTree('Ghana', data=iTData({'surface': 238537, 'inhabitants': 30950000}))
         └──iTree('Niger', data=iTData({'surface': 1267000, 'inhabitants': 23300000}))
     └──iTree('Asia', data=iTData({'surface': 44600000, 'inhabitants': 4000000000}))
         └──iTree('China', data=iTData({'surface': 9596961,  'inhabitants': 1411780000}))
         └──iTree('India', data=iTData({'surface': 3287263, 'inhabitants': 1380004000}))
     └──iTree('America', data=iTData({'surface': 42549000, 'inhabitants': 1009000000}))
         └──iTree('Canada', data=iTData({'surface': 9984670, 'inhabitants': 38008005}))
         └──iTree('Mexico', data=iTData({'surface': 1972550, 'inhabitants': 127600000}))
     └──iTree('Australia&Oceania', data=iTData({'surface': 8600000, 'inhabitants': 36000000}))
         └──iTree('Australia', data=iTData({'surface': 7688287, 'inhabitants': 25700000}))
         └──iTree('New Zealand', data=iTData({'surface': 269652, 'inhabitants': 4900000}))
     └──iTree('Europe', data=iTData({'surface': 10523000, 'inhabitants': 746000000}))
         └──iTree('France', data=iTData({'surface': 632733, 'inhabitants': 67400000}))
         └──iTree('Finland', data=iTData({'surface': 338465, 'inhabitants': 5536146}))
     └──iTree('Antarktika', data=iTData({'surface': 14000000, 'inhabitants': 1100}))

过滤可以这样做:

>>>item_filter = Filter.iTFilterData(data_key='inhabitants', data_value=iTInterval(0, 20000000))
>>>iterator=root.iter_all(item_filter=item_filter)
>>>for i in iterator:
>>>    print(i)
iTree("'New Zealand'", data=iTData({'surface': 269652, 'inhabitants': 4900000}), subtree=[])
iTree("'Finland'", data=iTData({'surface': 338465, 'inhabitants': 5536146}), subtree=[])
iTree("'Antarktika'", data=iTData({'surface': 14000000, 'inhabitants': 1100}), subtree=[])