段错误二叉树

Question

我在我的节目得到一个分段错误，当我尝试插入到二叉搜索树。这里的节点声明：

template < class T > class binTreeNode { 
friend class binTree <T>; 
friend class binSTree <T>; 
public: 
    // default constructor 
    binTreeNode (const T& newData =T(), binTreeNode <T>* newLeft = 0, binTreeNode <T>* newRight = 0) { 
     data = newData; 
     left = newLeft; 
     right = newRight; 
    } 
private: 
    T data; // data value in node 
    binTreeNode <T> *left, *right; // links to other nodes 
}; 

下面的功能都是新的，一切（如高度的功能和构造函数）都在父类中完成的，真的不应该是相关的。新的功能是：

template <class T> 
class binSTree : public binTree<T> { 
public: 
    void insert (const T& newData) { 
     if (root == NULL) { 
      root = new binTreeNode<T>(newData); 
     } 
     else 
      insert(root,newData); 
    } 
    bool search (const T& x) const { 
     if (root != NULL) 
      return search(root,x); 
     else 
      return false; 
    } 
    bool remove (const T& x) { 
     if (root == NULL) 
      return false; 
     remove(root,x); 
     return true; 
    } 
protected: 
    binTreeNode<T>* root; 
private: 
    void insert (binTreeNode<T>*& ptr, const T& x) { 
     if (ptr == NULL) {  // Base case, actual insertion 
      binTreeNode<T>* newNode; 
      newNode = new binTreeNode<T>(x); 
      ptr = newNode; 
      return; 
     } 
     if (x == ptr->data) 
      return; 
     else if (x < ptr->data) 
      insert(ptr->left,x); 
     else 
      insert(ptr->right,x); 
     return; 
    } 
    bool search (binTreeNode<T>* ptr, const T& x) const { 
     if (ptr->data == x) 
      return true; 
     else if (x < ptr->data && ptr->left != NULL) 
      search(ptr->left,x); 
     else if (ptr->right != NULL) 
      search(ptr->right,x); 
     else 
      return false; 
    } 
    binTreeNode<T>* remove (binTreeNode<T>* ptr, const T& x) { 
     if (ptr == NULL) 
      return NULL; 
     else if (ptr->data == x && leaf(ptr)) { 
      delete ptr; 
      ptr = NULL; 
      return ptr; 
     } 
     else if (ptr->data == x && !leaf(ptr)) 
      return ptr; 
     else if (x < ptr->data) { 
      ptr->left = remove(ptr->left,x); 
      return ptr; 
     } 
     else { 
      ptr->right = remove(ptr->right,x); 
      return ptr; 
     } 
    } 
    bool leaf (binTreeNode<T>* node) const { 
     if (node->left != NULL || node->right != NULL) 
      return false; 
     return true; 
    } 
}; 

段故障，根据Valgrind的，是在有条件私营插入其中I检查（X == ptr->数据）。有没有人有任何想法，为什么这是？我完全打了一堵墙。感谢：3

Answer 1

。在你的remove代码中的问题，可能会或可能不会的事业的崩溃，但绝对应该修正：当你递归删除ptr->left或ptr->right导致删除节点，还应该将left或right父指针设置为NULL;否则你会打开你的代码来发现与悬挂指针相关的错误。