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

Question

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

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

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 中低于您的级别的结果，以确保递归计算仅完成一次。

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