c++ - 二叉搜索树代码

Question

想为二叉搜索树写一个析构函数（它应该删除树中的所有节点）这是我到目前为止得到的

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;
}

我知道但是代码有问题，我该如何解决

Answer 1

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

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

Answer 2

失去elses。否则，如果树有left. right不会被删除。

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

最后输掉ifs。因为 delete NULL 是有效的。

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

Answer 3

当你这样做时

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

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

您也不会同时删除左右节点，由于else.

BSTNode我建议你在删除自己的孩子的地方放一个适当的析构函数：

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

那么树的析构函数就是：

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