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

本文关键字：计算 递归 数据结构 元素 方法 有没有 一种 简单 | 更新日期: 2023-09-27 18:27:54

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

一个对象有一个"部件"集合。每个部件也有一个部件集合。等等。理论上，这种结构可以永远嵌套。

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

我想统计一下这个结构中的所有部件。所以，所有的树枝和树叶。（在上述示例中，共有7个部件。）

有没有一种方法可以做到这一点，而不初始化计数器并在树中递归？我当然可以这样做，但这似乎太慢了，太夸张了。有更好/更容易的方法吗？

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

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

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中低于您的级别，以确保递归计算只进行一次。

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

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

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

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

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;
    }
}

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

每个集合节点都不关心其父/子节点的计数，并且如何维护总计数的实现对集合本身是隐藏的。

相关文章：