c++ - 向二叉树中插入一个重复的键值

Question

我正在尝试为我的二叉搜索树类编写一个插入方法。我希望它能够将新值插入到已经具有具有相同数据值的现有节点的树中，必须导致在现有节点的右子树中创建新节点。这是我的代码。我在尝试编译时收到未处理的异常错误。我不知道我在那里做错了什么。如果有人能解释编译器给我错误的原因，那就太好了。谢谢:)

template <class elemType>
void bSearchTreeType<elemType>::insert
                 (const elemType& insertItem)
{
    nodeType<elemType> *current; //pointer to traverse the tree
    nodeType<elemType> *trailCurrent; //pointer behind current
    nodeType<elemType> *newNode;  //pointer to create the node

    newNode = new nodeType<elemType>;
    newNode->info = insertItem;
    newNode->lLink = NULL;
    newNode->rLink = NULL;

    if (root == NULL)
        root = newNode;
    else
    {
        current = root;

        while (current != NULL)
        {
            trailCurrent = current;

            if (current->info == insertItem)
            {
                current = current->rLink;
                trailCurrent->rLink = newNode;
                if (newNode->info <= current->info) //this is where the compiler say the error is
                    newNode->rLink = current;
                else
                    newNode->lLink = current;
            }
            else if (current->info > insertItem)
                current = current->lLink;
            else
                current = current->rLink;
        }//end while

        if (trailCurrent->info < insertItem)
            trailCurrent->rLink = newNode;
        else if (trailCurrent->info > insertItem)
            trailCurrent->lLink = newNode;
    }
}//end insert

Answer 1

你应该和自己做个交易。这笔交易可以是这样的:

左子树的值小于或等于根中的值，依此类推。

在你的代码中:

if (trailCurrent->info < insertItem)
  trailCurrent->rLink = newNode;

交易后是这样的:

if (trailCurrent->info <= insertItem)
  trailCurrent->rLink = newNode;