单元测试简单的树结构操作

Question

给定一个非常简单的结构，例如：

public class TreeNode
{
    public int ID { get; set; }
    public List<TreeNode> Children { get; set; }
}

TreeNode可能具有其他属性

当以以下方式使用时：

var tree = new List<TreeNode>(); //no root node

如果我根据某些条件对树执行添加/更新/删除操作。例如，基于一个或多个其他属性删除节点，我想比较更改前后的树图，然后通过单元测试验证以下内容：

• 树保持不变
• 指定的节点已删除
• 添加指定的节点
• 指定的节点已更新
• 上面的3同时也验证了树的其余部分是不变的

理想情况下，我会抛出一个期望值，列出未找到、未期望的节点等。然而，在这个阶段，我会对我的检查结果为真/假感到满意。

现有项目中是否有任何已知的模式/算法可以帮助实现这一点？

我很喜欢其他语言中的伪代码或示例，只要它们不依赖于我在.NET.中无法复制的功能

我的树不太可能达到超过7或8个级别，总共不超过100个节点，因为它将是测试数据，所以强力循环很好，目前不考虑性能。

我真的在寻找关于如何处理这个问题的技巧、窍门、建议和代码。

TIA

Answer 1

当我对树结构进行单元测试时，我只需构建一个已知结构的特别树，对其执行操作，并验证更改是否正是我所期望的，如果你创建了好的测试用例，这是一种非常简单但可用的方法。

不管我的经验如何，你可能会想到一些树节点的递归比较方法，这些方法可能会返回不同的子节点列表。因此，基本思想是维护两个相等的树，对其中一个树执行操作，然后检查更改了什么。

如果您没有任何显示树的UI，我还建议您使用http://www.graphviz.org/，您可以在一些操作之前和之后生成树的图片，这样您将看到整个结构是如何更改的（不适用于单元测试，但无论如何）。

最后一件事，我建议有一个根节点，它会简化你的递归算法。如果你没有root，因为对UI的一些要求，你可以修改这个部分，简单地忽略root。

Answer 2

您还可以使用一个函数来获取树的字符串表示，并简单地比较两个字符串表示，而不是比较两个树我本周早些时候就这么做了示例函数（swift）

 public var description: String {
        var s = "(value)"
        if !children.isEmpty {
            s += " {" + children.map { "($0.description)"}.joined(separator: ", ") + "}"
        }
        return s
    }

你可以像这个一样测试它

XCTAssert ( tree.description == "beverages {hot {tea {black, green, chai}, coffee, cocoa}, cold {soda {ginger ale, bitter lemon}, milk}}");