摧毁整个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; 
}

表明，根本不为空（是不打印）

来源

2014-10-01 Syntactic Fructose

我看不错，但我建议你'节点 - > 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

看可能你的destroyTree函数有这个原型：

void destroyTree(nodeType<myType> *node);

问题是节点不能更新调用者的内存地址，但只有调用者指向的内容。这意味着root永远不会更新，即它的内容不能更新为NULL。

要做到这一点，你需要一个原型是类似的东西：

void destroyTree(nodeType<myType> **node);

来源

2014-10-01 01:41:29 Amadeus

我猜你是不是引用采取节点，因此，当您的节点设置为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; }

来源

2014-10-01 01:42:12

摧毁整个AVL树

回答

相关问题