二叉树：复制构造函数

Question

我必须为签名为bstt(const bstt& other)的二叉树创建一个副本构造函数。我尝试这样做，但是在以下代码中出现以下错误（在最后一个代码块中）。

我以为我需要更改我的辅助函数签名以包括const，但是我尝试了几种组合，但没有一种有效。我该如何解决？

助手功能：

void _postordercopy(NODE*& thisT, const NODE*& otherT)
{
 if(otherT==nullptr){
  thisT=nullptr;
 }
 else
 {
  NODE* tmp=new NODE;
  tmp->Key=otherT->Key;
  tmp->Value=otherT->Value;
  tmp->Left=otherT->Left;
  tmp->Right=otherT->Right; 
  tmp->isThreaded=otherT->isThreaded;

  _postordercopy(thisT->Left,otherT->Left);
  _postordercopy(thisT->Right,otherT->Right);
 }
}

复制构造函数：

  bstt(const bstt& other)
  {
   Size=other.Size;
   _postordercopy(Root,other.Root);
  }

错误信息：

bstt.h:110:35: error: no matching function for call to ‘bstt<int, int>::_postordercopy(bstt<int, int>::NODE*&, bstt<int, int>::NODE* const&)’

Answer 1

您正在tmp函数中创建一个_postordercopy节点，对其进行分配，但并未对其进行任何操作。此外，您正在复制“左”和“右”的确切指针。看起来也不正确。

我认为这是您真正想要的递归“复制树”功能：

    NODE* copyTree(const NODE* other)
    {
         NODE* newTree = nullptr;

         if (other!=nullptr)
         {
             newTree = new NODE;
             newTree->Key = other->Key;
             newTree->Value = other->Value;
             newTree->isThreaded = other->isThreaded;
             newTree->Left = copyTree(other->Left);
             newTree->Right = copyTree(other->Right);
         }

         return newTree;
    }

然后在您的副本构造函数中，只需按如下所示进行调用：

    bstt(const bstt& other)
    {
        this->Size = other.Size;
        this->Root = copyTree(other.Root);
    }

Answer 2

我将bstt::Root声明为NODE*，因为这似乎很可能。

_postordercopy的第二个参数的类型为const NODE*&，它是指向常量NODE的指针的引用。您尝试传递的参数类型是什么？由于other被声明为const，因此其每个成员均为const。因此，other.Root是指向NODE的常量指针，也称为NODE* const – const固定在声明类型的最右边。这与参数类型不兼容。 （有关此区别的更详尽讨论，请参见What is the difference between const int*, const int * const, and int const *?。）

问题在于，无法从常量初始化非常量引用。由于other必须为const，因此您需要更改函数参数的类型以匹配您提供的参数。一种解决方案是移动const，以便它限定指针而不是指向对象的指针：NODE* const &。另一个解决方案是删除“＆”号，因为在这种情况下这有点浪费：const NODE*。 （参考添加了一个额外的间接层，该层没有任何好处。）

虽然可以解决您的直接编译器错误，但是在代码中还有其他错误需要解决。另外，我将考虑添加两个访问器函数以获取根节点。这些功能可能会以您直接访问const时无法获得的方式强制执行Root。

NODE *& get_root() { return Root; }
const NODE * const & get_root() const { return Root; }

[主要区别在于，other.Root的类型为NODE * const，这会删除该节点的const限定词，而other.get_root()将产生一个const NODE * const，该词会传播该限定词。同时，由于this->get_root()不符合NODE*资格，因此this将产生简单的const。您将使用相同的语法，并且const -ness会适当传播。