通用二进制树节点的析构函数问题

Question

我一直在工作的分配，现在我只能和车析构函数。我必须用所有通常的成员函数和一些特殊的操作符创建一个通用的二叉树。还有一个限制：一切都必须反复地工作，所以没有讨厌的递归黑客这个时候。

显然有一些非常严重的问题BinTreeNode类的析构函数，因为如果我删除这样的节点：

BinTreeNode<int> * node = new BinTreeNode<int>(); 
delete node; 

我仍然可以访问其数据：

node->getData(); //should fail miserably 

所以删除无效果，但我没有可用的想法，我应该如何纠正析构函数。 在我看来，该算法应该是有关的权利，所以我怀疑有什么毛病我怎么使用指针，但在这一点上我很困惑，我甚至不知道我自己的代码。

代码我有这么远：

BinTree.h

#ifndef BINTREE_H_ 
#define BINTREE_H_ 

#ifndef NULL 
#define NULL 0 
#endif 

#include "BinTreeNode.h" 

template <class T> 
class BinTree 
{ 
    private: 
     BinTreeNode<T> * root; 
    public: 
     //constructors and destructor 
     BinTree(): 
      root(NULL){} 

     BinTree(T data): 
      root(new BinTreeNode<T>(data)){} 

     ~BinTree(); 

     //search 
     BinTreeNode<T> * search(T data); 

     //insert 
     bool insert(T data); 

     //remove 
     bool remove(T data); 
}; 

template <class T> 
BinTree<T>::~BinTree() 
{ 
    delete root; 
} 

template <class T> 
BinTreeNode<T> * BinTree<T>::search(T data) 
{ 
    BinTreeNode<T> * node = new BinTreeNode<T>(data); 
    BinTreeNode<T> * current = root; 

    while (current != NULL) 
    { 
     if (*current == *node) 
     { 
      delete node; 
      return root; 
     } 
     else if (*node < *current) 
     { 
      current = current->getLeft(); 
     } 
     else 
     { 
      current = current->getRight(); 
     } 
    } 
    delete node; 
    return NULL; 
} 

template <class T> 
bool BinTree<T>::insert(T data) 
{ 
    BinTreeNode<T> * node = new BinTreeNode<T>(data); 
    BinTreeNode<T> * current = root; 

    while (current != NULL) 
    { 
     if (*current == *node) 
     { 
      delete node; 
      return false; 
     } 
     else if (*node < *current) 
     { 
      if (current->getLeft() == NULL) 
      { 
       current->setLeft(node); 
       return true; 
      } 
      else 
      { 
       current = current->getLeft(); 
      } 
     } 
     else 
     { 
      if (current->getRight() == NULL) 
      { 
       current->setRight(node); 
       return true; 
      } 
      else 
      { 
       current = current->getRight(); 
      } 
     } 
    } 
    return false; 
} 

#endif 

BinTreeNode.h

#ifndef BINTREENODE_H_ 
#define BINTREENODE_H_ 

#ifndef NULL 
#define NULL 0 
#endif 

template <class T> 
class BinTreeNode 
{ 
    private: 
     T data; 
     BinTreeNode<T> *left, *right, *parent; 
    public: 
     //constructors and destructor 
     BinTreeNode(): 
      data(NULL), left(NULL), right(NULL), parent(NULL){} 

     BinTreeNode(T data): 
      data(data), left(NULL), right(NULL), parent(NULL){} 

     ~BinTreeNode(); 

     //set and get data member 
     T getData() const; 

     void setData(T data); 

     //set and get left and right branches 
     BinTreeNode<T> * getLeft() const; 

     BinTreeNode<T> * getRight() const; 

     void setLeft(BinTreeNode<T> * node); 

     void setRight(BinTreeNode<T> * node); 

     //set and get parent 
     BinTreeNode<T> * getParent() const; 

     void setParent(BinTreeNode<T> * node); 

