如何在Python中实现树?

如何在Python中实现通用树?这有内置的数据结构吗?

当前回答

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

2021-05-14 07:48:59

其他回答

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

2023-02-08 21:07:35

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

2015-04-09 07:07:59

如果有人需要一个更简单的方法，树只是一个递归嵌套的列表(因为set是不可哈希的):

[root, [child_1, [[child_11, []], [child_12, []]], [child_2, []]]]

每个分支都是一对:[object， [children]] 每个叶子是一对:[object， []]

但是如果你需要一个带有方法的类，你可以使用任何树。

2019-02-10 07:58:42

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

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

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

2010-03-01 18:28:31