我该如何在Python中实现一棵树？

Question

我该如何在Python中实现一棵通用树？是否有内置的数据结构可用于此?

- vishnu

---

https://www.geeksforgeeks.org/binarytree-module-in-python/ - GrvTyagi

实际上，问题中最初所指的“general”并不清楚。它可能意味着“每个节点上任意数量的子节点”，“节点中存储任意类型的数据”，或者可能是其他一些东西。 - Karl Knechtel

Answer 1

我推荐 anytree（我是作者）。

示例：

示例：

from anytree import Node, RenderTree

udo = Node("Udo")
marc = Node("Marc", parent=udo)
lian = Node("Lian", parent=marc)
dan = Node("Dan", parent=udo)
jet = Node("Jet", parent=dan)
jan = Node("Jan", parent=dan)
joe = Node("Joe", parent=dan)

print(udo)
Node('/Udo')
print(joe)
Node('/Udo/Dan/Joe')

for pre, fill, node in RenderTree(udo):
    print("%s%s" % (pre, node.name))
Udo
├── Marc
│   └── Lian
└── Dan
    ├── Jet
    ├── Jan
    └── Joe

print(dan.children)
(Node('/Udo/Dan/Jet'), Node('/Udo/Dan/Jan'), Node('/Udo/Dan/Joe'))

anytree 同时具备强大的 API，包括：

• 简单的树形结构创建
• 简单的树形结构修改
• 前序遍历和后序遍历
• 解决相对和绝对节点路径
• 从一个节点走到另一个节点
• 树形结构渲染（见上面的示例）
• 节点附加/分离连接

- c0fec0de

---

这并没有回答问题，只是为了宣传你自己的项目，但出于某种原因却成为了谷歌搜索结果的首选。问题是如何实现一棵树，而不是如何使用你的实现。 - Emanuel P

他的开源实现是一个很好的学习范例。 - undefined

他的开源实现是一个很好的学习范例。 - Clintm

Answer 2

Python没有像Java那样丰富的“内置”数据结构。但是，由于Python是动态的，因此很容易创建一棵普通树。例如，二叉树可以表示为：

class Tree:
    def __init__(self):
        self.left = None
        self.right = None
        self.data = None

您可以像这样使用它：

root = Tree()
root.data = "root"
root.left = Tree()
root.left.data = "left"
root.right = Tree()
root.right.data = "right"

如果您需要每个节点具有任意数量的子节点，请使用子节点列表：

class Tree:
    def __init__(self, data):
        self.children = []
        self.data = data

left = Tree("left")
middle = Tree("middle")
right = Tree("right")
root = Tree("root")
root.children = [left, middle, right]

- Greg Hewgill

---

这并没有对如何实现一棵有用的树结构进行详细解释。 - Mike Graham

问题被打上了Python3的标签，因此无需从object派生class Tree。 - cfi

若一个类没有继承其他基类，那么从 object 继承有时只是一条指南。对于嵌套的类也是如此。请参考《Google Python 风格指南》。 - Konrad Reiche

请完整阅读并引用指南：Google明确指出这对于Python 2代码的正常工作是必需的，并建议提高与Py3的兼容性。在这里，我们谈论的是Py3代码。没有必要进行额外的遗留类型标注。 - cfi

这是一棵二叉树，而不是要求的一般树。 - Michael Dorner

Answer 3

通用树是一个节点，它有零个或多个子节点，每个子节点都是一个真正的（树）节点。它与二叉树不同，它们是不同的数据结构，尽管两者共享一些术语。

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

- Rudá Moura

---

太棒了，这可以很容易地用作图表！我看到的唯一问题是：我如何区分左节点和右节点？ - Ângelo Polotto

按照孩子索引。在这种情况下，左边始终是children[0]。 - Freund Allein

并且右侧始终为len(self.children)。 - Willy satrio nugroho

Answer 4

你可以尝试：

from collections import defaultdict
def tree(): return defaultdict(tree)
users = tree()
users['harold']['username'] = 'hrldcpr'
users['handler']['username'] = 'matthandlersux'

正如这里所建议的：https://gist.github.com/2012250

- Ib33X

---

如果您想扩展到任意数量的级别，请查看：https://dev59.com/UXE95IYBdhLWcg3wUcVn#43237270 - natbusa

Answer 5

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

- shivam garg

---

你能否添加一些注释来介绍你的代码和实现方法？请注意要保持原意，让内容更加通俗易懂。 - Michele d'Amico

感谢您提供了完整的二叉树实现及其实用函数。由于它是基于Python 2编写的，我创建了一个Gist来为需要Python 3版本的人提供二叉树实现（Py3）。 - CᴴᴀZ

Answer 6

虽然 Python 标准库没有树形数据结构，但您可以通过从 List 继承 Node 类型并编写遍历方法来轻松构建一个。如果这样做，我发现 bisect 很有用。

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

如果我没记错的话，Python 标准库之所以不包括树形数据结构，是因为 .NET 基础类库也不包括：内存局部性减少，导致更多的缓存未命中。在现代处理器上，通常更快的方法是将大块内存带入缓存中，并且“指针丰富”的数据结构会抵消这种好处。

- Justin R.

---

FYI：互联网上充斥着针对Boost的仇恨。 显然，这个库被认为非常难处理，特别是因为它的支持已经停止。所以我建议远离它。 - inspectorG4dget

谢谢。我个人没有遇到任何问题，但我不想误导别人，所以我已经删除了那个参考。 - Justin R.

Answer 7

我将一棵根树实现成一个字典{child:parent}。因此，例如以根节点0为例，一棵树可能如下所示：

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

这种结构使得从任何节点沿着路径向上到达根节点非常容易，这对我正在解决的问题很有帮助。

- paw

---

这是我一开始考虑的方法，直到看到答案。尽管树是一个有两个子节点的父节点，如果你想往下走，可以使用 {parent:[leftchild,rightchild]}。 - Jacqlyn

另一种方法是使用列表的列表，其中列表中的第一个（或更多）元素是节点值，接下来的两个嵌套列表表示其左子树和右子树（或n元树的更多子树）。 - pepr

Answer 8

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

现在只需创建一个根并构建它：

ex:

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

这应该足够让你开始思考如何让这个工作起来了

- Bruno

---

这个答案有些不完整，我已经试了这个解决方案两天了，我认为你的对象添加方法中有一些逻辑流程问题。我会提交我的答案给这个问题，请检查一下并让我知道是否需要帮忙。 - MAULIK MODI

Answer 9

如果有人需要更简单的方法，那么树只是一个递归嵌套的列表（因为集合是不可哈希的）：

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

每个分支都是一对： [ 对象, [子节点] ]
每个叶子都是一对： [ 对象, [] ]

但如果您需要带有方法的类，则可以使用 anytree。

- Hugo Trentesaux

Answer 10

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

通过这种方式，您可以根据自己的意愿保留/添加/删除每个字典级别。所有字典遍历等方法仍然适用。

- natbusa

---

你为什么选择扩展 dict 而不是 defaultdict？根据我的测试，扩展 defaultdict 而不是 dict 然后在 init 的顶部添加 self.default_factory = type(self) 应该具有相同的功能。 - Rob Rose

我可能在这里漏掉了什么，你如何导航这个结构？例如，从子节点到父节点或兄弟节点似乎非常困难。 - Stormsson