     //comparison operators 
     bool operator<(const BinTreeNode<T>& node) const; 
     bool operator>(const BinTreeNode<T>& node) const; 
     bool operator==(const BinTreeNode<T>& node) const; 
}; 

template <class T> 
BinTreeNode<T>::~BinTreeNode() 
{ 
    BinTreeNode<T> * current = this; 
    BinTreeNode<T> * parent = NULL; 
    while (current != NULL) 
    { 
     parent = current->getParent(); 
     if (current->getLeft() == NULL) 
      current = current->getLeft(); 
     else if (current->getRight() == NULL) 
      current = current->getRight(); 
     else 
     { 
      if (parent->getRight() == current) 
       parent->setRight(NULL); 
      else 
       parent->setLeft(NULL); 
      current = NULL; // this line (among others) is very suspicious 
     } 
     current = parent; 
    } 
} 

template <class T> 
T BinTreeNode<T>::getData() const 
{ 
    return data; 
} 

template <class T> 
void BinTreeNode<T>::setData(T data) 
{ 
    this->data = data; 
} 

template <class T> 
BinTreeNode<T> * BinTreeNode<T>::getLeft() const 
{ 
    return left; 
} 

template <class T> 
BinTreeNode<T> * BinTreeNode<T>::getRight() const 
{ 
    return right; 
} 

template <class T> 
void BinTreeNode<T>::setLeft(BinTreeNode<T> * node) 
{ 
    node->setParent(this); 
    left = node; 
} 

template <class T> 
void BinTreeNode<T>::setRight(BinTreeNode<T> * node) 
{ 
    node->setParent(this); 
    right = node; 
} 

template <class T> 
BinTreeNode<T> * BinTreeNode<T>::getParent() const 
{ 
    return parent; 
} 

template <class T> 
void BinTreeNode<T>::setParent(BinTreeNode<T> * node) 
{ 
    parent = node; 
} 

template <class T> 
bool BinTreeNode<T>::operator<(const BinTreeNode<T>& node) const 
{ 
     return this->data < node.data; 
} 

template <class T> 
bool BinTreeNode<T>::operator>(const BinTreeNode<T>& node) const 
{ 
    return this->data > node.data; 
} 

template <class T> 
bool BinTreeNode<T>::operator==(const BinTreeNode<T>& node) const 
{ 
    return this->data == node.data; 
} 

#endif /* BINTREENODE_H_ */ 

Answer 1

你BinTreeNode析构函数应该简单地：

template <class T> 
BinTreeNode<T>::~BinTreeNode() { 
    delete left; 
    delete right; 
} 

这将递归地调用左侧和右侧的析构函数，释放为这些节点及其子节点分配的内存。这将因此释放整个树。

将NULL分配给指针不会释放它指向的内存。

在另一方面，你提什么，即删除后，该行：

node->getData(); 

仍返回数据，是完全正常的。删除释放内存，而是存储在其中的数据可能仍然可用了一段时间，直到新的东西写的内存地址。访问已经释放的内存地址意味着未定义的行为。

BTW，你应该使用 “0”（不带引号）在C++而不是NULL。因此，这是没有必要使用#ifndef NULL（...）。

编辑：我没有看到“无递归”评论。这是一个非递归算法：

#include <deque> 

/* ... */ 

template <class T> 
BinTreeNode<T>::~BinTreeNode() { 
    std::deque deq; 
    // we're going to delete our children 
    deq.push_back(this); 
    while(deq.size()) { 
     BinTreeNode<T> *ptr = deq.front(); 
     deq.pop_front(); 
     if(ptr) { 
      deq.push_back(ptr->left); 
      deq.push_back(ptr->right); 
      // we don't want the child nodes 
      // to double delete the children 
      ptr->left = 0; 
      ptr->right = 0; 
      // avoid deleteing ourselves 
      if(ptr != this) 
       delete ptr; 
     } 
    } 
} 

我没有测试过它，但它应该工作。