Двоичное дерево: конструктор копирования

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

Я буду считать, что bstt::Root объявлено как NODE*, что представляется наиболее вероятным.

Второй параметр _postordercopy имеет тип const NODE*&, ссылка на указатель на константу NODE. Какой тип аргумента вы пытаетесь передать? Поскольку other объявлен const, каждый из его членов - const. Таким образом, other.Root - это постоянный указатель на NODE, также известный как NODE* const - const находится справа от объявленного типа. Это несовместимо с типом параметра. (См. В чем разница между const int*, const int * const и int const*? для более подробного обсуждения этого различия.)

Проблема является то, что непостоянная ссылка не может быть инициализирована из константы. Поскольку other должно быть const, вам нужно изменить тип параметра функции, чтобы он соответствовал тому, что вы ему даете. Одним из решений является перемещение const так, чтобы оно квалифицировало указатель, а не указатель на объект: NODE* const &. Другое решение состоит в том, чтобы удалить амперсанд, поскольку это немного расточительно в этом случае: const NODE*. (Ссылка добавляет дополнительный уровень косвенности, который не дает никакой пользы.) Подумайте о том, что ваша функция должна делать, и const - оцените то, что должно измениться. В этом случае узел, на который указывает второй параметр, не должен изменяться.

Хотя это устраняет вашу непосредственную ошибку компилятора, в вашем коде есть другие ошибки, которые нужно устранить. Кроме того, я хотел бы рассмотреть возможность добавления двух функций доступа для получения узла root. Эти функции могут обеспечивать 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 распространяется соответствующим образом.

Answer 2

Вы создаете 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);
    }