递归地删除每个节点在二叉树

以下是我的代码在二叉搜索树递归地删除每个节点：递归地删除每个节点在二叉树

template <class T> 
bool BST<T>::clear() 
{ 
    if(root == NULL) 
    { 
     cout << "Empty" << endl; 
     return false; 
    } 
    else 
    { 
     clearNodes(root); 
     return true; 
    } 

} 

template <class T> 
void BST<T>::clearNodes(BTNode<T> *cur) 
{ 
    if(cur == NULL) 
    { 
     return; 
    } 

    clearNodes(cur->left); 
    clearNodes(cur->right); 

    delete cur; 
}

在我的主要功能，当我尝试打印出来的内容，检查节点是否运行我的清除功能后删除，不知何故，我在这里遇到奇怪的显示：

我可以知道我的节点实际上是通过上面的清除功能删除？

感谢您的导游！

来源

2015-08-30 user2611244

'delete'不会改变你的树结构。你所做的只是释放内存，留下无效节点的树。另外，'delete'不会将指针设置为NULL，这似乎是您的代码依赖的。 – PaulMcKenzie

我假设“检查节点是否被删除”相当于clear()打印为空。您的算法缺少重置已删除节点的步骤。

修改后的版本是

template <class T> 
void BST<T>::clearNodes(BTNode<T>* &cur) //reference on pointer 
{ 
    if (cur==NULL) 
    { 
    return; 
    } 

    clearNodes(cur->left); 
    clearNodes(cur->right); 

delete cur; 
cur = NULL; //neccessary 
}

编辑：关于变更 一旦你观察同节点问题没有设置为null解释，第一次迭代将每次调用后设置有问题的节点，即

clearNodes(cur->right); 
cur->right = NULL;

这给责任来电，他的一个潜在的缺陷，因为迟早呼叫者可能会忘记设置为空或设置错误的值。因此，您要在clearNodes中设置。为了修改函数内的指针，您需要传递指向它的指针或引用。在C++中，我更愿意传递一个引用。因此签名变成'

void BST<T>::clearNodes(BTNode<T>* &cur);

来源

2015-08-30 12:20:36 UmNyobe

嗨，UmNyobe，谢谢你的指导，我做到了。按照您的编辑，事情正常工作。顺便说一下，我很好奇为什么2次更改是必要的？我觉得理解算法对我来说很重要，而不是单纯地获得答案。如果你能给我一些进一步的想法，我感谢你的努力。谢谢=） – user2611244

嗨UmNyobe。我想确保'cur'具有NULL子元素，并写入'if（nullptr == cur-> left && nullptr == cur-> right）{delete cur; cur = nullptr; }'在后面部分，但是valgrind报告存在内存泄漏。显然，如果条件是罪魁祸首。你能解释为什么这是错误的吗？ –

我猜测树的根没有设置为Null，因此它保存垃圾，并且打印函数正在迭代随机垃圾树。确保在清除方法结束时将NULL设置为树根。

template <class T> 
bool BST<T>::clear() 
{ 
    if (root==NULL) 
    { 
    cout << "Empty" << endl; 
    return false; 
    } 

    else 
    { 
    clearNodes(root); 
    root = NULL; 
    return true; 
    }  

}

我假设你在打印时检查树根是否为空，以确定树是否为空。

来源

2015-08-30 12:20:18

递归地删除每个节点在二叉树

回答

相关问题