c++ - 我的二叉搜索树的运算符 += 有什么问题？

Question

我有一些关于二叉搜索树 (BSTreeBag) 的代码，我不太明白。

“operator +=(const BSTreeBag& addend)”需要将加数中的内容插入到我们当前的树中。如果我们拥有的当前树与“加数”相同，我们需要将我们的树加倍(以复制树中的所有项目)

这是我的代码

template <class ItemType>
void BSTreeBag<ItemType>::operator +=(const BSTreeBag& addend)
{
    if(this==&addend)//This works
    {
        binary_tree_node<ItemType>* addroot_ptr=root_ptr;//create a pointer
                                                         //that points to the current tree 
        insert_all(addroot_ptr);//This is a helper function that insert 
                                //every item of the addend into the current tree. It works fine.
    }
    else
    {
        insert_all(addend.root_ptr);
    }
}

只要不进行自赋值，这些代码行就可以完美运行。它总是停在行上

insert_all(addroot_ptr);

不提供任何有关段错误或其他问题的信息。谁能解释一下这是怎么回事？

Answer 1

一个很可能的问题是，当您将一棵树添加到自身时，会出现无限循环。就像在中一样，您在遍历树时添加节点，但由于添加了新节点，您继续迭代并添加它们，无休止。

让我们举一个简单列表的例子。假设您有以下列表:

root -> A

现在，如果您尝试将列表添加到自身，您将从根指针开始遍历列表，找到节点 A，然后添加它。现在你的列表看起来像

root -> A -> A

您继续迭代并找到...节点 A(再次)，然后添加它:

root -> A -> A -> A

等等等等。

您可能应该从 root_ptr 创建一棵全新的树，然后添加它。