在树结构中计算子孙节点数

Question

我有一个类，它会递归地调用自身来形成一种类似树形的数据结构：

public class chartObject
{
    public string name { get; set; }
    public int descendants { get; set; }
    public List<chartObject> children { get; set; }
}

对于树中的每个对象，我希望能够填充其“descendant”属性，以显示位于其下方的对象数量。

示例结构：

chartObject1 (descendants: 4)
└-chartObject2 (descendants: 0)
└-chartObject3 (descendants: 2)
└--chartObject4 (descendants: 1)
└---chartObject5 (descendants: 0)

这个问题最有效的解决方法是什么？

- Rkaede

Answer 1

如何看待递归公式：

children.Count + children.Sum(c => c.descendants)

如果树不是不可变的（从类声明中可以看出它不是），并且您希望在可变性的情况下实现高效率，则需要进行更加复杂的操作。可以考虑标记部分树为“脏”，并在修改时急切地强制重新评估这个度量，以便“冒泡”作为树的一部分。

- Ani

---

我在编程方面还很新，您能解释一下这段代码的含义以及它如何使用吗？ - Rkaede

Answer 2

这对我有效：

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>() { }
                        }
                    }
                }
            }
        }
    }
};

然后得到了这个结果：

- Enigmativity

Answer 3

为了使计算最有效，将其结果缓存到节点本身中。否则，每次查找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);
    }
}

- Sergey Kalinichenko

Answer 4

遍历树的所有节点（深度优先即可），并在完成子节点后将“descendants”属性设置为子节点的后代数+子节点数量的总和。您必须在每次更改树结构时执行此操作。您应该能够仅限于更改元素的父级来限制更新。

如果节点被设为不可变，则可以在创建时填充该字段。

附注：

• 您的树现在是可变的（可以在任何地方轻松添加更多子节点），因此最好有一个计算后代数的方法，而不是节点上的属性。
• 将计算属性 int descendants { get; set; } 设为读/写会让人感到困惑，因为任何人都可以将其值设置为任意数字。考虑使其只读，并在其中一个子节点更改时进行更新（需要一些自定义通知机制）。
• 代码风格-对于打算公开的代码，请考虑使用大写字母命名类（遵循Microsoft的C#编码准则）。chartObject -> ChartObject

- Alexei Levenkov