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

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

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

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

另一个基于Bruno回答的树的实现:

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)

它应该输出:

                        Root node                        
     /             /                      \              
Child node 0  Child node 1           Child node 2        
                   |              /              \       
             Grandchild 1.0 Grandchild 2.0 Grandchild 2.1

嗨，你可以试试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=[])

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()