通用二進制樹節點的析構函數問題

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

我沒有測試過它，但它應該工作。