父子集合（排序樹的）

我需要某種形式的樹集合，它能夠存儲基本的親子關係，並在下一個簡單的操作：父子集合（排序樹的）

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個級別（由於開銷少一點）。如果你的樹有任何寬度，並且是這樣的大小，它將成爲一個真正的怪物 –

父子集合（排序樹的）

回答

相關問題