Python中最简单的树形数据结构，可以轻松地双向遍历。

Question

我需要一个最简单的数据结构实现，可以在父-子和子-父方向上遍历；因此理想情况下，子节点应该也持有对父节点的引用。

考虑使用字典，其中子节点只需简单地保存对其父节点的引用，类似于以下示例：

# define the root node
a = {'name': 'trunk', 'value': 0, 'parent': None, 'children': []}
# add child
a['children'].append({'name': 'branch-1', 'value': 1,
                      'parent': a, 'children': []})
# and so on...

这样做安全吗？（循环引用可能会影响垃圾回收？）这么做有意义吗？有更简单的方法吗？

- taskalman

---

有人可能会认为简单意味着代码量少，易于维护或遍历结构。另一个观点认为简单意味着占用空间较少。还有一种解释是将操作的时间复杂度作为定义简单的标准。 - undefined

你说得对，客观地定义这个并不总是容易的。我想我的意思是它应该具有尽可能少的移动部分，并且尽可能接近语言中的基本数据结构。当然，同时也不能太难使用... - undefined

如果子节点只引用父节点，那么从父节点移动到子节点会很困难。有几个问题。每个节点都有唯一的值吗？你熟悉创建类吗？ - undefined

@ExperimentsWithCode 对不起，忘了这个：让我们假设节点是唯一的。 - undefined

@ExperimentsWithCode 谢谢，我想我犯了一个错误，没有在这里更具体地说明我的需求。我的需求非常简单，即从根节点构建树，并偶尔从一个节点向上遍历几个层级以读取内容。所以没有更新，没有删除，只是构建树然后移动和读取。实际上，我计划以这种方式封装ElementTree对象（我只能使用stdlib版本。没有父引用 :( ），以便能够查看几个父节点以交叉检查依赖关系。话虽如此，我仍然喜欢你的答案，也许是因为我试图过于努力地避免使用类... - undefined

Answer 1

一个简单的树（节点）类，可以双向遍历：

class Tree(object):
    def __init__(self, data, children=None, parent=None):
        self.data = data
        self.children = children or []
        self.parent = parent

    def add_child(self, data):
        new_child = Tree(data, parent=self)
        self.children.append(new_child)
        return new_child

    def is_root(self):
        return self.parent is None

    def is_leaf(self):
        return not self.children

    def __str__(self):
        if self.is_leaf():
            return str(self.data)
        return '{data} [{children}]'.format(data=self.data, children=', '.join(map(str, self.children)))

> t = Tree('foo')
> bar = t.add_child('bar')
> baz = t.add_child('baz')
> print(t)
'foo [bar, baz]'

> print(bar.parent)
'foo [bar, baz]'

- user2390182

Answer 2

你需要创建一个名为Node的类。基本结构看起来像这样，不过说实话你也可以用字典来实现。只是我个人觉得类更加简洁易读。

class Node(object):
    def __init__(self):
        self.parent = None # Single object
        self.child = []  # Array of objects
        self.name = None
        self.data = None 

其余的取决于你的需求。一些你可能想要构建到你的类中的功能（或者如果你使用哈希表，可以作为脚本中的方法构建）：

• 更新：接受一个特定的节点并更新其值/名称/其他内容
• 删除：接受一个特定的节点并从树中删除它。如果这样做，请确保将已删除节点的子节点连接到已删除节点的父节点。
• 插入：接受树中的特定位置并添加一个新的节点。这应该更新节点周围的父节点和子节点。
• 更新子节点：将子节点附加到节点.child数组。应该从更新父节点调用这两个过程是自我参照的。
• 更新父节点：从parent.child数组中删除self。将self添加到new_parent.child数组中。

如果您想轻松地引用节点的特定部分，可以创建一个哈希映射作为目录。

node_tree_map = {}
node_tree_map[node.name] = node 
# node_tree_map['name'] would allow you quick access to bob's
# parent/children/value 
# just by knowing the name but without having to traverse 
# the whole tree to find it 

如果有必要，以上方法将允许您轻松地进入特定的节点。

顺便说一下，如果从树或哈希映射中删除一个节点，则垃圾收集将不再是一个问题。

- ExperimentsWithCode

---

我将这个作为答案，喜欢你从最简单的类开始，然后采用教育性的方法来展示选项。查找特定节点的“混合”解决方案也很不错，我以后可能会用到它。谢谢！ - undefined