为什么我的 C++代码无法删除我的 BST 中的所有节点?
这应该遍历 BST 并删除每个节点,包括根节点。然而,最后,我收到消息“根仍然有一个左节点”。为什么没有删除所有节点?
void deleteTree()
{
deleteNode(root);
if(root->right)
cout << "root still has a right node" << endl;
if(root->left)
cout << "root still has a left node" << endl;
root = 0;
}
void deleteNode(node *p)
{
if(p->left)
{
deleteNode(p->left);
p->left = 0;
}
if(p->right)
{
deleteNode(p->right);
p->right = 0;
}
cout << "Deleting node containing " << p->data << endl;
delete p;
}
This is supposed to traverse a BST and delete every node, including the root node. However, at the end, I get the message "root still has a left node." Why aren't all nodes deleted?
void deleteTree()
{
deleteNode(root);
if(root->right)
cout << "root still has a right node" << endl;
if(root->left)
cout << "root still has a left node" << endl;
root = 0;
}
void deleteNode(node *p)
{
if(p->left)
{
deleteNode(p->left);
p->left = 0;
}
if(p->right)
{
deleteNode(p->right);
p->right = 0;
}
cout << "Deleting node containing " << p->data << endl;
delete p;
}
如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱,如果其他用户或者作者回复了您的评论,将不能在第一时间通知您!
发布评论
评论(5)
您正在删除末尾的
p
(root
),然后尝试在deleteTree()
中访问其内容,其中root 不再指向分配的内存。结果将是不确定的。
Your are deleting
p
at the end (root
) and then trying to access its contents indeleteTree()
, whereroot
no longer points to allocated memory. The result is going to be undefined.您正在删除
root
。然后你的代码尝试访问原来的内存。你已经进入了未定义行为领域。
You're deleting
root
. And then your code is trying to access memory where it was.You're well into undefined-behaviour land there.
在
deleteNode
中删除root
后,不应取消引用它。使用调试器检查为什么root->left
不为空。You should not dereference
root
after you delete it indeleteNode
. Use a debugger to inspect whyroot->left
is non-null.在删除根之后,您将查看
root->left
,使其可在新分配的块中使用。You are looking at
root->left
after you've already deleted root, making it avalable for use in a new allocated block.我只需更改树本身,这样处理它就会更容易:
通过面向对象,每个节点现在负责它处理的内存。此外,在界面中使用 std::auto_ptr 可以清楚地表明它获取所有权。
请注意,它是为深度复制、任何其他需要 boost::shared_ptr 或等效方法的方法量身定制的。是的,std::auto_ptr 让您自己处理复制,这没有什么魔力。
这种设计比使用普通的 C 结构要干净得多,每个人都可以操作资源。您仍然可以通过访问器完全访问底层数据...但是他们注意不要调用未定义的行为...
当然,您仍然可以将其崩溃:
但是如果 C++ 可以防止意外问题,那么它就留下了大门对邪恶代码开放。
I would simply change the tree itself, it would be easier to deal with it then:
By being Object-Oriented, each Node is now responsible for the memory it handles. Also, using
std::auto_ptr
in the interface makes it clear that it takes ownership.Note that it's been tailored for deep-copying, any other approach requiring
boost::shared_ptr
or equivalent. And yesstd::auto_ptr
leaves you dealing with copying by yourself, no magic there.This design is much cleaner than using a plain
C-struct
with everyone being able to manipulate the resources. You still have full access to the underlying data via the accessor... but THEY take care not to invoke undefined behavior...Of course, you can still crash it down:
But if C++ may protect against unintended issues, it leaves the door open to evil code.