父子集合（排序树的）

我需要某种形式的树集合，它能够存储基本的亲子关系，并在下一个简单的操作：父子集合（排序树的）

IsParent（thisNode，otherNode）（递归一个任何级别的父母）的
IsChild（thisNode，otherNode）（递归任何级别孩子的）
GetLevel（节点之一）获取节点的水平。

这个集合应该是快速的，可以是不可变的我不需要改变树。有很多树木收集，我不知道我需要什么样的树。

你知道Python中的这种集合吗？

2017-01-03 Brans Ds

[寻找一个好的Python树数据结构]可能的重复（http://stackoverflow.com/questions/3009935/looking-for-a-good-python-tree-data-structure） – wildwilhelm

@wildwilhelm I don不知道我需要什么类型的树。有很多类型 –

我想你必须自己写。这很容易，但

class Tree: 

    def __init__(self, data, parent=None): 
     self.children = [] 
     self.parent = parent 
     self.data = data 

    def add_child(self, data): 
     self.children.append(Tree(data, self)) 

    def has_child(self, target): 
     return any(map(lambda x: x.data == target or x.has_child(target), self.children)) 

    def has_parent(self, target): 
     return (self.parent.data == target or self.parent.has_parent(target)) if self.parent else False

我不会担心在这一点上速度过快。有可能有一些方法加速这一点，但像这样的数据结构相对较轻。如果你确实需要一些快速的东西，那么你最好的选择是用C语言编写它，然后用python访问它。这可能是为了你的目的矫枉过正。

来源

2017-01-03 14:26:53

这不是一个在lamda内部的递归，它可能因内存不足而导致深层树的内存不足，并且有很多级别？ –

@BransDs我不知道lambda函数的递归深度不同，但可能我不知道它。如果这是一个问题，那么我会建议编写一个类似的迭代函数。你想要这个东西有多大？我认为默认的递归深度就像1000个级别（由于开销少一点）。如果你的树有任何宽度，并且是这样的大小，它将成为一个真正的怪物 –

父子集合（排序树的）

回答

相关问题