2

我在 C# 对象中有一个递归数据结构。

一个对象有一个“部分”的集合。每个 Part 也有一个 Parts 集合。等等。该结构理论上可以永远嵌套。

object
--> Part
--> Part
  --> Part
  --> Part
    --> Part
  --> Part
--> Part

我想计算这个结构中所有部件的数量。所以，所有的树枝和树叶。（在上面的示例中，共有 7 个部件。）

有没有办法在不初始化计数器并通过树向下递归的情况下做到这一点？当然，我可以做到这一点，但它似乎很慢而且有点矫枉过正。有没有更好/更简单的方法？

4

4 回答 4

5

对于计数或任何其他类型的聚合，处理递归数据结构的一种自然方式是使用递归函数：

class Part {
    IEnumerable<Part> SubParts {get;set;}
    public int TotalParts {
        get {
            return 1 + SubParts.Sum(p => p.TotalParts);
            //     ^                       ^
            //     |                       |
            // Add one for this part       |
            //                             |
            //         Use LINQ to aggregate counts recursively
        }
    }
}

该函数假定较低级别的部分在较高级别的部分之间不共享，即您的部分图是一棵树。提高此类函数性​​能的一种方法是将结果缓存在 中低于您的级别Part，以确保递归计算仅执行一次。

您可以通过实现队列或堆栈来避免递归，但实现不会那么简单。

于 2013-08-16T13:28:47.000 回答
2

您可以覆盖每个元素的 Add 方法，并在添加元素时在每个 Part 上保留一个 count 属性，类似于 List.Count

否则没有比迭代更准确的方法了。对于大小的估计，您可以取一个有代表性的样本并从中推断出一个粗略的大小。

于 2013-08-16T13:30:52.603 回答
2

这是一个非递归解决方案，而不是迭代解决方案，它也能够遍历树并计算节点。

public class Part
{
    public IEnumerable<Part> Children { get; set; }
    public int Count()
    {
        var stack = new Stack<Part>();
        stack.Push(this);

        int total = 0;
        while (stack.Any())
        {
            total++;
            foreach (var child in stack.Pop().Children)
                stack.Push(child);
        }

        return total;
    }
}
于 2013-08-16T13:44:05.343 回答
0

我只会使用递归，但如果你真的想避免它，那么你可以覆盖集合的添加/删除方法，并使用包含对象上的方法的委托来更新totalCount变量的单个实例（每个包含对象，不是每个集合）。每次从树中的任何集合中添加或删除部件时，totalCount都会通过委托修改变量。

每个集合节点都忽略了它的父/子节点的计数，并且如何维护总计数的实现对集合本身是隐藏的。

于 2013-08-16T13:47:28.413 回答