BST 插入 C++
我正在学习 C++ 并编写二叉搜索树。以下是我为插入方法编写的代码。
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 作为地址，即使它们确实位于我可以访问的内存中的有效位置。
谁能告诉我我可能做错了什么？
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.
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.
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?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
您的编译器可能应该发现这一点，但是在助手末尾附近有这一行：
if(n->right) Insert_Helper(v,n->right);您可能应该返回任何 <代码>Insert_Helper返回：
if(n->right) return Insert_Helper(v,n->right);Your compiler probably should have spotted this, but this line near the end of your helper:
if(n->right) Insert_Helper(v,n->right);You probably should return whatever
Insert_Helperreturns:if(n->right) return Insert_Helper(v,n->right);您可以将
if(n) size++更改为if (n != NULL) size++You can change
if(n) size++toif (n != NULL) size++