java - 单元测试正确的数据结构创建

Question

如何测试数据结构是否正确构建？我正在实现一种修改后的基数树，并且一直想知道您如何检查您的数据结构是否正确构建。

考虑一棵 TreeNode {String, Int} 节点的树。 您总是希望将新的子节点附加到值等于 0 的最深节点，如下例所示:

Root, 0
- Child_1, 5
- Child_2, 0
   - Child_3, 1

Question is, how to unit test if tree structure builds up as you wished? TreeNode only has one method, which would be insert.

My idea so far was to write TreeVisitor that would walk through tree and convert each node to string. Tree from example above, could look like this:

[Root, 0 [Child_1, 5][Child_2, 0 [Child_3, 1]]]

Knowing algorithm that builds tree, I can create such string manually if I have idea what elements I'm inserting. My unit test would look like this (using same example).

TreeNode root = new TreeNode("Root", 0);
root.insert(new TreeNode("Child_1", 5));
root.insert(new TreeNode("Child_2", 0));
root.insert(new TreeNode("Child_3", 1));
TreeVisitor visitor = new TreeVisitor();
String expected = "[Root, 0 [Child_1, 5][Child_2, 0 [Child_3, 1]]]";
asssertEquals(expected, visitor.visit(root));

我觉得这不是最好的方法。首先，一旦访问者发生变化，所有测试都会失败(只需将 [ ] 更改为 ( ))。此外，这种方法允许我测试非常小的树(大到我可以手动计算的大小)。你会如何测试更大的？

一般的问题是，如何编写测试来检查数据结构是否正确构建？

我想我可能把整个测试想法弄错了，因为我刚刚接触了很多教程，人们在这些教程中测试 .Sum(a, b) 是否按预期工作:-)

Answer 1

这看起来像是测试驱动设计的实际案例。只有“插入”方法的接口(interface)是不可测试的，因为它也是不可用的。 build 一棵树，但无法看到或对您 build 的树做任何事情，这不会让您到达任何地方。

确定您希望客户端如何访问树(访问方法、访问者界面或其他)。然后通过它们进行测试。

如果您无法通过公共(public)接口(interface)轻松获得内部复杂性(即树更像是 Java TreeMap 而不是您放入 TreeView 中的树类型)，您可以使用:

• 断言和不变量
• 有点像暴露的 debugVerifyTree 方法。
• 暴力破解:插入 36542 个伪随机项，使用覆盖工具检查覆盖所有情况。

无论哪种方式，无论何时编写测试，请务必提出以下问题:“如果此测试失败，此代码的任何客户端都会关心吗？”。如果没有，请将其删除。