摧毁整个AVL树
问题描述:
我有一个问题完全删除我的AVL树。我已经想出了如何删除一个节点,但我的destroyTree
函数似乎并没有实际上以递归方式销毁每个节点。我可能做错了什么?摧毁整个AVL树
我有一个结构nodeType<myType>
template <class myType>
struct nodeType {
myType keyValue;
int nodeHeight;
nodeType<myType> *left;
nodeType<myType> *right;
};
,我试图删除所有现有的节点:
if(node != NULL) {
destroyTree(node->left);
destroyTree(node->right);
delete node;
}
node = NULL;
,但这似乎并没有正确地删除节点,高度检查时尽管在尝试打印时崩溃,它仍然给我高度之前的高度。
destroyTree(root);
if(root == NULL)
std::cout << "destroyed" << std::endl;
:在主函数调用破坏树是我在这段代码中使用一个简单的if语句
template <class myType>
void avlTree<myType>::destroyTree()
{
destroyTree(root);
if(root == NULL)
std::cout << "destroyed" << std::endl;
}
表明,根本不为空(是不打印)
答
看可能你的destroyTree函数有这个原型:
void destroyTree(nodeType<myType> *node);
问题是节点不能更新调用者的内存地址,但只有调用者指向的内容。这意味着root永远不会更新,即它的内容不能更新为NULL。
要做到这一点,你需要一个原型是类似的东西:
void destroyTree(nodeType<myType> **node);
答
我猜你是不是引用采取节点,因此,当您的节点设置为NULL
你实际上将该节点的本地副本设置为空。
不会起作用,因为root
采取的是价值 - 将有后函数调用前值:
template <class myType>
void avlTree<myType>::destroyTree(nodeType<myType>* node) // note node taken by value here
{
if(node != NULL) {
destroyTree(node->left);
destroyTree(node->right);
delete node;
}
node = NULL;
}
会工作,因为root
采取的是参考 - 将在函数调用后空:
template <class myType>
void avlTree<myType>::destroyTree(nodeType<myType>* &node) // note node taken by reference here
{
if(node != NULL) {
destroyTree(node->left);
destroyTree(node->right);
delete node;
}
node = NULL;
}
我看不错,但我建议你'节点 - > left'和删除后'节点 - > right'到'NULL'设置。是什么让你认为节点没有被删除? – 2014-10-01 00:58:11
这是一种方法?我不太记得C++,但是你必须说一些类似'self.destroyTree'的东西吗? – 2014-10-01 01:00:01
@JonathonReinhart因为在调用'destroyTree'后调用我的高度函数仍然会给我高度,尽管它应该为零 – 2014-10-01 01:01:02