BST在C++中插入

Question

我正在学习C++并编写二叉搜索树.以下是我为insert方法编写的代码.

BSTNode * BST::Insert(const std::string & v) {
    BSTNode *n = !root ? root = new BSTNode(v) : Insert_Helper(v,root);
    if(n) size++;
    return n;
}

BSTNode * BST::Insert_Helper(const std::string & v, BSTNode *n) {
    if(!n->value.compare(v))
        return NULL; // already have v
    else if(n->value.compare(v) > 0) // v goes to the left
        if(n->left) return Insert_Helper(v,n->left);
        else return n->left = new BSTNode(v);
    else // v goes to the right
        if(n->right) Insert_Helper(v,n->right);
        else return n->right = new BSTNode(v);
}

我得到的错误是这样的:它一切正常和花花公子,直到我尝试插入一个重复的节点.它不会添加新节点,但会增加计数.

通过在GDB中观察,我发现当我尝试添加我已经拥有的字符串时,Insert_Helper正常工作并返回NULL.然而,这个值(在我的机器上)就像0x6,当然超出界限,但不像我想的那样是0x0.我认为这会导致我有if(n)语句的问题.在这种情况下,n的计算结果为true,因此增加的大小比它应该增加一个.

此外,在我的程序中的这一点,节点继续正确添加,但我的插入函数继续返回0x6作为地址,即使它们确实在我可以访问的内存中的有效位置.

谁能给我任何关于我可能做错的指示？

Answer 1

您的编译器可能应该已经发现了这一点,但这一行接近您的帮助程序的结尾:

if(n->right) Insert_Helper(v,n->right);

你可能应该返回任何Insert_Helper回报:

if(n->right) return Insert_Helper(v,n->right);