一般的なバイナリツリーノードのデストラクタの問題

Question

私は割り当てに取り組んできましたが、今はバグのあるデストラクタに悩まされています。私は、すべての通常のメンバ関数といくつかの特別な演算子を持つ汎用バイナリツリーを作成する必要があります。また、制限があります：すべてが反復的に動作しなければならないので、今度は厄介な再帰的なハックはありません。

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

はとても削除はありませんがあります。

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

が、私はまだそのデータにアクセスすることができます：私はこのようなノードを削除した場合ので

BinTreeNodeクラスのデストラクタを持つ非常に間違って何かが明らかにありどのように私はデストラクタを修正する必要があります使用可能なアイデアはありません。 アルゴリズムはほぼ正しいと思われるので、ポインタの使い方に何か問題があると思われますが、この時点で私は自分のコードを理解できないほど混乱しています。

私はここまでコード：

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(); 

それでも、データを返す完全に正常です：削除した後、この行は、あなたが言及何一方

、削除するとメモリは解放されますが、新しいメモリがそのメモリアドレスに書き込まれるまで、そのメモリに保存されているデータはしばらく使用可能になる場合があります。すでに空いているメモリアドレスにアクセスすると、未定義の動作が発生します。

ところで、NULLではなく、C++で "0"（引用符なし）を使用する必要があります。したがって、#ifndef NULL（...）を使用する必要はありません。

EDIT：私は「再帰なし」のコメントは見ていませんでした。

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

私はそれをテストしていませんが、動作するはずです。