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

Answer 2

你可以创建一个节点类。在

基本的结构应该是这样的，不过老实说，你也可以用dicts来实现。只是我个人觉得课程看起来更干净。在

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

剩下的取决于你的需要。您可能希望将一些函数内置到类中（或者如果使用哈希，则在脚本中作为方法构建）

• Update：获取特定节点并更新其值/名称/什么 你有吗
• Delete：获取特定节点并将其从树中移除。如果 执行此操作时，请确保将已删除的节点子节点连接到
  已删除父节点。在
• Insert：获取树中的特定点并添加新节点 投入其中。这将更新节点周围的父节点和子节点。在
• 更新子项：将子项附加到节点.子级数组。应该是 从update parent调用，因为这两个进程是自引用的。在
• 更新父对象：从中删除自身父级.子级数组。将自身添加到 新的_父级.子级数组。在

如果您想方便地引用节点的特定部分，可以将hash_映射作为一种目录

^{pr2}$

如果需要的话，上面的内容将允许您轻松地深入到特定的节点中。在

顺便说一句，删除树或哈希映射中引用的节点将使垃圾回收成为一个不成问题的问题。在