Блог

Я пишу конструктор для бинарного дерева поиска, проблема в том, что вспомогательная функция внутри дерева вызывается бесконечно, это в конечном итоге приводит к переполнению стека.

 void copyTree(myTreeNode* amp; copy, const myTreeNode* amp; originalTree)
{
    if(originalTree==NULL)
    {
        copy=NULL;
    }
    else
    {
        copy=new myTreeNode();
        cout<<"This is the data my friend: "<<endl<<copy->data.getCharacter()<<endl;
        copy->data=originalTree->data;
        copyTree(copy->left, originalTree->getLeft());
        copyTree(copy->right,originalTree->getRight());
    }
}

//this is the copy constructor for the tree
myTree (const myTree amp; copy)
{
    this->copyTree(this->root,copy.getRoot());
}

//and this is the way I have written the getLeft and getRight Functions
//they both return references to the left and rightNodes

const myTreeNode *amp; getLeft() const
{
    const myTreeNode*  ptr=NULL;
    if(this->left)
    {
        ptr=this->left;
    }
    return ptr;
}
  

P.S объект data не является примитивным типом данных, но у него нет динамического выделения памяти.

Я не уверен, как это может вызывать бесконечную рекурсию, но ваша getLeft() функция кажется подозрительной. Вы возвращаете ссылку на что-то в стеке. Кто знает, что происходит с этой памятью после этого. Похоже, вы продолжаете использовать один и тот же слот в памяти снова и снова, так что вы, возможно, создаете цикл вместо дерева.

Измените его так, чтобы он возвращал указатель, а не ссылку на указатель (удалите ‘amp;’).

@JCooper разобрался с этим — я просто предоставляю пример кода. Функция getLeft() должна выглядеть примерно так. Пожалуйста, обратите внимание, что я НЕ создаю никаких НОВЫХ переменных, поэтому проблемы со сроком службы стека нет.

 const myTreeNode * getLeft() const
{
    //may be NULL
    return this->left;
}
  

(РЕДАКТИРОВАТЬ: сделано код более сжатым. Спасибо @molbdnilo!)