一种通用的树实现？

Question

我希望构建一棵通用树，其根节点包含'n'个子节点，这些子节点可能包含其他子节点......

- vishnu

---

好的，我将尽力为您翻译。以下是需要翻译的内容：This has been asked only a few days ago ... http://stackoverflow.com/questions/2461170/tree-implementation-in-python这个问题只在几天前被问到过...http://stackoverflow.com/questions/2461170/tree-implementation-in-python - Johannes Charra

你阅读了哪些在线资源？你尝试过什么？你卡在哪里了？ - user97370

双重复制：https://dev59.com/UXE95IYBdhLWcg3wUcVn?rq=1 - eric

Answer 1

Python中的树相当简单。创建一个包含数据和子节点列表的类。每个子节点都是同一类的实例。这是一个通用的n进制树。

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

    def add_child(self, obj):
        self.children.append(obj)

然后进行交互：

>>> n = Node(5)
>>> p = Node(6)
>>> q = Node(7)
>>> n.add_child(p)
>>> n.add_child(q)
>>> n.children
[<__main__.Node object at 0x02877FF0>, <__main__.Node object at 0x02877F90>]
>>> for c in n.children:
...   print c.data
... 
6
7
>>> 

这是一个非常基本的框架，没有进行任何抽象处理。实际的代码将取决于您的具体需求 - 我只是想展示Python很简单。

- Eli Bendersky

---

@vishnu: 这是否足够？ - Eli Bendersky

这个答案应该被接受。 - rottweiler

问题是，这可能会导致对象或魔术方法的递归限制错误。那么使用链表实现转换成树形结构怎么样？就像这里：https://github.com/erayerdin/linglib/blob/syntax/linglib/syntax/__init__.py | 问题是，这将带来很多工作，比如确保节点没有两个父节点之类的事情。 - Eray Erdin

这似乎在超过2个级别时无法工作。如何将子元素添加到列表中每个元素的根？ - Ben Alan

@BenAlan：你可以使用 n.children[0].add_child(foo)。 - Eli Bendersky

Answer 2

我在我的网站上发布了一个Python [3]树实现：http://www.quesucede.com/page/show/id/python_3_tree_implementation。希望对你有所帮助。

以下是代码：

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)

- Brett Kromkamp

---

可以考虑在Stack Overflow上发布代码。如果你的博客消失了，这个答案就变得毫无意义了。 - Bart Kiers

@Brett Kromkamp。不错的实现，但我想知道您发布了哪种软件许可证类型？谢谢。 - enthusiasticgeek

啊，糟糕！看起来是GPLv3许可证https://github.com/dbrgn/pyTree/blob/master/LICENSE 。不能使用这段代码。 :-( - enthusiasticgeek

你如何从这样的树中间删除节点？ - uuu777

Answer 3

anytree

我推荐使用 https://pypi.python.org/pypi/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

---

看起来不错，但是使用OrderedDict的话，搜索具有特定属性的所有节点将无法工作。我已经在GitHub上开了一个问题。 - Dejell

Answer 4

node = { 'parent':0, 'left':0, 'right':0 }
import copy
root = copy.deepcopy(node)
root['parent'] = -1
left = copy

只是为了展示另一种在“面向对象编程”中实现的思路

class Node:
    def __init__(self,data):
        self.data = data
        self.child = {}
    def append(self, title, child):
        self.child[title] = child

CEO = Node( ('ceo', 1000) )
CTO = ('cto',100)
CFO = ('cfo', 10)
CEO.append('left child', CTO)
CEO.append('right child', CFO)

print CEO.data
print ' ', CEO.child['left child']
print ' ', CEO.child['right child']

- uronce