我有以下类，它在自身上重复形成一个树状数据结构：
public class chartObject
{
public string name { get; set; }
public int descendants { get; set; }
public List<chartObject> children { get; set; }
}
对于树中的每个对象，我想用它下面存在的数量对象填充后代属性。
示例结构：
chartObject1 (descendants: 4)
└-chartObject2 (descendants: 0)
└-chartObject3 (descendants: 2)
└--chartObject4 (descendants: 1)
└---chartObject5 (descendants: 0)
这样做最有效的方法是什么？
递归公式如何：
children.Count + children.Sum(c => c.descendants)
如果树是不可变的（它不是来自类声明），这适用于急切评估/缓存。如果您即使面对可变性也想要效率，您会发现这要困难得多；您可以考虑将树的某些部分标记为“脏”，因为它已发生突变/急切地强制重新评估此指标以“冒泡”，因为树的一部分已发生突变。
这对我有用：
public void SetDescendants(chartObject current)
{
foreach (var child in current.children)
{
SetDescendants(child);
}
current.descendants = current.children.Sum(x => 1 + x.descendants);
}
我用这段代码测试过：
var co = new chartObject()
{
name = "chartObject1",
children = new List<chartObject>()
{
new chartObject()
{
name = "chartObject2",
children = new List<chartObject>() { }
},
new chartObject()
{
name = "chartObject3",
children = new List<chartObject>()
{
new chartObject()
{
name = "chartObject4",
children = new List<chartObject>()
{
new chartObject()
{
name = "chartObject5",
children = new List<chartObject>() { }
}
}
}
}
}
}
};
结果是这样的：
为了使计算最有效，请将其结果缓存在节点本身中。否则，您将在每次descendants查找该属性时重新计算计数。
这样做的代价是需要使父链上的缓存一直无效，如下所示：
public class chartObject
{
private chartObject _parent;
private int? _descCache = null;
public string name { get; set; }
public int descendants {
get {
return _descCache ?? calcDescendents();
}
}
public List<chartObject> children { get; set; }
public void AddChild(chartObject child) {
child._parent = this;
children.Add(child);
chartObject tmp = this;
while (tmp != null) {
tmp._descCache = null;
tmp = tmp._parent;
}
}
private int calcDescendents() {
return children.Count+children.Sum(child => child.descendants);
}
}
遍历树的所有节点（深度优先），当孩子完成后，将“descendants 属性设置为孩子的后代 + 孩子计数的总和。你必须在每次更改树结构时都这样做。你应该能够限制更新仅适用于已更改元素的父母。
如果节点不可变，您可以在创建时填充该字段。
旁注：
int descendants { get; set; }读/写是令人困惑的，因为任何人都可以将其值设置为任何数字。考虑是否将其设为只读并在子节点之一更改时进行更新（需要一些自定义通知机制）。chartObject->ChartObject