java - 测试深度优先树

Question

我编写了一个 Java 程序来以深度优先的方式浏览一棵树。程序是正确的，但是节点的儿子的选择是随机的。例如在这棵树中:

有时，结果是:

• A-B-E-C-F-D
• A-C-F-D-B-E
• A-B-E-D-C-F

我想对该程序进行测试(单元测试)，但我不知道该怎么做？请

我想做一个包含元素的列表，并将列表的元素与我的深度优先树的结果进行比较，但我的深度优先的结果是随机的。那我就不能和List的元素比较了。

Answer 1

您要测试 2 个属性:

1. 每个节点恰好访问了一个节点
2. 遍历是深度优先

第一个很容易测试:访问的唯一节点数必须等于树中的节点数。可以针对任何随机树进行测试。

第二个稍微有点棘手 - 在一般情况下表达它可能比测试代码更复杂。更容易根据特定的已知数据选择一些有代表性的约束，即

• B必须在A之后
• E 必须在 B 之后立即
• ...

很难想象现实的代码满足所有树的第一个属性，但仅在特定情况下才会使第二个属性失败。因此，除了最正式的安全关键系统(以及它们使用动态数据结构做什么？)之外，这就足够了。