二叉树：复制构造函数

Question

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

我认为我需要更改我的辅助函数签名以包含 const，但我尝试了一些组合并且 none 有效。我该如何解决这个问题？

辅助函数：

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

您正在 _postordercopy 函数中创建一个 tmp 节点，并为其赋值，但未对它执行任何操作。此外，您正在复制 Left 和 Right 的确切指针。这看起来也不对。

我认为这是递归 "copy the tree" 函数真正想要的：

    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 时无法获得的方式强制执行 const。

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 得到适当传播。

二叉树：复制构造函数

Binary Tree: Copy Constructor

c++

binary-tree

binary-search-tree