創建二進制搜索樹時出現分段錯誤問題

Question

我開始時提供了所有我認爲相關的代碼。基本上二進制搜索樹已經定義了，我們需要添加一個父節點功能。我已經這樣做了，但是我不斷收到分段錯誤。

template <class TKey> 
class bst { 
    private: 
    struct node { 
     node() { key=TKey(); link[0]=link[1]=NULL; parent=NULL; } 
     operator TKey() { return key; } 
     void print(); 

     TKey key; 
     node *link[2]; 
     node *parent; 
    }; 

    public: 
    class iterator { 
    public: 
    private: 
     friend class bst<TKey>; 
     node *p; 
    }; 
    node *prev_node; 
    iterator begin() { } 
    iterator end() { } 

    bst() { Troot=NULL; } 
    ~bst() { clear(Troot); } 

    bool empty() { return Troot==NULL; } 
    void clear() { clear(Troot); Troot=NULL; } 

    void erase(TKey &key); 
    void insert(TKey &key); 

    void print_inorder() { print_inorder(Troot); } 
    void print_bylevel(); 

    private: 
    void clear(node *); 

    node *minmax_key(node *, int); 
    node *erase(node *, TKey &); 
    node *insert(node *, TKey &); 

    void print_inorder(node *); 

    node *Troot; 
}; 

那就是類定義。

template <class TKey> 
void bst<TKey>::insert(TKey &key) 
{ 
    Troot = insert(Troot, key); 
} 

template <class TKey> 
class bst<TKey>::node *bst<TKey>::insert(node *T, TKey &key) 
{ 

     cout << "insert1" << endl; 
    if (T == NULL) { 

     T = new node; 
     T->key = key; 
     if (prev_node != NULL) 
      T->parent = prev_node; 
     cout << T->parent->key; 
    } else if (T->key == key) { 
     cout << "key " << key << " already in tree" << endl; 
    } else { 
     prev_node = T; 
     int dir = T->key < key; 
     T->link[dir] = insert(T->link[dir], key); 
    } 

    return T; 
} 

這些是插入功能。我猜我正在做一些亂七八糟的事情，因爲我仍然很生疏，遞歸。當我運行使用該樹的測試程序時，它會輸出inser1行，但會發出seg故障。所以我知道這是搞亂了第一次插入。任何幫助？如果您需要查看代碼的其餘部分，我可以把它放在一起，但它會有很多與我所做的更改無關的東西。

Answer 1

我想的段錯誤是在這條線

COUT < < T->父 - >鍵;

如果T> parent爲空，那麼如果T是新創建的根（即，如果prev_node == NULL），那麼您無法訪問NULL值的'key'。

注意：請注意，我只刪除了您的代碼，所以這只是我遇到的第一件事情，可能還有其他錯誤。

編輯： 你是什麼意思，「我還有問題」，你有什麼問題？

這可能不是我將如何實施BST插入，但我不能看到任何跳出來說這是錯誤的。

我將如何實現它，而不是一個全局變量prev_node，我可能會改變，像這樣的代碼：

template <class TKey> 
void bst<TKey>::insert(TKey &key) 
{ 
    // Note that I have an initial prev_node of NULL 
    Troot = insert(Troot, key, NULL); 
} 

// Note the extra function parameter 
template <class TKey> 
class bst<TKey>::node *bst<TKey>::insert(node *T, TKey &key, node *prev_node) 
{ 

    cout << "insert1" << endl; 
    if (T == NULL) { 

     T = new node; 
     T->key = key; 
     // I have a habit of always using braces, so that it is easier to read. 
     // This would have helped you with your initial problem. 
     if (prev_node != NULL) { 
      T->parent = prev_node; 
     } 
     //cout << T->parent->key; 
    } else if (T->key == key) { 
     cout << "key " << key << " already in tree" << endl; 
    } else { 
     int dir = T->key < key; 
     T->link[dir] = insert(T->link[dir], key, T); // Note diff here 
    } 

    return T; 
} 

除非你使用prev_node別的地方。

但是，這不應該改變怎麼插入的作品，除非您的實現：

1. prev_node不爲空最初出於某種原因（這將是在連續插入物的情況，除非你是某處將其復位其他）。
2. 事情是當你使用它改變prev_node（認爲線程安全）