我需要一个数据结构的最简单的实现，它可以在父->子和子->父方向上遍历；因此，理想情况下，子级也应该拥有对父级的引用。
我在想一本字典，孩子们可以简单地引用他们的父母，类似于这样：
# 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...
这样做安全吗？(循环引用可能会影响垃圾收集？)这样做有意义吗？什么会更简单？
一个简单的Tree(Node)类，可以双向遍历：
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]'
您可以创建一个Node类。
基本结构看起来是这样的，尽管老实说，你也可以用dicts来做。只是个人感觉课堂看起来更干净。
class Node(object):
def __init__(self):
self.parent = None # Single object
self.child = [] # Array of objects
self.name = None
self.data = None
其余的取决于你的需要。您可能希望将一些函数构建到类中(或者，如果您使用哈希，则在脚本中构建为方法)
- 更新：获取特定节点并更新其值/name/what有你吗
- Delete：获取特定节点并将其从树中删除。如果执行此操作时，请确保将已删除节点的子节点连接到
已删除节点父节点 - Insert：在树中取一个特定点并添加一个新节点这应该会更新节点周围的父节点和子节点
- 更新子级：将子级追加到node.child数组中。应该是从更新父进程调用，因为这两个进程是自引用的
- 更新父对象：从parent.child数组中删除self。将自身添加到new_parent.child数组
如果您想方便地引用节点的特定部分，可以将hash_map作为一种目录
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
以上内容将使您能够在必要时轻松深入特定节点。
顺便说一句，从树或哈希映射中删除引用的节点将使垃圾收集成为一个不成问题的问题。