段錯誤二叉樹

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;否則你會打開你的代碼來發現與懸掛指針相關的錯誤。