单元测试binarysearchtree

可以说你有这个二叉搜索树（BST）。见下面的代码。属性：单元测试binarysearchtree

节点的左侧子树只包含键小于节点键的节点。
节点的右子树只包含密钥大于节点密钥的节点。
左右子树也必须是二叉搜索树。

你会如何测试它？您无法访问节点并且无法验证结构。您不能单独测试插入功能。

1）您可以从BST创建一个继承的测试类，并声明额外的方法来测试。这是常见的吗？

2）以不同方式实施BST。有一个树类。这个类可以访问子节点等，并实现基本的树功能。从Tree继承BST。在Tree提供的方法的帮助下测试BST。

3）您的意见？

谢谢。

template <typename ValueType> 
class BinarySearchTree 
{ 
public: 

    BinarySearchTree() : m_count(0), m_root(nullptr) {} 
    void Insert(const ValueType& elementToInsert); 
    bool Remove(const ValueType& elementToRemove); 
    bool Contains(const ValueType& elementToFind); 
    bool IsEmpty() const; 
    size_t Count() const; 
    ValueType Max() const; 
    ValueType Min() const; 
    int Delimiter() const; 
    void PrintToFile(std::ofstream& outFile); 
    void BuildFromFile(std::ifstream& inFile); 
    ~BinarySearchTree() { delete m_root; } 
    // TODO: copy ctr, copy assignment operator, move ctr 

private: 

    struct Node 
    { 
     Node(const ValueType& value) : value(value), parent(nullptr), left(nullptr), right(nullptr) {} 
     ~Node() { delete left; delete right; } 
     // TODO: copy ctr, copy assignment operator, move ctr 

     ValueType value; 
     Node* parent; 
     Node* left; 
     Node* right; 
    }; 

    Node* m_root; 
    int m_count; 
};

来源

2016-11-09 bencemeszaros

真的很有趣的问题！但是，不幸的是，我认为它会很接近，因为太广泛了......但是，恕我直言，你必须将它测试为一个黑盒子：你通过插入，删除...输入刺激，并使用访问器来查看他有什么。另一种解决方案是使用一些单元测试库来测试你的代码以允许访问私人领域 – Garf365

约翰拉科斯（C++ std委员会）曾经写过一本关于[大规模C++设计]的书（https：// www。 amazon.com/Large-Scale-Software-Design-John-Lakos/dp/0201633620）。它广泛谈论关于可测试性的设计，你应该抓住它。 – StoryTeller

以下常见的STL实现的线，我想你BinarySearchTree类拆分成不同的组件：

一些二叉树类，只有拥有节点工程。让我们命名它BinaryTree。它支持插入和删除Node *，遍历（begin和end）和有用的树操作（如rotate平衡树）。但它不会分配任何东西或找到任何东西（没有ValueType已知）。
保证深度为log(n)的特定二叉树版本。我们称之为AVLTree（你也可以用红黑色或其他东西）。该树意识到ValueType，并将实现诸如find和插入/删除值（包括内存管理）的方法。它也将根据存储的值来处理平衡。

（最重要的是，你可以再建类似set或map像STL做的。）进行测试

优点：

的BinaryTree类将在作为模板树中使用的Node类型（基于性能原因基于多态virtual方法的模板）。因此，对于单元测试，您可以使用不同类型的Nodes构建BinaryTree。这些特殊类型的节点可以为您的测试保留附加信息（例如计数器）（例如，在某些操作中，左侧孩子最多只会更改一次）。

另一方面，AVLTree只能基于值进行测试，例如。插入后可以找到一些值。这基本上与您的原始BinarySearchTree相同。我建议添加一些测试方法（例如，verify_invariants）迭代完整的树并检查所有的不变量（例如，深度，节点的子节点的父亲是节点的log(n)）。这可能是昂贵且缓慢的，但应该仅用于您的单元测试。

只是一个结束语：如果你为自己/作业编写自己的树 - 很好！如果这应该在“真实”世界的某个地方使用，那么应该强烈考虑使用STL容器。

来源

2016-11-09 10:01:53 m8mble

谢谢。我非常喜欢你的第一部分回答，关于如何使用特殊类型的节点来实现和测试BinaryTree。 – bencemeszaros

关于第二部分。实施和使用BinaryTree的方法来访问左侧，右侧的孩子，父母并验证BinarySearchTree的结构与这些关系不是更好吗？ – bencemeszaros

你的意思是在'verify_invariant'内？当然是的。但那是唯一的地方。来自外部的其他测试/用户将无法访问树... – m8mble

单元测试binarysearchtree

回答

相关问题