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...

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

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