1

我正在尝试用 C++ 编写二叉树实现，并且正在使用 Google Test 对其进行测试。为了测试有序遍历，我对类进行了子BTree类化，以便我可以覆盖该visit()方法，以便我可以输出到字符串而不是控制台。问题是我想使用现有逻辑向树中插入新节点，并且它插入的是基类而不是派生类，即使我将指向派生对象的指针传递给该insert()方法。有没有办法让它为所有节点插入派生类？

这是测试用例：

TEST_F(BTreeTestSuite, inOrder)
{
    class InOrderTest : public BTree
    {
    public:
        InOrderTest(int data) throw(int) : BTree(data), itsVisitString() {};
        virtual ~InOrderTest() {};
        std::string visitString(void) const { return itsVisitString; }
        virtual void visit()
        {
            std::ostringstream oss;
            oss << itsData;
            itsVisitString += oss.str();
            std::cerr << "vs1: " << itsVisitString << '|' << std::endl;
            itsVisitString += " ";
            std::cerr << "vs2: " << itsVisitString << '|' << std::endl;
        }
    private:
        std::string itsVisitString;
    };
    InOrderTest iot(20);
    iot.insert(new InOrderTest(30));
    iot.insert(new InOrderTest(15));
    iot.insert(new InOrderTest(10));
    iot.inOrder();
    EXPECT_STREQ("10 15 20 30 ", iot.visitString().c_str());
}

这是基类的相关部分：

class BTree
{
public:
    BTree(int data) throw();        // constructor(s)
    ~BTree() throw();               // destructor

    virtual void insert(BTree *node);
    unsigned count() const;
    void inOrder();
    virtual void visit();

    int   data() const throw() { return itsData; };
    BTree *left() const throw() { return itsLeft; };
    BTree *right() const throw() { return itsRight; };

protected:
    int     itsData;
private:
    // Don't allow creation of BTree without data
    BTree() throw();        // constructor(s)
    BTree   *itsLeft;
    BTree   *itsRight;
};
...
BTree::BTree(int data) throw() : itsData(data)
{
    itsLeft = itsRight = 0;
}

void BTree::insert(BTree *node)
{
    if (node->itsData < itsData)
    {
        std::cerr << "Inserting data on the left\n";
        if (itsLeft)
        {
            itsLeft->insert(node);
        }
        else
        {
            itsLeft = new BTree(node->itsData);
        }

    }

    if (node->itsData > itsData)
    {
        std::cerr << "Inserting data on the right\n";
        if (itsRight)
        {
            itsRight->insert(node);
        }
        else
        {
            itsRight = new BTree(node->itsData);
        }
    }

    /* Drop value if it already exists in tree. */
}

void BTree::inOrder()
{
    if (itsLeft) itsLeft->inOrder();
    visit();
    if (itsRight) itsRight->inOrder();
}

void BTree::visit()
{
    cout << "base-visit: " << itsData << endl;
}
4

1 回答 1

0

问题出在你的BTree::insert方法上。即使它得到了InOrderTest *你正在BTree从这两行创建一个实例：

void BTree::insert(BTree *node)
{
  // logic checks...
  itsLeft = new BTree(node->itsData);
  // more logic checks...
  itsRight = new BTree(node->itsData);
  //...
}

您可以采取两种方法来解决此问题。您可以只使用传入的节点而不是构造新对象。在这种情况下，您的根节点承担其子节点的所有权，并应注意适当地解除分配它们。由于您的单元测试无论如何都new InOrderTest没有匹配delete，因此这种方法可以工作。

第二种方法是创建一个虚拟clone方法并让您的派生类处理它自己的创建。

class BTree
{
  // BTree stuff
public:
  virtual BTree* BTree::clone() const;
  // more stuff
};

class InOrderTest : public BTree
{
public:
  InOrderTest* clone() const { return new InOrderTest(*this); }
};

此外，如果您希望客户端代码BTree从中派生，则将BTree::~BTree析构函数设为虚拟。（参见 Effective C++ item#7）

于 2013-05-24T06:34:01.223 回答