有一种简单的方法来计算递归数据结构中的元素吗？

Question

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

对象具有"部件"的集合.每个零件还有一个零件集合.等等.结构理论上可以永远嵌套.

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

我想得到这个结构中所有部件的数量.所以,所有的分支和叶子.(在上面的例子中共有7个部分.)

有没有办法在不初始化计数器并通过树递归的情况下执行此操作？当然,我可以做到这一点,但它看起来很慢而且有点过分.有更好/更简单的方法吗？

Answer 1

对于计数或任何其他类型的聚合,处理递归数据结构的自然方法是使用递归函数:

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,以确保递归计算只进行一次.

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