二叉搜索树码

想写的二叉搜索树析构函数（它应该删除在树中的所有节点）这是我走到这一步，二叉搜索树码

virtual ~BST() { 
    BSTNode<Data>* node = root; 
    if (node == NULL){ 
    return; 
    }else if (node->left) { 
     while(node->left){ 
     delete node; 
     } 
    }else if (node->right){ 
     while(node->right) 
     delete node; 
    } 
     isize = 0; 
}

我知道但是有一些错误代码，我该如何解决它

来源

2013-04-11 cloud9resident

向我们展示了BST类和BSTNode类。 – 2013-04-11 22:15:31

当你做eg

while(node->left){ 
    delete node; 
}

您删除节点，但实际上并没有循环到下一个节点。因此下一次在循环中node将不会是NULL，因此您解除引用未分配的数据结构未定义的行为，并可能导致崩溃。然后您尝试删除相同的node再次这仍然是未定义的行为，并且可能会导致崩溃。

您也不会删除这两个左右节点，其中只有一个是因为else。

我建议你把正确的析构函数中删除自己的孩子BSTNode：

template<typename T> 
BSTNode<T>::~BSTNode() 
{ 
    delete left; 
    delete right; 
}

然后树的析构函数将仅仅是：

BST::~BST() 
{ 
    delete root; 
}

来源

2013-04-11 22:10:57

失去else秒。否则，如果树有left。 right将不会被删除。

失去while。节点应该有自己的析构函数，并且应该递归地删除。

最后丢失if s。因为删除NULL是有效的。

virtual ~BST() { 
    BSTNode<Data>* node = root; 
    if (node == NULL){ 
    return; 
    } 
    delete node->left; 
    delete node->right; 
    isize = 0; 
}

来源

2013-04-11 22:11:58

这可能只会删除根直接的孩子，让树的其余部分“在风中”这么说。 – 2013-04-11 22:31:28

没错，那正是我在想的，但是我需要一个删除所有节点 – cloud9resident 2013-04-11 22:34:46

@JoachimPileborg Ya他不太清楚他是如何实现BST和BSTNode之间的关系的。我让他出示，但他没有。我在这里假设，既然他在节点中有左和右，那些节点也有左和右。我的意思是BST只是实际树形结构的包装。但后来我不确定。这可能是错误的。这就是为什么我向他提到节点应该有自己的析构函数并递归删除。 – 2013-04-11 22:37:19

void BST::deleteNode(BSTNode<Data> *node) { 
    if (node) { 
     deleteNode(node->left); 
     deleteNode(node->right); 
     delete node; 
    } 
} 

BST::~BST() { 
    deleteNode(root); 
}

来源

2013-04-11 22:15:16 Archie

这是否会递归删除所有节点，而不仅仅是直接节点？ – cloud9resident 2013-04-11 22:36:26

@ cloud9resident是的，这看起来好像会正确删除所有的孩子。 – 2013-04-11 22:45:15

二叉搜索树码

回答

相关问题