일반 이진 트리 노드 소멸자 문제

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

. 삭제는 메모리를 해제하지만 그 안에 저장된 데이터는 새로운 메모리 주소에 새로운 것이 기록 될 때까지 잠시 동안 사용할 수 있습니다. 이미 free'd 메모리 주소에 액세스하는 것은 정의되지 않은 동작을 의미합니다.

현재로는 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; 
     } 
    } 
} 

테스트하지는 않았지만 제대로 작동합니다.