题
如何测试数据结构是否正确构建?我正在实现一种修改后的基数树,并且想知道如何检查数据结构是否正确构建。
考虑一棵树 TreeNode {String, Int}
节点。您总是希望将新的子节点追加到值等于 0 的最深节点,如下例所示:
Root, 0 - Child_1, 5 - Child_2, 0 - Child_3, 1
问题是,如何进行单元测试 树结构 是否如您所愿建立?TreeNode 只有一种方法,即 insert
.
到目前为止我的想法是写 TreeVisitor
它将遍历树并将每个节点转换为字符串。上面示例中的树可能如下所示:
[Root, 0 [Child_1, 5][Child_2, 0 [Child_3, 1]]]
了解构建树的算法,如果我知道要插入哪些元素,我可以手动创建这样的字符串。我的单元测试看起来像这样(使用相同的示例)。
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) 是否按预期工作:-)
解决方案
这看起来像是测试驱动设计的实际应用案例。仅具有“插入”方法的接口是不可测试的,因为它也无法使用。建造一棵树,如果你无法看到或用它做任何事情,你所建造的树不会让你有任何进展。
弄清楚您希望客户端如何访问树(访问方法、访问者界面或其他)。然后通过他们进行测试。
如果存在内部复杂性,您无法轻松通过公共接口(即该树更像是 Java TreeMap,而不是放入 TreeView 中的树类型),您可以使用:
- 断言和不变量
- 类似于裸露的debugverifytree方法。
- 蛮力:插入36542个伪随机项,使用覆盖工具检查覆盖所有情况。
无论哪种方式,每当您编写测试时,请确保提出问题“此代码的任何客户端都会关心此测试是否失败?”。如果没有,请将其删除。
其他提示
也许你可以用你自己的子类替换单元测试中的 TreeNode 的实现,这些子类公开了让你以递归方式检查当前子集的方法。这些方法将添加到 TreeNode 实现中以帮助单元测试,并且不会替换其现有功能,因此您仍然可以进行有效测试。
我通常最终做的是制作指示您正在测试的东西的值或名称。因此,对于树,名称可能表示深度和子索引。
TreeNode root = new MyTreeNode("0.0", 0);
root.insert(new MyTreeNode("1.0", 5));
root.insert(new MyTreeNode("1.1", 0));
root.insert(new MyTreeNode("2.0", 1));
verify(root, 0, 0);
...
public void verify(TreeNode node, int depth, int index) {
verifyName(node, depth, index);
int numChildren = node.getChildCount();
depth++;
for (int i = 0; i < numChildren; i++) {
verify(node.getChildAt(i), depth, i);
}
}
public void verifyName(TreeNode node, int depth, int index) {
StringBuilder expectedName = new StringBuilder();
expectedName.append(depth).append('.').append(index);
assertEquals("Tree node not in expected place",
expectedName.toString(), node.getName());
}
现在我可以想象测试一棵相当大的树。如果递归的深度是一个问题,那么你可以使用堆栈来解包递归方法。
public void verify(TreeNode root) {
Stack<TreeNode> toBeVerified = new Stack<TreeNode>();
verifyName(root, 0, 0);
toBeVerified.push(root);
while(!toBeVerified.isEmpty()) {
TreeNode node = toBeVerified.pop();
int depth = getDepth(node.getName()) + 1;
int numChildren = node.getChildCount();
for (int i = 0; i < numChildren; i++) {
verifyName(node, depth, i);
toBeVerified.push(node);
}
}
}
public int getDepth(String name) {
return Integer.parseInt(name.substring(0, name.indexOf('.')));
}