BST在C ++中插入 [英] BST insert in C++

问题描述

我正在学习C ++并编写一个二叉搜索树。下面是我为我的插入方法写的代码。

I'm learning C++ and writing a binary search tree. The following is the code I wrote for my insert method.

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);
}

我得到的错误是这样的：一切正常， ，直到我尝试插入一个重复的节点。它不添加新的节点，但它增加计数。

The bug I'm getting goes like this: It all works fine and dandy, until I try to insert a duplicate node. It doesn't add a new node, yet it increments count.

通过在GDB中观察，我发现，当我尝试添加一个字符串，我已经， Insert_Helper 正常工作并返回NULL。然而（在我的机器上）这个值是像0x6，这是超出了界限，但不是0x0像我以为它会是。我认为这导致一个问题，我有if（n）语句。在这种情况下，n的计算结果为true，因此将大小增加一个。

By observing in GDB, I've found that when I try to add a string that I already have, Insert_Helper works correctly and returns NULL. This value however (on my machine) is something like 0x6, which is out of bounds of course, but not 0x0 like I thought it would be. I think this causes an issue at the point where I have the if(n) statement. In this case n evaluates to true, and so increments size one more than it should.

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

Furthermore, at this point in my program, the nodes continue to get added correctly, but my insert function continues to return 0x6 as the address, even though they really are in valid locations in memory that I can access.

任何人都可以给我任何指针我可能做错了？

Can anyone give me any pointers as to what I might be doing wrong?

推荐答案

编译器可能应该发现这个，

Your compiler probably should have spotted this, but this line near the end of your helper:

if（n-> right）Insert_Helper（v，n-> right）;

您可能应该返回 Insert_Helper 返回：

if（n-> right）return Insert_Helper（v，n-> right）;

这篇关于BST在C ++中插入的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！