模拟树数据结构

本文关键字：数据结构 模拟 | 更新日期: 2024-10-24 02:01:56

我正在编写一个程序，该程序采用给定的二进制树，并尝试确定该树是否平衡。

该程序需要一个二进制树作为输入，例如：1，-1，-2，-3将用1作为根节点表示，随后的.getLeft（）（或.getRight（），如果树的平衡方式不同！）命令将产生-1、-2、-3。

如果需要重复调用不同的节点对象，我该如何实现这种行为？在moq中实现这一点是最佳实践，还是只使用简单的实现更好。

模拟树数据结构

使用普通实现。我不建议你在这种情况下使用假货。创建fake的成本将高于为将要测试的每个场景创建树的成本。另一个危险是创建超过指定的测试，该测试在任何更改时都将失败。

你的方法可能会实现如下：

    public static bool isBalanced(Node root){
        if(root==null){
            return true; 
        }
        else{
            int lHight = root.left.height();
            int rHight = root.right.height();
            if(Math.Abs(lHight - rHight) > 1)
            {
                return false;
            }
            return isBalance(root.left) && isBalance(root.right);
        }
    }

正如你所看到的，有一个递归。通常很难用fakes测试递归方法。在你的情况下，你可以在没有任何虚假的情况下测试方法行为，所以我认为这是正确的选择。

我建议您测试以下行为：

空树，根平衡，根不平衡（向左，向右），多层树：平衡，向右，向左

如果你要创建上面的场景，你可能涵盖了所有的情况，并且你的测试不会被过度指定。。。

相关文章：